teori graf

112

Click here to load reader

Upload: debra

Post on 04-Jan-2016

416 views

Category:

Documents


73 download

DESCRIPTION

Teori Graf. Pendahuluan. Graf adalah suatu diagram yang memuat informasi tertentu Tujuan : sebagai visualisasi objek-objek agar lebih mudah dipahami Contoh: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik. Pendahuluan. Definisi Graf. Jenis-Jenis Graf. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Teori Graf

1

Teori Graf

Page 2: Teori Graf

Pendahuluan

Graf adalah suatu diagram yang memuat informasi tertentu

Tujuan : sebagai visualisasi objek-objek agar lebih mudah dipahami

Contoh: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik

2

Page 3: Teori Graf

3

Pendahuluan G r a f d i g u n a k a n u n t u k m e r e p r e s e n t a s i k a n o b j e k - o b j e k d i s k r i t

d a n h u b u n g a n a n t a r a o b j e k - o b j e k t e r s e b u t .

G a m b a r d i b a w a h i n i s e b u a h g r a f y a n g m e n y a t a k a n p e t a j a r i n g a n j a l a n r a y a y a n g m e n g h u b u n g k a n s e j u m l a h k o t a d i P r o v i n s i J a w a T e n g a h .

Brebes Tegal

Slawi

Pemalang

Purwokerto

Cilacap

Banjarnegara

Wonosobo

Kebumen

Purworejo

KendalSemarang

Pekalongan

Purbalingga

Magelang

Salatiga

Klaten

Solo

Purwodadi

DemakKudus

Rembang

Blora

Sukoharjo

Wonogiri

SragenBoyolali

Kroya

Temanggung

Page 4: Teori Graf

4

Sejarah Graf: masalah jembatan Königsberg (tahun 1736)

Gambar 1. Masalah Jembatan Königsberg

Graf yang merepresentasikan jembatan Königsberg:

Simpul (vertex) menyatakan daratan Sisi (edge) menyatakan jembatan

Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

C

A

B

D

Page 5: Teori Graf

5

Definisi GrafSuatu graf G terdiri dari 2 himpunan berhingga, yaitu himpunan titik-titik tidak kosong (V(G)) dan himpunan garis-garis (E(G)). Graf G = (V, E), yang dalam hal ini:

V = himpunan tidak-kosong dari simpul-simpul (vertices)

= { v1 , v2 , ... , vn } E = himpunan sisi (edges) yang menghubungkan sepasang

simpul = {e1 , e2 , ... , en }

Page 6: Teori Graf

6

G 1 G 2 G 3

G a m b a r 2 . ( a ) g r a f s e d e r h a n a , ( b ) g r a f g a n d a , d a n ( c ) g r a f s e m u

C o n t o h 1 . P a d a G a m b a r 2 , G 1 a d a l a h g r a f d e n g a n

V = { 1 , 2 , 3 , 4 } E = { ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } G 2 a d a l a h g r a f d e n g a n

V = { 1 , 2 , 3 , 4 }

E = { ( 1 , 2 ) , ( 2 , 3 ) , ( 1 , 3 ) , ( 1 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 3 , 4 ) } = { e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 }

G 3 a d a l a h g r a f d e n g a n

V = { 1 , 2 , 3 , 4 } E = { ( 1 , 2 ) , ( 2 , 3 ) , ( 1 , 3 ) , ( 1 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 3 , 4 ) , ( 3 , 3 ) } = { e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 , e 8 }

1 1 1

2 3

4

2 3

4

2

4

3

e1

e2

e3

e4

e 5

e6

e7

e 1

e 2

e3

e4

e5

e6

e7

e 8

Page 7: Teori Graf

7

G1 G2 G3

Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu

Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda/garis paralel (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop)

karena ia berawal dan berakhir pada simpul yang sama.

1 1 1

2 3

4

2 3

4

2

4

3

e1

e2

e3

e4

e5

e6

e7

e1

e2

e3

e4

e5

e6

e7

e8

Page 8: Teori Graf

8

Jenis-Jenis Graf Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu

graf, maka graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana

Page 9: Teori Graf

Jenis-jenis GrafAda dua macam graf tak sederhana:

1. graf gandagraf yang mengandung

sisi ganda 2. graf semu graf yang

mengandung gelangJumlah simpul pada graf disebut

kardinalitas graf Jumlah sisi

9

Vn Em

Page 10: Teori Graf

Berdasarkan jumlah simpul dalam graf, dapat dibedakan menjadi:

1. Graf berhingga graf dengan jumlah simpul berhingga , n

2. Graf tak berhingga graf dengan jumlah simpul tak berhingga

10

Jenis-jenis Graf

Page 11: Teori Graf

11

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.

Page 12: Teori Graf

12

(a) G4 (b) G5

Gambar 3 (a) graf berarah, (b) graf-ganda berarah

1 1

