bab1 pertemuan1

8/17/2019 bab1 pertemuan1

1/10

MA 3283MA 3283

PENGANTARPENGANTAR

TEORI GRAFTEORI GRAF

Pekan I – Pekan V Pekan I – Pekan V

1.1. Graf dan graf sederhanaGraf dan graf sederhana

2.2. Isomorfisme graf Isomorfisme graf

3.3. Matriks ketetanggaanMatriks ketetanggaan

4.4. Subgraf Subgraf 5.5. Derajat titik Derajat titik

6.6. Path dan keterhubunganPath dan keterhubungan

.. !"#$e!"#$e

Graf dan subgraf Graf dan subgraf

Trees (pohon)Trees (pohon)1.1. %rees &'ohon(%rees &'ohon(

2.2. !ut )dge!ut )dge

3.3. *ond dan !ut +erte,*ond dan !ut +erte,

4.4. -ormu$a !a"$e"-ormu$a !a"$e"


2/10

MA 3283MA 3283

PENGANTARPENGANTAR

TEORI GRAFTEORI GRAF Bab 1 Bab 1Graf dan subgraf Graf dan subgraf

1.1. Graf dan graf sederhanaGraf dan graf sederhana

2.2. Isomorfisme graf Isomorfisme graf

3.3. Matriks ketetanggaanMatriks ketetanggaan

4.4. Subgraf Subgraf

5.5. Derajat titik Derajat titik

6.6. Path dan keterhubunganPath dan keterhubungan

.. !"#$e!"#$e


3/10

Pada suatu daerah tersedia 5 frekuensi berbeda yangPada suatu daerah tersedia 5 frekuensi berbeda yangdisediakan untuk 10 buah pemancar. Tentukanlahdisediakan untuk 10 buah pemancar. Tentukanlahmodel untuk menyelesaikan masalah diatas.model untuk menyelesaikan masalah diatas.

problem 2 problem 2

problem 1 problem 1Proses penyimpanan sejumlah bahan kimia CProses penyimpanan sejumlah bahan kimia C11,C,C22,C,C33, …,, …,

CCnn harus dilakukan sebuah perusahaan dengan baikharus dilakukan sebuah perusahaan dengan baik

karena ada beberapa bahan yang berbahaya jikakarena ada beberapa bahan yang berbahaya jika bersentuhan. Oleh karena itu tidak boleh diletakkan bersentuhan. Oleh karena itu tidak boleh diletakkan

dalam ruangan yang sama. Tentukan model dari kasusdalam ruangan yang sama. Tentukan model dari kasustersebut.tersebut.


4/10

GRAFGRAF Suatu graf G didefinisikan sebagaiSuatu graf G didefinisikan sebagaiordered tripleordered triple &+&G( )&G(&+&G( )&G( GG((

dimana /dimana /

• V(G)V(G) ≠≠ 0 adalah himpunan vertex (simpul, titik)0 adalah himpunan vertex (simpul, titik)

• E(G) adalah himpunan edges (garis, sisi)E(G) adalah himpunan edges (garis, sisi)

• ΨΨGG : E(G) himpunan pasangan tak: E(G) himpunan pasangan tak

terurut dari unsur V(G)terurut dari unsur V(G)


5/10

0ika0ika ee suatu sisi &edge( kemudiansuatu sisi &edge( kemudian uu dandan vv suatusuatu

titik &erte,( sedemikiantitik &erte,( sedemikian GG&&ee( ( uvuv maka e maka edikatakan menghubungkandikatakan menghubungkan uu dandan vv

se$anjutn"ase$anjutn"a uu dandan vv disebut titik ujung daridisebut titik ujung dari ee

catatancatatan


6/10

contohcontoh

11MisalkanMisalkan G &G &V(G), E(G),V(G), E(G), G G (( dimanadimana

V(G)V(G) vv11 ,v ,v22 ,v ,v33 ,v ,v44 ,v ,v55 E(G) E(G) ee11 ,e ,e22 ,e ,e33 ,e ,e44 ,e ,e55 ,e ,e6 6 ,e ,e7 7 ,e ,e88

dandan Ψ Ψ GG didefinisikan olehdidefinisikan oleh

G G (e(e11 )=v )=v11vv22 , , G G (e(e22 )=v )=v22vv33 , , G G (e(e33 )=v )=v33vv33 , , G G (e(e44 )=v )=v33vv44

G G (e(e55 )=v )=v22vv44 , , G G (e(e6 6 )=v )=v44vv55 , , G G (e(e7 7 )=v )=v22vv55 , , G G (e(e88 )=v )=v22vv55


7/10

Diagram Graf G

v4

v1

v2

v5

v3

e8

e1

e3

e6

e2

e7e5

e4

v4

v1

v2

v5

v3

e8

e1

e3

e6

e2

e7e5

e4


8/10

contohcontoh

22MisalkanMisalkan H (H (V(H), E(H),V(H), E(H), Ψ Ψ H H ))di manadi mana

V(H)V(H) ! !u, v, w, x, yu, v, w, x, y"" E(H) E(H) ! !a, b, c, d, e, f, g, ha, b, c, d, e, f, g, h""

dandan Ψ Ψ H H didefinisikan olehdidefinisikan oleh

Ψ Ψ H H (a)=uv,(a)=uv, Ψ Ψ H H (b)=uu,(b)=uu, Ψ Ψ H H (c)=vw,(c)=vw, Ψ Ψ H H (d)=wx(d)=wx

Ψ Ψ H H (e)=vx,(e)=vx, Ψ Ψ H H (f)=wx,(f)=wx, Ψ Ψ H H (g)=ux,(g)=ux, Ψ Ψ H H (h)=xy(h)=xy


9/10

Diagram Graf H

v v y y xx

uu

w w

aa

cc

bb

ee

d d

f f

gg

hh


10/10

Materi Disusi Materi Disusi Tunjukkan bahwa :Tunjukkan bahwa :

jika G graf sederhana maka jika G graf sederhana maka

≤

#

v

ε

bab1 pertemuan1

Documents