MATEMATIKA DISKRIT II ( 2 SKS)

MATEMATIKA DISKRIT II ( 2 SKS) Rabu, 18.50 – 20.20 Ruang Hard Disk

PERTEMUAN XI, XII RELASI Dosen

Lie Jasa 2006

Graf (Lanjutan) dan Pohon

1

Matematika Diskrit

Graf (lanjutan)

2006


2

1

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). 2006

2

1

1

(a)

(b)

contoh 2

3

d

a

4

3

b

5

(e)

2 (c)

4

(d)

3


5 1

4

6

1

2

3

(f)

6

7

a

b

c

d

3

e

c

4

5

e

(a) dan (b) graf semi-Euler, (c) dan (d) graf Euler , (e) dan (f) f bukan graf semi-Euler atau graf Euler 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 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 2006


4

2

Teorema-teorema • TEOREMA 6.2. Graf tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali. • TEOREMA 6.3. Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap. • (Catatlah bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya) • TEOREMA 6.4. Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajatmasuk dan derajat-keluar sama. 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 derajatmasuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar. 2006

5


Ilustrasi a b

d

c

d

c

a

b

a

b

g

f

c e

d (a)

(b)

(c)

(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

2006


6

3

Hamiltonian cycles • Traveling salesperson problem – To visit every vertex of a graph G only once by a simple cycle. – Such a cycle is called a Hamiltonian cycle. – If a connected graph G has a Hamiltonian cycle, G is called a Hamiltonian graph. 2006


7

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 semiHamilton. 2006


8

4

Ilustrasi

2006


9

Teorema • TEOREMA 6.5. Syarat cukup (jadi bukan syarat perlu) 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). • TEOREMA 6.6. Setiap graf lengkap adalah graf Hamilton. • TEOREMA 6.7. Di dalam graf lengkap G dengan n buah simpul (n ≥ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton. • TEOREMA 6.8. 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. 2006


10

5

contoh • (Persoalan pengaturan tempat duduk). 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? • Jumlah pengaturan tempat duduk yang berbeda adalah (9 - 1)/2 = 4. 2006


11

Dengan graf 9 8

1

7 2 6

Graf yang merepresentasikan persoalan pengaturan tempat duduk

3 5

2006


12

6

2006

13


45 1

50

2

10

5

40 20

3

2006

15

10

15

20

4

35 30

3


6

14

7

Beberapa Aplikasi Graf 1. • • •

•

Lintasan Terpendek (Shortest Path) graf berbobot (weighted graph), lintasan terpendek: lintasan yang memiliki total bobot minimum. Contoh aplikasi: 1. Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota 2. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer. Terdapat beberapa jenis persoalan lintasan terpendek, antara lain: 1. Lintasan terpendek antara dua buah simpul tertentu. 2. Lintasan terpendek antara semua pasangan simpul. 3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. 4. Lintasan terpendek abtara dua buah simpul yang melalui beberapa simpul tertentu. ==> Di dalam kuliah ini kita memilih jenis persoalan 3.

2006

15


Uraian Persoalan • Diberikan graf berbobot G = (V, E) dan sebuah simpul a. Tentukan lintasan terpendek dari a ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot positif. 45 1

50

2

10

5

40 20

3

2006

15

10

15

20

4

35 30

3


6

16

8

contoh 45 1

50

2

10

5

40 20

15

10

3

15

20

4

35 30

3

6

Tentukan lintasan terpendek dari simpul 1 ke semua simpul lain.

2006


2006


17

18

9

Algoritma lintasan terpendek

2006


19

Algoritma Lintasan Terpendek Dijkstra

2006


20

10

contoh

2006


2006


21

22

11

Pohon / tree • Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit

2006


23

Hutan (forest) • kumpulan pohon yang saling lepas, atau graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon.

Hutan yang terdiri dari tiga buah pohon • Pohon mempunyai bilangan kromatis = 2. 2006


24

12

Sifat-sifat Pohon • Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen: – G adalah pohon. – Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal. – G terhubung dan memiliki m = n – 1 buah sisi. – G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi. – G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit. – G terhubung dan semua sisinya adalah jembatan.

• Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

2006


25

Pohon Merentang (spanning tree) • Pohon merentang dari graf terhubung adalah upagraf merentang yang berupa pohon. • Pohon merentang diperoleh dengan memutus sirkuit di dalam graf.

2006


26

13

Aplikasi Pohon Merentang

2006


27

Pohon Rentang Minimum

2006


28

14

Algortima Prim • Langkah 1: ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T. • Langkah 2: pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T. • Langkah 3: ulangi langkah 2 sebanyak n – 2 kali. • Jumlah langkah seluruhnya di dalam algoritma Prim adalah • 1 + (n – 2) = n – 1 • yaitu sebanyak jumlah sisi di dalam pohon rentang dengan n buah simpul. 2006


29

Algoritma Prim

2006


30

15

Contoh

2006


2006


31

32

16

2006


33

Algoritma Kruskal • ( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya – dari bobot kecil ke bobot besar) • Langkah 1: T masih kosong • Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalam T. • Langkah 3: ulangi langkah 2 sebanyak n – 1 kali. 2006


34

17

Algoritma Kruskal

2006


35

Contoh

2006


36

18

2006


37

Pohon Berakar

2006


38

19

Pohon Berakar

2006


39

Terminologi pada Pohon Berakar a

b

c

e

h

d

f

i

g k

j

l

2006

m


40

20

Derajat (Degree)

2006


41

Daun (leaf)

2006


42

21

Tinggi (height) atau Kedalaman (depth)

2006


43

Pohon m-ary

2006


44

22

Pohon Biner

2006


45

Pohon Biner

2006


46

23

2006


2006


47

48

24

2006


2006


49

50

25

2006


2006


51

52

26

2006


2006


53

54

27

selesai

2006


55

28

MATEMATIKA DISKRIT II ( 2 SKS)

Recommend Documents