2 3

4

2 3

4

Page 13: Teori Graf

Dalam graf berarah, (vj, vk) ≠ (vk, vj) dua busur yang berbeda.Untuk busur (vj, vk), vj (simpul asal) dan vk(simpul terminal)

13

Jenis-jenis Graf

Page 14: Teori Graf

14

Tabel 1 Jenis-jenis graf [ROS99]

Jenis Sisi Sisi ganda dibolehkan?

Sisi gelang dibolehkan?

Graf sederhana Graf ganda Graf semu Graf berarah Graf-ganda berarah

Tak-berarah Tak-berarah Tak-berarah Bearah Bearah

Tidak Ya Ya Tidak Ya

Tidak Tidak Ya Ya Ya

Page 15: Teori Graf

15

Contoh Terapan Graf1. Rangkaian listrik .

(a) (b)

AB

C

DEF

AB

C

E DF

Page 16: Teori Graf

16

2. Isom er senyaw a kim ia karbon m etana (C H 4) etana (C 2H 6) propana (C 3H 8)

C

H

H

HH

Page 17: Teori Graf

17

3. Transaksi konkuren (bersamaan) pada basis data terpusat Transaksi T0 menunggu transaksi T1 dan T2 Transaksi T2 menunggu transaksi T1 Transaksi T1 menunggu transaksi T3 Transaksi T3 menunggu transaksi T2

deadlock!

T 1

T 0

T 3

T 2

Page 18: Teori Graf

18

LatihanGambarkan graf yang menggambarkan sistem pertandingan ½ kompetisi (round-robin tournaments) yang diikuti oleh 6 tim.

Page 19: Teori Graf

19

Terminologi Graf1. Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,

simpul 1 tidak bertetangga dengan simpul 4.

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

Page 20: Teori Graf

20

2. Bersisian (Incidency)

Untuk sembarang sisi e = (vj, vk) dikatakan

e bersisian dengan simpul vj , atau e bersisian dengan simpul vk Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,

sisi (2, 4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

Page 21: Teori Graf

21

3. Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Tinjau graf G3: simpul 5 adalah simpul terpencil.

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

Page 22: Teori Graf

22

4. Graf Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (Nn). Graf N5 :

1

2

3

45

Page 23: Teori Graf

23

5. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: d(v)

Tinjau graf G1: d(1) = d(4) = 2 d(2) = d(3) = 3 Tinjau graf G3: d(5) = 0 simpul terpencil

d(4) = 1 simpul anting-anting (pendant vertex) Tinjau graf G2: d(1) = 3 bersisian dengan sisi ganda

d(2) = 4 bersisian dengan sisi gelang (loop)

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

Page 24: Teori Graf

24

Pada graf berarah, din(v) = derajat-masuk (in-degree)

= jumlah busur yang masuk ke simpul v dout(v) = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v d(v) = din(v) + dout(v)

Page 25: Teori Graf

25

G 4 G 5

T in jau g ra f G 4 :

d in(1 ) = 2 ; d o u t(1 ) = 1 d in(2 ) = 2 ; d o u t(2 ) = 3

d in(3 ) = 2 ; d o u t(3 ) = 1 d in(4 ) = 1 ; d o u t(3 ) = 2

1 1

2 3

4

2 3

4

Page 26: Teori Graf

26

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

L e m m a J a b a t T a n g a n . J u m l a h d e r a j a t s e m u a s i m p u l p a d a s u a t u g r a f a d a l a h g e n a p , y a i t u d u a k a l i j u m l a h s i s i p a d a g r a f t e r s e b u t . D e n g a n k a t a l a i n , j i k a G = ( V , E ) , m a k a Evd

Vv

2)(

T i n j a u g r a f G 1 : d ( 1 ) + d ( 2 ) + d ( 3 ) + d ( 4 ) = 2 + 3 + 3 + 2 = 1 0

= 2 j u m l a h s i s i = 2 5

T i n j a u g r a f G 2 : d ( 1 ) + d ( 2 ) + d ( 3 ) = 3 + 3 + 4 = 1 0 = 2 j u m l a h s i s i = 2 5

T i n j a u g r a f G 3 : d ( 1 ) + d ( 2 ) + d ( 3 ) + d ( 4 ) + d ( 5 )

= 2 + 2 + 3 + 1 + 0 = 8 = 2 j u m l a h s i s i = 2 4

Page 27: Teori Graf

27

Akibat dari lemma (corollary):

Teorema: Untuk sembarang graf G, banyaknya simpul berderajat ganjil selalu genap.

Page 28: Teori Graf

28

Contoh 2. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah: (a) 2, 3, 1, 1, 2 (b) 2, 3, 3, 4, 4 Penyelesaian: (a) tidak dapat, karena jumlah derajat semua simpulnya ganjil

(2 + 3 + 1 + 1 + 2 = 9). (b) dapat, karena jumlah derajat semua simpulnya genap (2 + 3 + 3 + 4 + 4 = 16).

Page 29: Teori Graf

29

LatihanMungkinkah dibuat graf-sederhana 5 simpul dengan derajat masing-masing simpul adalah:(a) 5, 2, 3, 2, 4(b) 4, 4, 3, 2, 3(c) 3, 3, 2, 3, 2(d) 4, 4, 1, 3, 2Jika mungkin, berikan satu contohnya, jika tidak mungkin, berikan alasan singkat.

Page 30: Teori Graf

30

Jawaban:(a) 5, 2, 3, 2, 4: Tidak mungkin, karena ada

simpul berderajat 5(b) 4, 4, 3, 2, 3: Mungkin [contoh banyak](c) 3, 3, 2, 3, 2: Tidak mungkin, karena

jumlah simpul berderajat ganjil ada 3 buah (alasan lain, karena jumlah derajat ganjil)

(d) 4, 4, 1, 3, 2: Tidak mungkin, karena simpul-1 dan simpul-2 harus bertetangga dengan simpul sisanya, berarti simpul-3 minimal berderajat 2 (kontradiksi dengan simpul-3 berderajat 1)

Page 31: Teori Graf

31

6. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.

Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3.

G1 G2 G3 1

3 2

4

1

2 3

4

5

1

2

e 1

e 2 e

3

e 4

e 5 3

Page 32: Teori Graf

32

7. Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit. Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.

G1 G2 G3

1

32

4

1

23

4

5

1

2

e 1

e 2 e 3

e 4

e 53

Page 33: Teori Graf

Sirkuit Euler

Misal G suatu graf, Sirkuit Euler adalah sirkuit dimana setiap titik dalam G paling sedikit muncul sekali dan setiap garis dalam G muncul tepat satu kali.

33

Page 34: Teori Graf

34

8 . T e r h u b u n g (C o n n e c te d )

D u a b u a h s im p u l v 1 d a n s im p u l v 2 d ise b u t te r h u b u n g jik a te rd a p a t lin ta sa n d a ri v 1 k e v 2 .

G d ise b u t g r a f te r h u b u n g (c o n n e c te d g ra p h ) jik a u n tu k se tia p p a sa n g s im p u l v i d a n v j d a la m h im p u n a n V te rd a p a t lin ta sa n d a ri v i k e v j.

J ik a tid a k , m a k a G d ise b u t g r a f ta k -te r h u b u n g (d isc o n n e c te d g ra p h ) . C o n to h g ra f ta k -te rh u b u n g :

1

2

3

4

5

6

78

Page 35: Teori Graf

35

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung

kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf

tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Page 36: Teori Graf

Theorema

Misalkan G adalah graf terhubung.

G adalah sirkuit Euler bila dan hanya bila

semua titik dalam G mempunyai derajat

genap.

Kontraposisi:

Jika ada titik dalam G yang berderajat ganjil, maka G bukan sirkuit Euler.

36

Page 37: Teori Graf

SIRKUIT HAMILTON

Suatu graf terhubung G disebut Sirkuit Hamilton jika ada sirkuit yang mengunjungi setiap titiknya tepat satu kali (kecuali titik awal yang sama dengan titik akhirnya)

Perbedaan sirkuit Euler dan Hamilton:

Sirkuit Euler: semua garis harus dilalui tepat satu kali, sementara semua titiknya boleh dikunjungi lebih dari satu kali.

Sirkuit Hamilton: semua titik dikunjungi tepat satu kali dan tidak harus melalui semua garisnya.

37

Page 38: Teori Graf

38

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang sim pul sem barang u dan v di G , terhubung kuat. Kalau tidak, G disebut graf terhubung lem ah .

graf berarah terhubung lemah graf berarah terhubung kuat

1

2

3 4

1

2 3

Page 39: Teori Graf

SUBGRAF DAN KOMPLEMEN

Subgraf

Misalkan G = (V, E) adalah sebuah graf.

G1 = (V1, E1) adalah subgraph dari G jika V1 V

dan E1 E.

Setiap garis dalam H mempunyai titik ujung yang sama dengan garis tersebut dalam G.

Beberapa hal yang dapat diturunkan dari definisi:

a. Sebuah titik dalam G merupakan subgraf G

b. Sebuah garis dalam G bersama-sama titik

ujungnya merupakan subgraf G

39

Page 40: Teori Graf

c. Setiap graf merupakan subgraf dari dirinya

sendiri.

d. Dalam subgraf berlaku sifat transitif : jika H

adalah subgraf G dan G subgraf K, maka H

adalah subgraf dari K

Contoh (202/204)

40

Page 41: Teori Graf

41

Komplemen dari subgraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya. Notasi komplemen dari suatu graf G G

(a) Graf G1 (b) Sebuah subgraf (c) komplemen dari subgraf (b)

1

2

3

4 5

6

1

6

5

31

2

3

52

Page 42: Teori Graf

Titik-titik dalam G sama dengan titik-titik dalam G

Garis-garis dalam G adalah garis-garis yang tidak berada dalam G

Komplemen dari suatu graf lengkap Kn adalah suatu graf dengan n titik tanpa garis

Contoh

Misalkan G suatu graf dengan n buah titik dan k garis. Berapa banyak garis dalam G ?

42

Page 43: Teori Graf

43

Komponen graf (connected component) adalah jumlah maksimum subgraf terhubung dalam graf G. Graf G di bawah ini mempunyai 4 buah komponen.

1

2 3 4

5

6 7

8

9

10

11

12

13

Page 44: Teori Graf

44

P a d a g r a f b e r a r a h , k o m p o n e n t e r h u b u n g k u a t ( s t r o n g ly c o n n e c te d c o m p o n e n t ) a d a l a h ju m la h m a k s im u m u p a g r a f y a n g t e r h u b u n g k u a t . G r a f d i b a w a h in i m e m p u n y a i 2 b u a h k o m p o n e n t e r h u b u n g k u a t :

2 3

4

5

16

Page 45: Teori Graf

45

9. Subgraf Rentang (Spanning Subgraph)

Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan subgraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).

(a) graf G, (b) subgraf rentang dari G, (c) bukan subgraf rentang dari G

1

2 3

4 5

1

2 3

4 5

1

2 3

Page 46: Teori Graf

46

1 0 . C u t - S e t

C u t - s e t d a r i g r a f t e r h u b u n g G a d a l a h h i m p u n a n s i s i y a n g b i l a d i b u a n g d a r i G m e n y e b a b k a n G t i d a k t e r h u b u n g . J a d i , c u t - s e t s e l a l u m e n g h a s i l k a n d u a b u a h k o m p o n e n .

P a d a g r a f d i b a w a h , { ( 1 , 2 ) , ( 1 , 5 ) , ( 3 , 5 ) , ( 3 , 4 ) } a d a l a h c u t - s e t . T e r d a p a t b a n y a k c u t - s e t p a d a s e b u a h g r a f t e r h u b u n g . H i m p u n a n { ( 1 , 2 ) , ( 2 , 5 ) } j u g a a d a l a h c u t - s e t , { ( 1 , 3 ) , ( 1 , 5 ) , ( 1 , 2 ) } a d a l a h c u t - s e t , { ( 2 , 6 ) } j u g a c u t - s e t , t e t a p i { ( 1 , 2 ) , ( 2 , 5 ) , ( 4 , 5 ) } b u k a n c u t - s e t s e b a b h i m p u n a n b a g i a n n y a , { ( 1 , 2 ) , ( 2 , 5 ) } a d a l a h c u t - s e t .

( a ) ( b )

1

3 4

5

2

6

21

3

5

4

6

Page 47: Teori Graf

47

11. Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

a

b

cd

e

10 12

8

15 911

14

Page 48: Teori Graf

48

Beberapa Graf Khusus

a . G r a f L e n g k a p ( C o m p l e t e G r a p h )

G r a f l e n g k a p i a l a h g r a f s e d e r h a n a y a n g s e t i a p s i m p u l n y a m e m p u n y a i s i s i k e s e m u a s i m p u l l a i n n y a . G r a f l e n g k a p d e n g a n n b u a h s i m p u l d i l a m b a n g k a n d e n g a n K n . J u m l a h s i s i p a d a g r a f l e n g k a p y a n g t e r d i r i d a r i n b u a h s i m p u l a d a l a h n ( n – 1 ) / 2 .

K 1 K 2 K 3 K 4 K 5 K 6

Page 49: Teori Graf

49

b . G r a f L i n g k a r a n

G r a f l i n g k a r a n a d a l a h g r a f s e d e r h a n a y a n g s e t i a p s i m p u l n y a b e r d e r a j a t d u a . G r a f l i n g k a r a n d e n g a n n s i m p u l d i l a m b a n g k a n d e n g a n C n .

Page 50: Teori Graf

50

c. Graf Teratur (Regular Graphs)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r.

Jumlah sisi pada graf teratur adalah nr/2.

Page 51: Teori Graf

51

LatihanBerapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 16 buah sisi dan tiap simpul berderajat sama dan tiap simpul berderajat ≥ 4 ?

Page 52: Teori Graf

52

Jawaban: Tiap simpul berderajat sama -> graf teratur.Jumlah sisi pada graf teratur berderajat r adalah e = nr/2. Jadi, n = 2e/r = (2)(16)/r = 32/r.Untuk r = 4, jumlah simpul yang dapat dibuat adalah maksimum, yaitu n = 32/4 = 8.Untuk r yang lain (r > 4 dan r merupakan pembagi bilangan bulat dari 32):r = 8 -> n = 32/8 = 4 -> tidak mungkin membuat graf sederhana.r = 16 -> n = 32/16 = 2 -> tidak mungkin membuat graf sederhana.Jadi, jumlah simpul yang dapat dibuat adalah 8 buah (maksimum dan minimum).

Page 53: Teori Graf

53

d. Graf Bipartite (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2).

V1 V2

Page 54: Teori Graf

Apabila dalam Graf Bipartit, setiap titik dalam V1 berhubungan dengan setiap titik dalam V2, maka graf disebut Graf Bipartite lengkap.

Jika V1 terdiri dari m titik, V2 terdiri dari n titik, maka notasi Graf Bipartite lengkapnya = K m,n

54

Page 55: Teori Graf

55

Graf G di bawah ini adalah graf bipartit, karena simpul-simpulnya dapat dibagi menjadi V1 = {a, b, d} dan V2 = {c, e, f, g}

G

graf persoalan utilitas (K3,3), topologi bintang

H 2 H 3

W G E

H 1

a b

c

de

f

g

Page 56: Teori Graf

Representasi Graf dalam Matriks

Matriks dapat digunakan untuk menyatakan graf. perhitungan dapat dilakukan dengan mudah.

Kesulitan merepresentasikan graf dalam matriks adalah keterbatasan matriks untuk mencakup semua informasi yang ada dalam graf.

Akibatnya, ada berbagai macam matriks untuk menyatakan suatu graf tertentu

Tiap graf mempunyai keuntungan berbeda dalam menyaring informasi yang dibutuhkan pada graf.

56

Page 57: Teori Graf

Representasi Graf dalam matriks

57

1. Matriks Ketetanggaan (adjacency matrix)

Menyatakan graf dengan cara menyatakannya dalam jumlah garis yang menghubungkan titik-titiknya. Jumlah baris (dan kolom) matriks ketetanggaan sama dengan jumlah titik dalam graf. Definisi Misalkan G adalah graf tak berarah dengan titik-titik V1,V2,...,Vn (n berhingga). Matriks ketetanggaan yang sesuai dengan graf G adalah matriks A = (aij) dengan aij = jumlah garis yang menghubungkan titik Vi dengan Vj

A = [aij], 1 , jika simpul i dan j bertetangga(/grs) aij = { 0, jika simpul i dan j tidak bertetangga Matriks ketetanggan merupakan matriks simetris.

Page 58: Teori Graf

58

C o n to h :

4321 54321 4321

4

3

2

1

0110

1011

1101

0110

00000

00100

01011

00101

00110

5

4

3

2

1

4

3

2

1

0110

0001

1101

0010

(a ) (b ) (c )

4321

4

3

2

1

0210

2112

1101

0210

1

32

4

1

23

4

5

1

2 3

4

1

2

4

3

e1

e2

e3

e4

e5

e6

e7

e8

Page 59: Teori Graf

59

Derajat tiap simpul i: (a) Untuk graf tak-berarah

d(vi) =

n

jija

1

(b) Untuk graf berarah,

din (vj) = jumlah nilai pada kolom j =

n

iija

1

dout (vi) = jumlah nilai pada baris i =

n

jija

1

Page 60: Teori Graf

Beberapa hal yang menjadi catatan dalam merepresentasikan graf dalam matrik ketetanggaan:•Graf tidak mempunyai loop jika dan hanya jika semua elemen diagonal utamanya =0. Loop pada Vi bersesuaian dengan aii = 1

•Matriks ketetanggaan dapat dipakai untuk mendeteksi graf yang tidak terhubung secara mudah.•Derajat titik Vi = jumlah semua komponen matriks baris/kolom ke-I

derajat graf G = jumlah semua komponen matriks =

60

n

iij

n

jiji aavd

11

)(

i j

ija

Page 61: Teori Graf

• Graf G adalah graf Bipartite (Km,n) jika dan hanya jika matriks ketetanggaannya berbentuk

Dengan O= matriks 0

1m = matriks m x n semua elemen = 1

1n = matriks n x m semua elemen = 1

• G graf lengkap jika dan hanya jika semua elemen dalam diagonal utama = 0, semua elemen di luar diagonal utama = 1.

61

O

O

n

m

1

1

Page 62: Teori Graf

62

a b c d e

15810

151411

149

811912

1012

e

d

c

b

a

a

b

cd

e

10 12

8

15 911

14

Matrik ketetanggaan u/ graf berbobot

Page 63: Teori Graf

Matriks ketetanggaan dapat dipakai untuk menghitung banyaknya kemungkinan path dengan panjang tertentu antara 2 titik.

Misalkan A = (aij) matriks ketetanggaan graf G.

An = A x A x A … A (sebanyak n kali)

Banyaknya kemungkinan path dengan panjang n dari titik

Vi ke Vj adalah elemen aij pada matriks An (=aijn)

Contoh hal (237)

63

Page 64: Teori Graf

64

2. Matriks Biner (incidency matrix)

Misalkan G adalah graf tanpa loop dengan n titik V1, V2, …,Vn dan k garis e1, e2, … ek. Matriks yang sesuai adalah matriks berukuran n x k yang elemennya adalah:

A = [aij], 1, jika simpul i bersisian dengan sisi j aij = { 0, jika simpul i tidak bersisian dengan sisi j

e1 e2 e3 e4 e5

4

3

2

1

10000

11100

00111

01011

Derajat titik Vi = jumlah semua elemen pada baris ke-I Derajat total = jumlah semua elemen dari matriks

1

e 1 2

3

4

e 2 e 3 e 4

e 5

Page 65: Teori Graf

Catatan:

1. Matriks biner dapat dipakai untuk menyatakan graf secara tepat.

2. Setiap garis berhubungan denagn 2titik. Maka dalam matriks biner, setiap kolom mempunyai tepat 2 elemen 1, sisanya elemen 0

3. Jumlah elemen pada baris ke-i= derajat titik Vi. Derajat total graf G= jumlah semua elemen matriks

4. Jika semua elemen pada beris ke-i = 0, maka titik Vi adalah titik terasing

5. Dua kolom yang semua elemennya sama menyatakan garis yang paralel

65

Page 66: Teori Graf

Matriks Sirkuit

Misalkan G graf yang memuat q buah sirkuit sederhana dan e buah garis.

Matriks sirkuit A = (aij) yang bersesuaian adalah

matriks yang terdiri dari q baris dan e kolom

dengan elemen sbb:

66

A = [aij],   1, jika sirkuit ke- i memuat garis ke- j

aij = { 0, jika sirkuit ke- i tidak memuat garis ke- j

Page 67: Teori Graf

67

Graf Isomorfik

Diketahui matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak berarah. Gambarkan dua buah graf yang yang bersesuaian dengan matriks tersebut.

01011

10110

01110

11101

10010

Page 68: Teori Graf

68

Jawaban:

Dua buah graf yang sama (hanya penggambaran secara geometri berbeda) isomorfik!

1

1

2 3

345

5 4

2

Page 69: Teori Graf

69

Graf Isomorfik Dua buah graf yang sama tetapi secara geometri berbeda disebut graf

yang saling isomorfik.

Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat

korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1,

maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.

Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan

simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat digambarkan dalam banyak cara.

Page 70: Teori Graf

70

( a ) G 1 (b ) G 2 ( c ) G 3

G a m b a r 6 .3 5 G 1 is o m o rf ik d e n g a n G 2 , te ta p i G 1 t id a k is o m o rf ik d e n g a n G 3

3

4

1 2

d c

a b

v w

x y

Page 71: Teori Graf

71

(a) G1 (b) G2

Gambar 6.36 Graf (a) dan graf (b) isomorfik edcba zvwyx

AG1 =

e

d

c

b

a

01000

10101

01011

00101

01110

AG2 =

z

v

w

y

x

01000

10101

01011

00101

01110

z

d

c

a

b

e

x

v w

y

Page 72: Teori Graf

72

( a )

( b )

G a m b a r 6 . 3 8 ( a ) D u a b u a h g r a f i s o m o r f i k , ( b ) t i g a b u a h g r a f i s o m o r f i k

Page 73: Teori Graf

73

D a r i d e f i n i s i g r a f i s o m o r f i k d a p a t d i k e m u k a k a n b a h w a d u a b u a h g r a f i s o m o r f i k m e m e n u h i k e t i g a s y a r a t b e r i k u t [ D E O 7 4 ] : 1 . M e m p u n y a i j u m l a h s i m p u l y a n g s a m a . 2 . M e m p u n y a i j u m l a h s i s i y a n g s a m a 3 . M e m p u n y a i j u m l a h s i m p u l y a n g s a m a b e r d e r a j a t t e r t e n t u

N a m u n , k e t i g a s y a r a t i n i t e r n y a t a b e l u m c u k u p m e n j a m i n . P e m e r i k s a a n s e c a r a v i s u a l p e r l u d i l a k u k a n .

( a ) ( b )

x

u

v

w

y

Page 74: Teori Graf

74

LatihanApakah pasangan graf di bawah ini isomorfik?

a

b

c

d

e

f

g

h u

v

w

t

p

q

r

s

Page 75: Teori Graf

75

LatihanApakah pasangan graf di bawah ini isomorfik?

a b

cd

e f

p q

rs

tu

Page 76: Teori Graf

76

LatihanGambarkan 2 buah graf yang isomorfik dengan graf teratur berderajat 3 yang mempunyai 8 buah simpul

Page 77: Teori Graf

77

Jawaban:

Page 78: Teori Graf

78

Graf Planar (Planar Graph) dan Graf Bidang (Plane

Graph)Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar, jika tidak, maka ia disebut graf tak-planar. K4 adalah graf planar:

Page 79: Teori Graf

79

K5 adalah graf tidak planar:

Page 80: Teori Graf

80

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

(a) (b) (c)

Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang

Page 81: Teori Graf

81

Persoalan utilitas (utility problem)

(a) (b)

(a) Graf persoalan utilitas (K3,3), (b) graf persoalan utilitas bukan graf planar.

H 2 H 3

W G E

H 2 H 3

W G E

H 1H 1

Aplikasi Graf Planar

Page 82: Teori Graf

82

Aplikasi Graf Planar

Perancangan IC (Integrated Circuit)

Tidak boleh ada kawat-kawat di dalam IC-board yang saling bersilangan dapat menimbulkan interferensi arus listrik malfunction

Perancangan kawat memenuhi prinsip graf planar

Page 83: Teori Graf

83

LatihanGambarkan graf (kiri) di bawah ini sehingga tidak ada sisi-sisi yang berpotongan (menjadi graf bidang).

Page 84: Teori Graf

84

LatihanSolusi: graf yang kanan

Page 85: Teori Graf

85

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face).

Graf bidang pada gambar di bawah initerdiri atas 6 wilayah (termasuk wilayah terluar):

R1

R2

R3

R5

R4

R6

Page 86: Teori Graf

86

Hubungan antara jumlah simpul (n), jumlah sisi (e), dan jumlah wilayah (f) pada graf bidang:

n – e + f = 2 (Rumus Euler)

Pada Gambar di atas, e = 11 dan n = 7, f = 6, maka 11 – 7 + 6 = 2.

R1

R2

R3

R 5

R4

R6

Page 87: Teori Graf

87

LatihanMisalkan graf sederhana planar memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk?

Page 88: Teori Graf

88

Jawaban:Diketahui n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 4 = 96.

Menurut lemma jabat tangan, jumlah derajat = 2 jumlah sisi,

sehinggajumlah sisi = e = jumlah derajat/2 =

96/2 = 48

Dari rumus Euler, n – e + f = 2, sehingga f = 2 – n + e = 2 – 24 + 48 = 26 buah.

Page 89: Teori Graf

89

Pada graf planar sederhana terhubung dengan f buah wilayah, n buah simpul, dan e buah sisi (e > 2) selalu berlaku:

e 3n – 6

Ketidaksamaan yang terakhir dinamakan ketidaksamaan Euler,

yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana

kalau graf planar, maka ia memenuhi ketidaksamaan Euler, sebaliknya jika tidak planar maka ketidaksamaan tersebut tidak dipenuhi.

Page 90: Teori Graf

90

Contoh: Pada K4, n = 4, e = 6, memenuhi ketidaksamaan Euler, sebab

6 3(4) – 6. Jadi, K4 adalah graf planar.

Pada graf K5, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab

10 3(5) – 6. Jadi, K5 tidak planar

K4 K5 K3,3

Page 91: Teori Graf

91

Ketidaksamaan e 3n – 6 tidak berlaku untuk K3,3

karena e = 9, n = 6 9 (3)(6) – 6 = 12 (jadi, e 3n – 6) padahal graf K3,3 bukan graf planar! Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit empat buah sisi, Dari penurunan rumus diperoleh e 2n - 4

Page 92: Teori Graf

92

Contoh Graf K3,3 pada Gambar di bawah memenuhi ketidaksamaan e 2n – 4, karena e = 9, n = 6 9 (2)(6) – 4 = 8 (salah) yang berarti K3,3 bukan graf planar.

H 2 H 3

W G E

H 2 H 3

W G E

H 1H 1

Page 93: Teori Graf

93

Teorema Kuratoswki Berguna untuk menentukan dengan tegas keplanaran suat graf.

(a) (b) (c)

Gambar (a) Graf Kuratowski pertama (K5) (b) Graf Kuratowski kedua (K3, 3) (c) Graf yang isomorfik dengan graf Kuratowski kedua

Page 94: Teori Graf

94

Sifat graf Kuratowski adalah: 1. Kedua graf Kuratowski adalah graf teratur. 2. Kedua graf Kuratowski adalah graf tidak-planar 3. Penghapusan sisi atau simpul dari graf Kuratowski

menyebabkannya menjadi graf planar. 4. Graf Kuratowski pertama adalah graf tidak-planar

dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.

Page 95: Teori Graf

95

TEOREMA Kuratowski. Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

G1 G2 G3

Gambar Tiga buah graf yang homemorfik satu sama lain.

v

x

y

Page 96: Teori Graf

96

Contoh: Kita gunakan Teorema Kuratowski untuk memeriksa keplanaran graf. Graf G di bawah ini bukan graf planar karena ia mengandung upagraf (G1) yang sama dengan K3,3.

Graf G tidak planar karena ia mengandung upagraf yang sama dengan K3,3.

a bc

def

a bc

def

GG 1

Page 97: Teori Graf

97

Graf G tidak planar karena ia mengandung upagraf (G1) yang homeomorfik dengan K5 (dengan membuang simpul-simpul yang berderajat 2 dari G1, diperoleh K5).

G G1 K5

Gambar Graf G, upagraf G1 dari G yang homeomorfik dengan K5.

a

b

c

d

efg

h

a

b

c

d

efg

h

ii

a

c

eg

h

Page 98: Teori Graf

98

LatihanPerlihatkan dengan teorema Kuratowski bahwa graf Petersen tidak planar.

Page 99: Teori Graf

99

Jawaban: 1

2

3

4

5

6 7

89

1 0

1

2

3

4

5

6 7

89

1

2

3

4

5

6

(a) G ra f P eter se n , G (b ) G1

(c) G2

(d ) K3 ,3

1

2 4 6

3 5

Gambar (a) Graf Petersen (b) G1 adalah upagraf dari G (c) G2 homeomorfik dengan

G1 (d) G2 isomorfik dengan

K3,3

Page 100: Teori Graf

100

Lintasan dan Sirkuit Euler

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu

kali..

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

Page 101: Teori Graf

101

Contoh. Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1 Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3, 5 Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1 Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler

(a) dan (b) graf semi-Euler (c) dan (d) graf Euler (e) dan (f) bukan graf semi-Euler atau graf Euler

12

3 4

1 2

34

5 6

1

2 3

45

6 7

a

b

e

d

c

f

ba

c d

1 2

3

4 5 e

(a) (b) (c)

(d) (e) (f)

Page 102: Teori Graf

102

TEOREMA. Graf tidak berarah memiliki lintasan Euler (graf semi-Euler) jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

TEOREMA. Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.

Page 103: Teori Graf

103

TEOREMA. (a) Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama. (b) G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

Gambar (a) Graf berarah Euler (a, g, c, b, g, e, d, f, a) (b) Graf berarah semi-Euler (d, a, b, d, c, b) (c) Graf berarah bukan Euler maupun semi-Euler

a

b

c

de

fg

a b

cd

a b

cd

(a) (b) (c)

Page 104: Teori Graf

104

LatihanManakah di antara graf di bawah ini yang dapat dilukis tanpa mengangkat pensil sekalipun?

Page 105: Teori Graf

105

Lintasan dan Sirkuit Hamilton

Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.

Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf

tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton,

sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

Page 106: Teori Graf

106

(a) (b) (c)

(a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4) (b) graf yang memiliki sirkuit Hamilton (1, 2, 3, 4, 1) (c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton

1 2

34

1

3

2

4

1 2

34

Page 107: Teori Graf

107

(a) (b)

(a) Dodecahedron Hamilton, (b) graf yang mengandung sirkuit Hamilton

Page 108: Teori Graf

108

TEOREMA. Syarat cukup supaya graf sederhana G dengan n ( 3) buah simpul adalah graf Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) n/2 untuk setiap simpul v di G). (coba nyatakan dalam “jika p maka q”)

TEOREMA. Setiap graf lengkap adalah graf Hamilton.

TEOREMA. Di dalam graf lengkap G dengan n buah simpul (n 3), terdapat (n – 1)!/2 buah sirkuit Hamilton.

Page 109: Teori Graf

109

TEOREMA. Di dalam graf lengkap G dengan n buah simpul (n 3 dan n ganjil), terdapat (n – 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n 4, maka di dalam G terdapat (n – 2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh. Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan? Jawaban: Jumlah pengaturan tempat duduk yang berbeda adalah (9 – 1)/2 = 4.

Gambar Graf yang merepresentasikan persoalan pengaturan tempat duduk.

1

2

3

5

6

7

8

9

Page 110: Teori Graf

110

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, dan sebagainya..

(a) (b)

(a) Graf Hamilton sekaligus graf Euler (b) Graf Hamilton sekaligus graf semi-Euler

6

5

4

1

3

2

5

1 2

34

Page 111: Teori Graf

111

LatihanGambar di bawah ini adalah denah lantai dasar sebuah gedung. Apakah dimungkinkan berjalan melalui setiap pintu di lantai itu hanya satu kali saja jika kita boleh mulai memasuki pintu yang mana saja?

Page 112: Teori Graf

112

Jawaban:Nyatakan ruangan sebagai simpul dan pintu antar ruangan sebagai sisi.Setiap pintu hanya boleh dilewati sekali (tidak harus kembali ke titik asal) melewati sisi tepat sekali lintasan EulerDi dalam graf tersebut ada 2 simpul berderajat ganjil (simpul 1 dan 6), selebihnya genap pasti ada lintasan EulerKesimpulan: setiap pintu dapat dilewati sekali saja

1 2 3

45 6

7