modul 5 teori graf

57
Oleh: Bandung Arry Sanjoyo 1 1 Modul 5 TEORI GRAF Pendahuluan Permasalahan yang muncul di dunia nyata sering terkait dengan objek diskrit dan relasi antar objek tersebut. Sebagai contoh: ada beberapa kota dalam suatu propinsi, dan ada jalan yang menghubungkan dar suatu kota ke kota lain. Hal ini kota merupakan objek diskrit, sedangkan jalan merelasikan antar satu objek ke objek lainnya. Contoh lainnya, dalam sistem jaringan komputer terdiri dari objek-objek computer baik sebagai server maupun workstation. Disini kita bisa mencari apakah satu komputer dapat terhubung ke komputer lainnya. Permasalahan-permasalahan seperti ini dapat dimodelkan secara baik dengan menggunakan konsep, graf, graf berarah, pohon, maupun pohon biner. Dalam bab ini kita akan membahas tentang konsep dasar graf, contoh-contoh pemakaian dalam kehidupan sehari-hari, dan bagaimana mengimplementasikan graf dalam pemrograman komputer. Tujuan Instruksional Umum Mahasiswa mengerti konsep graf, macam-macam graf, dan dapat menerapkan dalam kehidupan sehari-hari. Tujuan Instruksional Khusus Mahasiswa diharapkan dapat: 1. Memahami definisi graf tak berarah dan graf berarah, dan dapat mengaitkannya dalam permasalahan sehari-hari. 2. Memahami pengertian lintasan dan sirkuit dalam graf tak berarah dan graf berarah. 3. Memahami pengertian Sikuit Euler Dan Hamilton dan penerapannya. 4. Mampu menyelesaikan Permasalahan Perjalanan Penjual. 5. Memahami definisi dan dapat mengenali Graf Isomophic.

Upload: hostkit

Post on 08-Aug-2015

186 views

Category:

Documents


13 download

TRANSCRIPT

Page 1: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 1

1 Modul 5 TEORI GRAF

Pendahuluan

Permasalahan yang muncul di dunia nyata sering terkait dengan objek diskrit dan relasi antar

objek tersebut. Sebagai contoh: ada beberapa kota dalam suatu propinsi, dan ada jalan yang

menghubungkan dar suatu kota ke kota lain. Hal ini kota merupakan objek diskrit, sedangkan

jalan merelasikan antar satu objek ke objek lainnya. Contoh lainnya, dalam sistem jaringan

komputer terdiri dari objek-objek computer baik sebagai server maupun workstation. Disini kita

bisa mencari apakah satu komputer dapat terhubung ke komputer lainnya.

Permasalahan-permasalahan seperti ini dapat dimodelkan secara baik dengan menggunakan

konsep, graf, graf berarah, pohon, maupun pohon biner. Dalam bab ini kita akan membahas

tentang konsep dasar graf, contoh-contoh pemakaian dalam kehidupan sehari-hari, dan

bagaimana mengimplementasikan graf dalam pemrograman komputer.

Tujuan Instruksional Umum

Mahasiswa mengerti konsep graf, macam-macam graf, dan dapat menerapkan dalam kehidupan

sehari-hari.

Tujuan Instruksional Khusus

Mahasiswa diharapkan dapat:

1. Memahami definisi graf tak berarah dan graf berarah, dan dapat mengaitkannya dalam

permasalahan sehari-hari.

2. Memahami pengertian lintasan dan sirkuit dalam graf tak berarah dan graf berarah.

3. Memahami pengertian Sikuit Euler Dan Hamilton dan penerapannya.

4. Mampu menyelesaikan Permasalahan Perjalanan Penjual.

5. Memahami definisi dan dapat mengenali Graf Isomophic.

Page 2: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 2

6. Memhami penertian Graf Planar dan dapat mengaitkannya dalam permasalahan sehari-

hari.

7. Dapat merepresentasikan Graf Dalam Program Komputer

Page 3: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 3

5.1 Kegiatan Belajar I:

Definisi Graf Tak Berarah Dan Graf Berarah

Suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung

oleh edge-edge (atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik

(melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan edge). Secara

fataumal, definisi dari graf sebagaimana yang terlihat pada definisi dibawah ini.

Definisi 5.1.1. Suatu graf tak berarah (Undirected graf) G adalah suatu pasangan terurut (V,

E) dengan V merupakan himpunan verteks (node) dan E adalah himpunan dari multiset yang

terdiri dari dua elemen di V, elemen dari E dinamakan edge atau arc. Graf tak berarah ini

biasa disimbolkan dengan G=(V,E).

Himpunan verteks V biasa dituliskan dengan },...,,{ 21 nvvvV , dalam hal ini V mempunyai n

buah elemen yaitu nvdanvv ,...,, 21 . Begitu juga himpunan E biasa dituliskan juga dengan

},...,,{ 21 meeeE dimana jkkji evve },{ .

Verteks u dan v dikatakan adjacent jika ada sebuah edge e = {u, v }. Dalam hal ini, verteks u

dan v disebut titik ujung dari e, dan e dikatakan menghubungkan verteks u dan v. Atau edge e

dikatakan incident dengan vertek u dan v.

Untuk bisa memahami definisi graf tak berarah diatas, akan diberikan beberapa contoh berikut

ini.

Contoh 5.1.1:

G=({a, b, c, d}, {{a,b}, {a,d}, {b,b}, {b,c}, {c,d}}) merupakan graf tak berarah. Pada graf G

ini mempunyai himpunan verteks V={a, b, c, d}, jadi himpunan V terdiri dari verteks – verteks

a, b, c, dan d. Sedangkan himpunan edge E adalah {{a,b}, {a,d}, {b,b}, {b,c}, {c,d}}, terlihat

bahwa setiap elemen dari E merupakan multiset yang terdiri dari dua verteks di V. Jadi sesuai

dengan definisi diatas G merupakan graf tak berarah. Verteks a dan b dikatakan adjacent karena

ada edge {a,b} yang menghubungkan antara verteks a dan b.

Page 4: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 4

Penggambaran Graf Tak Berarah

Suatu graf tak berarah G=(V,E) dapat dinyatakan dalam bentuk gambar dengan aturan

penggambaran sebagai berikut:

1. Untuk setiap verteks Vvi digambarkan dengan lingkaran kecil atau titik berlabel vi.

2. Untuk setiap edge },{atau jiijij vveEe digambarkan dengan garis yang

menghubungkan dari verteks vi ke verteks vj .

Contoh 5.1.2:

Untuk graf tak berarah pada Contoh 5.1.1. dapat dinyatakan dalam bentuk Gambar 5.1.1 (a)

atau Gambar 5.1.1. (b).

a b

d c

a b

cd

(a) (b)

Gambar 5.1.1.

Contoh 5.1.3:

Graf tak berarah pada Gambar 5.1.2. merupakan graf dengan verteks adalah sub-sub program

p1, p2, p3, p4, dan p5. Dan edge {pi, pj} menyatakan dua sub program pi dan pj yang

menggunakan data yang bersama.

p1

p2p3

p4p5

Gambar 5.1.2.

Page 5: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 5

Definisi 5.1.2. Suatu graf berarah (Directed graf) G adalah suatu pasangan terurut (V, E)

dengan V merupakan himpunan verteks (node) dan E adalah relasi biner pada V atau E:V→V.

Elemen dari E dinamakan edge atau arc (busur). Graf berarah ini biasa disimbolkan dengan

G=(V,E).

Sebagaimana pada graf tak berarah, himpunan verteks V biasa dituliskan dengan

},...,,{ 21 nvvvV , dalam hal ini V mempunyai n buah elemen yaitu nvdanvv ,...,, 21 . Begitu

juga himpunan E biasa dituliskan juga dengan },...,,{ 21 meeeE dimana

),( kji vve merupakan pasangan terurut verteks. Ingat bahwa ),(),( jkkj vvvv .

Verteks u dan v dikatakan adjacent jika ada sebuah edge e = (u, v) atau e = (v, u). Dalam hal e =

(u, v), verteks u disebut verteks awal dari e dan verteks v disebut verteks akhir dari e, dan e

dikatakan menghubungkan dari (incident from) verteks u dan menghubungkan ke (incedent

to) verteks v.

Untuk bisa memahami definisi graf tak berarah diatas, akan diberikan beberapa contoh berikut

ini.

Contoh 5.1.4:

G=({a, b, c, d}, {(a,b), (a,d), (b,b), (b,c), (c,d)} merupakan graf tak berarah. Pada graf G ini

mempunyai himpunan verteks V={a, b, c, d}, jadi himpunan V terdiri dari verteks – verteks a,

b, c, dan d. Sedangkan himpunan edge E adalah {(a,b), (a,d), (b,b), (b,c), (c,d)}, terlihat bahwa

setiap elemen dari E merupakan himpunan dari pasangan terurut dari dua verteks di V. Jadi

sesuai dengan definisi diatas G merupakan graf berarah. Verteks a dan b dikatakan adjacent

karena ada edge (a,b) yang menghubungkan antara verteks a dan b.

Penggambaran Graf Berarah

Suatu graf berarah G=(V,E) dapat dinyatakan dalam bentuk gambar dengan aturan

penggambaran sebagai berikut:

1. Untuk setiap verteks Vvi digambarkan dengan lingkaran kecil atau titik berlabel vi.

2. Untuk setiap edge ),(atau jiijij vveEe digambarkan dengan garis berarah yang

menghubungkan dari verteks vi berarah ke verteks vj .

Page 6: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 6

Contoh 5.1.5:

Untuk graf berarah pada Contoh 5.1.4. dapat dinyatakan dalam bentuk Gambar 5.1.3 (a) atau

Gambar 5.1.3. (b).

a b

d c

a b

cd

(a) (b)

Gambar 5.1.3.

Contoh 5.1.6:

Graf berarah pada Gambar 5.1.4. merupakan graf dengan verteks adalah gardu

transfataumatatau aliran listrik g1, g2, g3, g4, dan g5. Dan edge (gi, gj) menyatakan aliran listrik

mengalir dari gardu pi ke gardu pj.

g1

g2g3

g4g5

Gambar 5.1.4.

Contoh 5.1.7:

Dalam suatu kompetisi catur yang menggunakan aturan permainan setengah kompetisi, setiap

pasang pemain hanya bertdaning satu kali. Ada empat pemain yaitu: Anang, Badu, Cecep,

dan Deny. Hasil dari kompetisi tersebut disajikan dalam graf berarah pada Gambar 5.1.4.

Setiap pemain dinyatakan dengan verteks dan edge (u,v) menyatakan bahwa pemain u

mengalahkan pemain v.

Page 7: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 7

Gambar 5.1.4.

Untuk selanjutnya istilah graf mempunyai makna graf berarah atau graf tak berarah.

Page 8: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 8

5.2 Kegiatan Belajar II:

Multigraf Dan Graf Berbobot

Lihat graf pada Gambar 5.2.1, edge e5 dan e6 menghubungkan veteks yang sama, dua edge yang

mengubungkan vertek yang sama dinamakan edge yang sejajar/paralel atau biasa dinamakan

juga dengan multiedge. Sedangkan edge e3 incedent pada satu verteks b, suatu edge yang

incident pada sebuah verteks dinmakan loop. Suatu graf G dapat memuat edge sejajar atau loop,

dan ini kan membawa kita pada definisi berikut ini.

a b

d c

e1

e2

e3

e4e5

e6

Gambar 5.2.1.

Definisi 5.2.1.

Suatu Multigraf G=(V, E) adalah graf berarah atau tak berarah dengan V merupakan

himpunan verteks dan E berupa multiset dengan elemen:

i. berupa pasangan terurut verteks (u, v) jika graf G berarah, atau

ii. berupa himpunan dengan elemen dua verteks {u, v} jika graf G tak berarah.

Suatu Mutigraf yang tidak memuat edge paralel dan tidak memuat loop dinamakan graf

sederhana.

Dari definisi diatas, suatu multigraf dapat berupa graf berarah ataupun tak berarah. Perlu dilihat

lebih jauh, bahwa dengan didefinisikannya E merupakan multiset, mempunyai makna bahwa E

boleh mempunyai elemen kembar.

Page 9: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 9

Suatu multigraf dikatakan berhingga jika graf tersebut mempunyai jumlah verteks berhingga.

Sebagai akibat dari jumah verteks berhingga, maka banyaknya edge juga berhingga. Suatu graf

berhingga dengan banyaknya verteks hanya satu dinamakan graf trivial.

Definisi 5.2.2. Derajat dari suatu verteks pada graf G=(V, E)

i. Untuk graf tak berarah G, derajat dari verteks u, disimbolkan dengan deg(u), adalah

banyaknya edge yang incident dengan verteks u.

ii. Untuk graf berarah G, derajat masuk dari verteks u adalah banyaknya edge yang

terhubung ke verteks u. Sedangkan derajat keluar dari verteks u adalah banyaknya edge

yang terhubung dari verteks u. Derajat dari verteks u adalah derajat masuk + derajat

keluar.

Contoh 5.2.1:

Pada Gambar 5.2.2 merupakan multigraf tak berarah, yaitu ada lebih dari satu edge yang

menghubungkan verteks Jkt dan Bdg. Multigraf banyak dijumpai pada jalur transpatautasi yang

menghubungkan antar kota, biasanya dari kota / tempat satu ke kota / tempat lain ada lebih dari

satu jalur. Derajat dari verteks masing-masing verteks adalah:

deg(Jkt)=3, deg(Bdg)=3, deg(Smg)=3, deg(Jgy)=2, deg(Sby)=3, dan jumahan dari semua

derajat verteks ini adalah 14.

Gambar 5.2.2.

Teorema 5.2.1. Untuk suatu graf G=(V,E), jumlahan dari derajat verteks sama dengan dua

kali banyaknya edge pada G. Atau Vv

Ev ||2)deg(

Bukti:

Page 10: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 10

Untuk setiap edge Ee , memberikan kontribusi sebanyak 2 pada penghitungan derajat pada

verteks, dan dari definisi derajat dari verteks adalah banyaknya edge yang terhubung dengan

verteks tersebut, maka jumlahan derajat dari semua verteks adaah 2|E|. [Terbukti].

Contoh 5.2.2:

Pada Gambar 5.2.3 merupakan multigraf berarah, karena ada lebih dari satu edge yang

menghubungkan verteks 1 dan 3. Derajat pada setiap verteks adalah:

Verteks Derajat masuk Derajat keluar Jumlah

1 1 4 5

2 2 0 2

3 3 1 4

4 1 2 3

Jumlah 7 7 14

Terlihat bahwa jumlahan derajat (masuk dan keluar) adalah 14 dan banyaknya edge adalah 7.

Suatu verteks yang mempunyai derajat nol dikatakan verteks terisolasi (isolated vertex).

1 2

3 4

Gambar 5.2.3.

Jika kita memperhatikan kembali graf-graf pada contoh yang terdahulu, maka

banyaknya verteks yang berderajat ganjil adalah genap. Pada graf Gambar 5.2.2 bayaknya

verteks berderajat ganjil adalah 4, yaitu verteks Jkt, Bdg, Smg, dan Sby. Pada graf Gambar 5.2.3

banyaknya verteks berderajat ganjil adalah 2 yaitu verteks 1 dan 4. Hal ini kita nyatakan dalam

teorema berikut ini.

Teorema 5.2.2. Untuk suatu graf G=(V,E), banyaknya verteks yag berderajat ganjil adalah

genap.

Bukti:

Kebenaran dari Teorema 5.2.2 akan kita buktikan secara induksi. Misal banyaknya edge adalah

n.

Basis induksi:

Page 11: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 11

Untuk setiap n=0, banyaknya edge yang berderajat ganjil adalah 0 atau genap. Sebagai

gambaran lihat Gambar 5.2.4, verteks yang berwarna hitam berderajat ganjil, dan banyaknya

adalah genap .

(a) (b) (c)

Gambar 5.2.4.

Langkah asumsi:

Kita anggap bahwa untuk graf G=(V,E) dengan banyak edge n= k mempunyai banyak

verteks yang berderajat ganjil adalah genap. Jadi pernyataan benar untuk n=k.

Langkah induksi:

Selanjutnya akan ditunjukkan pernyataan benar untuk n=k+1, atau akan ditunjukkan bahwa

pernyataan benar apabila edge bertambah satu. Penambahan satu edge akan mengakibatkan

beberapa alternatif berikut ini:

i. Jika kedua verteks ujung dari edge yang baru keduanya berderajat ganjil (yang berarti

sebelum penambahan edge keduanya berderajat genap) maka terjadi penambahan dua

buah edge yang berderajat ganjil. Sehingga banyaknya edge yang berderajat ganjil

adalah tetap genap.

ii. Jika kedua verteks ujung dari edge yang baru keduanya berderajat genap (yang berarti

sebelum penambahan edge keduanya berderajat ganjil) maka terjadi pengurangan dua

buah edge yang berderajat ganjil. Sehingga banyaknya edge yang berderajat ganjil

adalah tetap genap.

iii. Jika satu verteks ujung dari edge yang baru berderajat ganjil dan satu ujung lain

berderajat genap maka tidak ada penambahan atau pengurangan verteks yang berderjat

ganjil. Sehingga banyaknya edge yang berderajat ganjil adalah tetap genap.

Dengan demikian kebenaran teorema di atas terbukti secara induksi. [Terbukti].

Sekarang kita akan menuju ke suatu graf yang setiap edgenya berlabel sebuah bilangan

riil seperti graf pada Gambar 5.2.4. Label pada setiap edge pada graf tersebut menyatakan jarak

antar kota dalam kilo meter. Label bilangan riil pada edge dinamakan bobot dari edge tersebut.

Page 12: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 12

Suatu graf (berarah atau tak berarah) yang setiap edgenya mempnyai bobot dinamakan graf

berbobot dan secara fataumal didefinisikan sebagai berikut.

Gambar 5.2.4.

Definisi 5.2.3. Graf berbobot (weighted graf) adalah suatu graf (berarah atau tak berarah)

yang setiap edge Ee diberikan label bobot bilangan riil. Graf berbobot disimbolkan dengan

G=(V, E,W) degan (V,E) dapat berupa graf berarah atau tak berarah dan W merupakan suatu

fungsi yang memetakan himpunan edge ke himpunan bilangan riil R atau W:E→R. Untuk

edge Ee dan Rr , w(e)=r menyatakan label r pada edge e.

Contoh 5.2.3:

Dalam suatu kompetisi catur yang menggunakan aturan permainan sistem kompetisi penuh,

setiap pasang pemain hanya bertdaning dua kali. Ada empat pemain yaitu: Anang, Badu,

Cecep, dan Deny. Hasil dari kompetisi tersebut disajikan dalam graf berarah pada Gambar

5.2.5. Setiap pemain dinyatakan dengan verteks dan edge (u,v,r) menyatakan bahwa pemain u

mengalahkan pemain v dalam waktu r menit.

Gambar 5.2.5.

Edge dari Anang ke Badu berabel 100 artinya Anang mengalahkan Badu dalam waktu 100

menit. Ada juga edge dari Badu ke Anang berlabel 150 artinya bahwa dalam pertemuan yang

lain Badu mengalahkan Anang dalam waktu 150 menit. Ada dua edge dari Anang ke deny

Page 13: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 13

masing-masing berabel 80 dan 75, artinya bahwa dalam dua pertemuan Anang mengalahkan

Badu dalam waktu 80 menit dan 70 menit.

Page 14: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 14

5.3 Kegiatan Belajar III:

Lintasan Dan Sirkuit

Dalam suatu graf G, jika verteks menyatakan kota dan edge menyatakan jalan yag

menghubugkan kota satu dengan kota lain, maka perjalanan dari suatu kota melewati beberapa

kota dan berkhir di kota yang lain melalui sederetan jalan. Sederetan jalan yang demikian ini

dinamakan suatu lintasan dari kota awal menuju kota akhir.

Definisi 5.3.1. Lintasan

Dalam suatu graf G=(V,E), Lintasan (path) dari vertek v0 menuju vn dengan panjang n

adalah sederetan berselang-seling antara (n+1) verteks dan n edge yang berawal dari verteks

v0 da berakhir dengan verteks vn atau dalam bentuk simbol sebagai berikut.

v0, e1, v1, e2,..., vn-1, en, vn

edge ei incident dengan verteks vi-1 dan vi untuk i=1, 2, ..., n.

Dalam suatu graf G=(V,E,W), Lintasan (path) dari vertek v0 menuju vt adalah sederetan

berselang-seling verteks dan edge yang berawal dari verteks v0 da berakhir dengan verteks vt

atau dalam bentuk simbol sebagai berikut.

v0, e1, v1, e2,..., vt-1, et, vt

edge ei incident dengan verteks vi-1 dan vi untuk i=1, 2, ..., t.

Panjang lintasan dalam graf berbobot G adalah )(1

t

i

iew atau jumlahan dari semua bobot

edge dalam lintasan tersebut.

Kalau kita perhatikan definisi lintasan diatas, panjang lintasan dalam graf berbobot dan tidak

berbobot ada perbedaan. Dalam graf berbobot panjang lintasan adalah jumlahan semua bobot

edge pada lintasan. Sedangkan dalam graf tidak berbobot panjang lintasan adalah banyaknya

edge pada lintasan tersebut. Untuk lebih jelasnya kita lihat contoh berikut ini.

Ingat bahwa verteks dan edge yang dilalui di dalam lintasan boleh diulang-ulang. Sebuah

lintasan dikatakan lintasan sederhana (simple path) jika lintasan tersebut tidak

memuat/melewati edge yang sama dua kali (setiap edge yang dilalui hanya satu kali). Sebuah

Page 15: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 15

lintasan dikatakan lintasan dasar (elementary path) jika lintasan tersebut tidak

memuat/melewati verteks yang sama dua kali (setiap verteks yang dilalui hanya satu kali,

verteks awal dan akhir boleh sama).

Jika graf yang sedang kita tinjau merupakan graf sederhana, maka simbol – simbol edge pada

penuisan lintasan dapat kita hilangkan. Hal ini dikarenakan edge dari verteks u ke v dalam graf

sederhana tidak lebih dari satu. Sedangan pada multigraf, penulisan lintasan harus lengkap.

Definisi 5.3.2. Sirkuit

Dalam suatu graf G, Suatu Lintasan (path) yang mempunyai verteks awal dan verteks akhir

sama dinamakan Sirkuit (Circuit) atau Cycle.

Sebuah sirkuit dikatakan sirkuit sederhana (simple circuit) jika sirkuit tersebut tidak

memuat/melewati edge yang sama dua kali (setiap edge yang dilalui hanya satu kali). Sebuah

sirkuit dikatakan sirkuit dasar (elementary circuit) jika sirkuit tersebut tidak memuat/melewati

verteks yang sama dua kali (setiap verteks yang dilalui hanya satu kali, verteks awal dan akhir

boleh sama).

Contoh 5.3.1:

Untuk graf tak berarah dan tak berbobot pada Gambar 5.3.1, carilah:

a. Lintasan dari a ke d yang panjangnya masing-masing 1, 2, 3, dan 6?

b. Lintasan sederhana dari c ke b yang panjangnya 4?

c. Sirkuit sederhana dari a ke a yang panjangnya 5?

a b

d c

e1

e2

e3

e4e5

e6

Gambar 5.3.1.

Penyelesaian:

a. Lintasan dari a ke d:

Page 16: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 16

Yang panjangnya 1: a-e2-d merupakan lintasan sederhana dan juga lintasan dasar.

Yang panjangnya 2: tidak ada

Yang panjangnya 3: a-e2-d-e5-c-e5-d bukan lintasan sederhana, juga bukan litasan dasar.

a-e2-d-e5-c-e6-d merupakan lintasan sederhana, bukan lintasan

dasar.

a-e1-b-e4-c-e6-d merupakan lintasan sederhana.

dan yang lainnya, silahkan dicoba cari yang lainnya.

Yang panjangnya 6: a-e1-b-e3-b-e4-c-e5-d-e6-c-e5-d bukan lintasan sederhana.

Dan masih ada satu lagi, silahkan dicoba untuk dicari.

b. Lintasan sederhana dari c ke b yang panjangnya 4 adalah a-e5-d-e6-c-e4-b-e3-b.

Dan masih ada satu lagi, silahkan dicoba untuk dicari.

c. Sirkuit sederhana dari a ke a yang panjangnya 5: a-e2-d-e6-c-e4-b-e3-b-e1-a.

Dan silahkan dicoba untuk mencari yang lainnya.

Contoh 5.3.2:

Untuk graf berarah dan tak berbobot pada Gambar 5.3.2, carilah lintasan dari a ke d yang

panjangnya masing-masing 1, dan 4?

a b

d c

Gambar 5.3.2.

Penyelesaian:

Graf pada Gambar 5.3.2, himpunan edge E tidak memuat memuat elemen kembar. Oleh karena

itu lintasannya dapat dituliskan dengan meggunakan sederatan verteks-verteks saja.

Lintasan dari a ke d yang panjangnya 1 adalah a-d, merupakan lintasan sederhana dan lintasan dasar.

Lintasan dari a ke d yang panjangnya 4 adalah a-b-b-c-d, merupakan lintasan sederhana dan bukan lintasan dasar.

Page 17: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 17

Contoh 5.3.3:

Untuk graf tak berarah dan berbobot pada Gambar 5.3.3, carilah beberapa lintasan dari a ke z

dan tentukan panjangnya?

a

b

c

d

e

f1

24

1

5

7

3

2

6

Gambar 5.3.3.

Penyelesaian:

No Lintasan dari a ke z Panjang lintasan

1 a-c-e-f 11

2 a-b-d-f 10

3 a-b-e-f 12

4 a-b-c-e-f 10

5 a-b-c-e-d-f 8

...

Selanjutnya kita akan melihat keterhubungan suatu graf. Keterhubungan dua buah verteks

dalam suatu graf adalah penting. Dua buah verteks u dan verteks v dikatakan terhubung jika

terdapat lintasan dari u ke v. Jika verteks u terhubung dengan verteks v maka pasti verteks v

dapat dicapai dari verteks u. Misal suatu graf menggambarkan suatu jaringan komputer, maka

dua komputer akan dapat berkomunikasi apabila kedua komputer tersbut terhubung dalam

jaringan. Secara fataumal, definisi graf terhubung adalah sebagai berikut:

Definisi 5.3.3. Graf Tak Berarah Terhubung

Dalam suatu graf tak berarah G, G disebut graf terhubung (connected graf) jika untuk setiap

pasang verteks u dan v di dalam himpunan V terdapat lintasan dari u ke. Jika tidak demikian

maka graf G disebut graf tak-terhubung (disconnected graf).

Contoh 5.3.4:

Page 18: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 18

Untuk graf tak berarah pada Gambar 5.3.4 (a) merupakan graf terhubung, karena jika kita ambil

dua verteks sembarang u dan v pada graf tersebut, maka ada lintasan dari u ke v. Sedangkan

untuk graf tak berarah pada Gambar 5.3.4 (b) merupakan graf tak terhubung, karena ada

sepasang verteks yang tidak ada lintasan yang menghuungkannya, yaitu tidak ada lintasan dari

verteks a dan f.

(a) (b)

Gambar 5.3.4.

Definisi 5.3.3. Graf Berarah Terhubung

Suatu graf berarah G disebut graf terhubung (connected graf) jika arah pada setiap edge

pada G dihilangkan, akan didapat graf tak berarah terhubung. Jika tidak demikian maka graf

berarah G disebut graf tak-terhubung (disconnected graf).

Dalam graf berarah terhubung, dua verteks u dan v dikatakan terhubung kuat (strongly

connected) jika terdapat lintasan berarah dari u ke v dan terdapat lintasan berarah dari v ke u.

Dan dua verteks u dan v dikatakan terhubung lemah (weakly connected) jika terdapat lintasan

berarah dari u ke v tetapi tida ada lintasan dari v ke u.

Definisi 5.3.4. Graf Berarah Terhubung Kuat

Suatu graf berarah G disebut graf terhubung kuat (strongly connected graf) jika setiap

pasang verteks pada G terhubung kuat. Jika ada sepasang verteks di G yang tidak terhubung

kuat, maka graf G dikatakan terhubung lemah (weakly connected graf) dihilangkan, akan

didapat graf tak berarah terhubung. Jika tidak demikian maka graf berarah G disebut graf tak-

terhubung (disconnected graf).

Contoh 5.3.5:

Untuk graf tak berarah pada Gambar 5.3.5 (a) merupakan graf terhubung kuat, karena untuk

setiap pasang verteks u dan v di dalam graf tersebut terdapat lintasan dari u ke v dan lintasan

Page 19: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 19

dari v ke u. Sedangkan graf pada Gambar 5.3.5 (b) merupakan graf terhubung lemah, karena

tidak semua pasangan verteks mempunyai lintasan dari dua arah. Contohnya: untuk verteks a

dan verteks d, ada lintasan dari a ke d, akan tetapi tidakada lintasan dari d ke a.

(a) (b)

Gambar 5.3.4.

.

Page 20: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 20

5.4 Kegiatan Belajar IV:

Lintasan Euler Dan Hamilton

Tulisan pertama tentang tentang graf adalah karya Leonhard Euler pada 1736. Tulisan tersebut

menyajikan sebuah permasalahan umum yang menyertakan sebuah solusi yang sekarang

disebut masalah jembatan Königsberg. Dua pulau terhampar di Sungai Pregel yang terletak di

kota Königsberg (saat ini Kaliningrad di Rusia) saling terhubung oleh jembatan-jembatan,

seperti yang diperlihatkan dalam Gambar 5.4.1 (a). Permasalahannya adalah untuk memulai

berjalan dari sembarang lokasi A, B, C, atau D menyeberangi setiap jembatan satu kali,

kemudian kembali lagi pada tempat semula. Ini yang dinamakan dengan permasalahan sirkuit

Euler. Permasalahan Euler pada jembatan Königsberg dapat disederhanakan dalam bentuk graf

seperti yang terlihat pada Gambar 5.4.1 (b).

(a) (b)

Gambar 5.4.1 Jembatan Kőnigsberg dan grafnya

Definisi 5.4.1. Lintasan Euler dan Sirkuit Euler

Lintasan Euler pada suatu graf G adalah suatu lintasan yang melewati setiap edge pada graf

G tepat satu kali.

Sirkuit Euler pada suatu graf G adalah suatu sirkuit yang melewati setiap edge pada graf G

tepat satu kali.

Lintasan Euler melewati setiap edge dari graf tepat satu kali. Bila lintasan Euler tersebut

kembali ke verteks asal maka lintasan tertutup tersebut dinamakan sirkuit Euler. Graf yang

mempunyai sirkuit Euler disebut graf Euler (Eulerian graf). Sedangkan graf G hanya memiliki

lintasan Euler dinamakan graf semi-Euler (semi-Eulerian graf).

Page 21: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 21

Contoh 5.4.1:

Perhatikan Gambar 5.4.2. Setiap graf yang berada pada gambar tersebut merupakan graf semi

Euler, yaitu hanya terdapat lintasan Euler.

a

b

c

d

e

a

b

c

d

e

f

(a) (b)

Gambar 5.4.2 Graf semi Euler

Untuk graf pada Gambar 5.4.2 (a), salah satu lintasan Eulernya adalah: c-a-b-c-e-b-d-e. Dan

graf ini tidak memiliki sirkuit Euler. Sedangkan untuk graf pada Gambar 5.4.2 (b), salah satu

lintasan Eulernya adalah: c-a-b-c-e-b-d-e-f-d. Dan graf ini tidak memiliki sirkuit Euler.

Contoh 5.4.2:

Perhatikan Gambar 5.4.3. Setiap graf yang berada pada gambar tersebut merupakan graf Euler,

yaitu terdapat sirkuit Euler.

a

b

c

d

e

a

b d

e

f

c

(a) (b)

Gambar 5.4.3 Graf Euler

Untuk graf pada Gambar 5.4.3 (a), salah satu sirkuit Eulernya adalah: a-b-c-d-e-c-a. Sedangkan

untuk graf pada Gambar 5.4.3 (b), salah satu lintasan Eulernya adalah: a-b-c-e-b-d-e-f-d-c-a.

Contoh 5.4.2:

Perhatikan graf Gambar 5.4.1. Graf permasalahan jembatan Königsberg tersebut tidak

mempunyai lintasan maupun sirkuit Euler.

Page 22: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 22

a

b

c

d

e

a

b d

e

f

c

(a) (b)

Gambar 5.4.3 Graf Euler

Untuk graf pada Gambar 5.4.3 (a), salah satu sirkuit Eulernya adalah: a-b-c-d-e-c-a. Sedangkan

untuk graf pada Gambar 5.4.3 (b), salah satu lintasan Eulernya adalah: a-b-c-e-b-d-e-f-d-c-a.

Syarat cukup dan perlu keberadaan lintasan Euler maupun sirkuit Euler dalam suatu graf

ternyata sangat sederhana. Euler menemukan syarat tersebut untuk memecahkan masalah

jembatan Konigsberg, yang dinyatakan di dalam Teorema 5.4.1 sampai dengan teorema 5.4.3.

Teorema 5.4.1. Jika suatu graf tak berarah terhubung G terdapat sirkuit Euler maka setiap

verteks di dalam graf G tersebut berderajat genap.

Bukti:

Dipunyai bahwa dalam suatu graf G yang terdapat sirkuit Euler yang berawal dari suatu

verteks, misal a, dan akan berakhir di a. Ini berarti bahwa ada edge awal dan edge akhir dari

sirkuit yang memberikan kontribusi pada jumlahan derajat dari a sebanyak dua. Sedangkan

untuk verteks lain b, yang bukan verteks awal atau akhir dari sirkuit, yang dilalui sirkuit,

ada edge menuju b dan edge keluar b. Ini mengakibatkan derajat dari verteks tersebut

bertambah dua (genap). Karena setiap edge pada graf G harus dilalui oleh sirkuit Euler dan

setiap edge yang dilalui derajatnya bertambah dua (genap), maka setiapverteks akan

berderajat genap.

Teorema 5.4.2. Jika setiap verteks di dalam suatu graf tak berarah terhubung G berderajat

genap maka pada graf G terdapat sirkuit Euler.

Bukti:

Pembuktin teorema ini akan dilakukan secara induksi. Misal banyaknya edge adalah n.

Basis induksi:

Page 23: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 23

Untuk n=0, graf G terhubung dan tidak mempunyai edge, berarti graf G hanya terdiri dari

sebuah verteks. Oleh karena itu pada G ada sirkuit Euler yang terdiri dari verteks tunggal

dan tanpa edge.

Langkah asumsi dan induksi:

Danaikan G mempunyai n edge, n > 0, dan bahwa sembarang graf terhubung dengan k edge,

k < n, setiap verteks mempunyai derajat genap maka G mempunyai sebuah sirkuit Euler. Ini

merupakan cara langsung untuk membuktikan bahwa sebuah graf terhubung dengan verteks

atau lebih, masing-masing mempunyai derajat genap, mempunyai sebuah sirkuit, sehingga

kita asumsikan bahwa graf tersebut mempunyai paling sedikit tiga verteks.

Karena G terhubung, terdapat verteks v1, v2, dan v3 di G dengan edge e1 insident pada v1 dan

v2, serta edge e2 insiden pada v2 dan v3. Jika kita hapus edge e1, dan e2, tetapi kita biarkan

verteks-verteksnya, dan kita tambahkan sebuah edge e yang insiden pada v1 dan v3 untuk

memperoleh graf G' seperti terlihat pada Gambar 5.4.4(a). Perhatikan bahwa setiap

komponen dari graf G' mempunyai edge lebih sedikit dari n edge. Dan dalam setiap

komponen dari graf G' setiap verteks mempunyai derajat genap. Kita tunjukkan bahwa G'

mempunyai satu atau pun dua komponen.

(a) (b) (c)

Gambar 5.4.3 Pembuktian teorema 5.4.2

Misalkan v adalah sebuah verteks di G. Karena G terhubung, terdapat sebuah lintasan P di G

dari v ke v1. Misalkan P' adalah bagian dari lintasan P yang berawal dari v yang edge-

edgenya juga di G'. Selanjutnya P' berakhir baik pada v1, v2, ataupun v3 karena satu-satunya

cara P gagal sebagai sebuah lintasan di V' adalah P mengdanung satu dari edge-edge

terhapus e1 atau e2. Jika P' berakhir di v1, maka v berada di komponen yang sama seperti v1

di G, Jika P' berakhir di v3 [lihat Gambar 5.4.3 (b)], maka v berada di komponen yang sama

Page 24: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 24

dengan v3 di G’, yang berada dalam komponen yang sama dengan v1 di G' (karena edge e di

G' insiden pada v1 dan v3). Jika P' berakhir di v2, maka v2 berada dalam komponen yang

sama dengan v. Oleh karena itu, sembarang verteks di G' berada dalam komponen yang

sama dengan baik v1 maupun v2. Sehingga G' mempunyai satu atau dua komponen.

Jika G' mempunyai satu komponen, yakni, jika G' terhubung, kita dapat menerapkan

hipotesis induktif untuk menyimpulkan bahwa G' mempunyai sebuah sirkuit Euler C'.

Sirkuit Euler ini dapat dimodifikasi untuk menghasilkan sebuah sirkuit Euler di G, kita

hanya mengganti kemunculan edge e di C' dengan edge-edge e1 dan e2.

Danaikan bahwa G' mempunyai dua komponen [lihat Gambar 5.4.3 (c)]. Menurut hipotesis

induktif, komponen yang mengdanung v1 mempunyai sebuah sirkuit Euler C' dan komponen

yang mengdanung v2 mempunyai sebuah sirkuit Euler C" yang berawal dan berakhir di v2.

Sebuah sirkuit Euler di G diperoleh dengan memodifikasi C' dengan menggantikan (v1, v3)

di C' dengan (v1, v2) yang diikuti oleh (v2, v3) atau dengan menggantikan (v3, v1) di C'

dengan (v3, v2) yang diikuti oleh C" yang diikuti oleh (v2, v1). Langkah Induktif telah

lengkap dan G mempunyai sebuah sirkuit Euler. [Terbukti]

Teorema 5.4.3. Untuk suatu graf tak berarah terhubung G merupakan graf semi Euler

(terdapat lintasan Euler) jika dan hanya jika di dalam graf G tersebut terdapat tepat dua

verteks berderajat ganjil.

Bukti:

Bukti dari teorema ini dibiarkan untuk latihan.

Pembahasan lintasan dan sirkuit Euler di atas untul graf tak berarah terhubung. Bagaimana

dengan graf yang berarah terhubung. Untuk graf berarah, keberaaan lintasan dan sirkuit

Euler lang disajikan pada teorema 5.4.4 yang tidak sertai dengan bukti.

Teorema 5.4.4. Graf berarah terhubung G memiliki sirkuit Euler jika dan hanya jika G

terhubung dan setiap verteks memiliki derajat-masuk dan derajat-keluar sama. G

memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap verteks memiliki

derajat masuk dan derajat-keluar sama kecuali dua verteks, yang pertama memiliki

derajat keluar satu lebih besar derajat-masuknya, dan yang kedua memiliki derajat

masuk satu lebih besar dari derajat-keluarnya.

Page 25: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 25

Jika pada pembahasan lintasan dan sirkuit Euler melewati setiap edge dari graf tepat sekali,

maka selanjutnya kita akan mengkaji permasalahan suatu lintasan yang melewati setiap verteks

pada graf tepat satu kali.

Definisi 5.4.2. Lintasan dan Sirkuit Hamilton

Lintasan Hamilton pada suatu graf G adalah suatu lintasan yang melewati setiap verteks graf

G tepat satu kali.

Sirkuit Hamilton pada suatu graf G adalah suatu sirkuit yang melewati setiap edge pada graf

G tepat satu kali.

Dari definisi di atas, apabila dalam lintasan Hamilton verteks awal sama dengan verteks akhir,

lintasan tersebut menjadi tertutup dan dinamakan sikuit Hamilton. Graf yang memiliki sirkuit

Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton

disebut graf semi-Hamilton.

Nama sirkuit Hamilton muncul ketika Sir William Hamilton membuat permainan

dodecahedron. Pada tahun 1859 Sir William Hamilton menawarkan mainan teka-teki ke pabrik

alat mainan Dublin. Mainan itu terdiri dari dodecahedron (yaitu benda yang disusun oleh 12

buah pentagonal dan di sini ada 20 buah titik sudut) dan tiap titik sudut diberi nama ibukota

negara seperti terlihat pada Gambar 5.4.4 (a). Permainan yang dapat dilakukan adalah

membentuk perjalanan keliling dunia, yang mengunjungi 1 ibukota tepat satu kali dan kembali

lagi ke kota asal. Persoalan ini dinamakan mencari sirkuit Hamilton. Gambar 5.4.4 (b) adalah

graf yang memodelkan proyeksi dodecahedron dengan sebuah sirkuit Hamilton yang bergaris

tebal.

Page 26: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 26

(a) (b)

Gambar 5.4.4 Sirkuit Hamilton pada dodecahedron

Selanjutnya akan dibahas beberapa teorema yang menunjukkan keberadaan lintasan atau sirkuit

Hamilton, yaitu Teorema Dirac dan Teorema Ataue.

Teorema 5.4.5. Dirac

Jika graf G merupakan graf sederhana dengan n buah verteks, n ≥ 3, sedemikian sehingga

derajat tiap verteks paling sedikit n/2 maka graf merupakan graf Hamilton.

Teorema 5.4.6. Ataue

Jika graf G merupakan graf sederhana dengan n buah verteks, n ≥ 3, sedemikian sehingga

jumlah derajat tiap pasang verteks u dan v di G yang tidak adjacent paling sedikit n atau d(u)

+d(v) ≥ n maka graf merupakan graf Hamilton.

Teorema 5.4.7. Jika graf G adalah graf lengkap maka G merupakan graf Hamilton.

Teorema 5.4.6. Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3, maka

terdapat (n - 1)!/2 buah sirkuit Hamilton.

Teorema 5.4.7.

Page 27: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 27

Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3 dan n ganjil, maka terdapat

(n - 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada edge yang beririsan).

Jika graf G merupakan graf lengkap dengan n buah verteks, n ≥ 3 dan n genap, maka terdapat

(n - 2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh 5.4.3:

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?.

Penyelesaian:

Persoalan di atas dapat direpresentasikan oleh sebuah graf dengan sembilan buah verteks

sedemikian sehingga setiap verteks menyatakan anggota klub, dan edge yang menghubungkan

dua buah verteks menyatakan kedua verteks tersebut bertetangga dalam tempat duduk, lihat

Gambar 5.5.5.

8

7

6 5

4

3

2

1

9

Gambar 5.5.5

Sirkuit Hamilton: 1, 2, 3, 4, 5, G, 7, 8, 9, 1 edge dengan garis tebal, menyatakan salah satu cara

pengaturan tempat duduk. Pada fataumasi ini atauang 1 bertetangga kiri dengan 2 dan

bertetangga kanan dengan atauang 9. Atauang 2 bertetangga kiri dengan 3 dan bertetangga

kanan dengan atauang 1, dan seterusnya.

Sirkuit Hamilton: 1, 5, 9, 4, 8, 3, 7, 2, 6, 1 edge dengan garis tipis, menyatakan salah satu cara

lain pengaturan tempat duduk. Pada fataumasi ini atauang 1 bertetangga kiri dengan 5 dan

Page 28: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 28

bertetangga kanan dengan atauang 6. Atauang 2 bertetangga kiri dengan 6 dan bertetangga

kanan dengan atauang 7, dan seterusnya.

Kalau kita lihat sirkuit Hamilton garis tebal dan garis tipis tidak beririsan edge dengan sirkuit

Hamilton yang bergaris tipis, atau kedua sirkuit tersebut saling asing.

Jumlah pengaturan tempat duduk yang berbeda ada (9-1)/2 = 4. Oleh karena itu atauang dalam

klub tersebut dapat bertemu dalam 4 hari dengan selalu berganti tetangga duduk.

Suatu graf dapat berupa graf Hamilton dan sekaligus berupa graf Euler, seperti graf pada

Gambar 5.5.6.

a

b d

e

f

c

Gambar 5.5.6 Graf Hamilton sekaligus graf Euler

Page 29: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 29

5.5 Kegiatan Belajar V:

Lintasan Terpendek

Dalam suatu graf berbobot G=(V,E,W), panjang lintasan dari verteks awal s ke verteks akhir t

adalah )(1

t

i

iew dengan w(ei) adalah bobot pada edge ei yang berada pada lintasan tersebut,

atau jumlahan dari semua bobot edge dalam lintasan tersebut. Sebagaimana kita ketahui

sebelumnya bahwa lintasan dari satu verteks ke verteks lain tidak tunggal, sehingga panjang

lintasan dari verteks s ke verteks t bisa lebih dari satu nilai. Dari sini, muncul suatu

permasalahan bagaimana mencari lintasan terpendek dari vertek s ke verteks t.

Definisi 5.5.1. Lintasan Terpendek

Lintasan terpendek dari verteks s ke verteks t pada suatu graf berbobot G=(V,E,W) adalah

minimal dari semua panjang lintasan yang dapat dibentuk dari verteks s menuju verteks v.

Contoh 5.5.1:

Perhatikan graf tak berarah berbobot dan terhubung pada Gambar 5.5.1.

a

b

d

c

3 5

7

1

3

Gambar 5.5.1.

Tabel berikut ini menampilkan beberapa lintasan terpendek dari suatu verteks ke satu verteks

yang lain.

Page 30: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 30

Vertek awal

s

Vertek tujuan

t

Lintasan dari s ke t Panjang

lintasan

Lintasan terpendek dan

dan panjangnya

a b a-b 3

a-c-b 8

a-c-d-b 15

Dan lainnya

a d a-b-d 8

a-b-c-d 7

a-c-d 10

Dan lainnya

d b d-b 5

d-c-b 4

d-c-a-b 13

Dan lainnya

a-b

Panjang = 3

a-b-c-d

Panjang = 7

d-c-b

Panjang = 4

Dan yang lainnya

Contoh 5.5.2:

Perhatikan graf berarah berbobot dan terhubung pada Gambar 5.5.2.

a

b

d

c

3 5

7

1

3

-2

Gambar 5.5.2.

Tabel berikut ini menampilkan beberapa lintasan terpendek dari suatu verteks ke satu verteks

yang lain.

Vertek awal

s

Vertek tujuan

t

Lintasan dari s ke t Panjang

lintasan

Lintasan terpendek dan

dan panjangnya

a d a-b-d 8

a-c-b-d 13

a-c-d 10

a-c-d-a-b-d 16

Dan lainnya

a c a-c 7

a-b-d-a-c 13

Dan lainnya

a-b-d

Panjang = 8

a-c

Panjang = 7

Dan yang lainnya

Page 31: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 31

Langkah-langkah untuk mencari lintasan terpendek dari satu verteks ke satu verteks lain

ditemukan oleh E. W. Dijkstra, lahir 5 Mei 1930 di Rotterdam Beldana. Oleh karena itu,

langkah-langkah untuk mencari lintasan terpendek ini dikenal sebagai algoritma Dijkstra.

Karena dedikasinya pada pemograman maka pada saat pernikahannya di tahun 1957, ia

mencantumkan prdariesinya sebagai seatauang programmer. Akan tetapi pemerintah Beldana

menyatakan bahwa prdariesi semacam itu tidak ada dan dia harus mengubah prdariesi menjadi

"fisikawan teatauitis:" Ia memenangkan Turing Award dari Association fatau Computing

Machinery pada tahun 1972. Ia juga terpilih sebagai Schlumbleger Centennial Chair in

Computer Science di Universitas Texas, Austin tahun 1984.

Ingat bahwa dalam pembahasan pencarian lintasan terpendek ini, graf G=(V,E,W) menyatakan

sebuah graf berbobot tersambung dan tidak memuat sirkuit (cycle) dengan panjang negatif.

Algatauitma Dijkstra melibatkan pemasangan label pada setiap verteks v V. Anggaplah kita

akan mencari lintasan terpendek dari verteks s ke verteks lainnya. Dua langkah utama dalam

algatauitma Dijkstra adalah:

1. Pemberian label pada vertek

2. Pencarian lintasan dan penghitungan panjang lintasan terpendek

1. Langkah Pemberian label pada verteks

Pada setiap vertek v V diberikan label [p(v), d(v), m(v)] dimana:

p(v) : predecessatau v (verteks sebelum v di dalam lintasan)

d(v) : Panjang (distance) lintasan dari verteks awal s menuju verteks v.

m(v) : suatu tdana yang nilainya permanen (’*’) atau sementara (’-’).

Urutan langkah-langkah pencarian pemebrian label dalam algatauitma Dijkstra sebagai berikut:

i. Langkah inisialisasi:

Untuk verteks awal s diberikan label p(s)=s, d(s)=0, dan m(s)=’*’ atau [s,0,*].

Untuk setiap verteks v V selain s diberikan label p(v)=v, d(v)= , dan m(s)=’-‘ atau

[v, , -].

t = verteks terakhir yang diberikan tdana permanen (*), pada awal ini t=s.

ii. Untuk setiap verteks v V yang adjacent dengan t dan tidak berlabel permanen, lakukan:

Penghitugan label d(v)=min {d(v), d(t)+ w(t,v)}, w(t,v) adalah bobot edge (t,v).

Page 32: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 32

Label ),()()(,

),()()(,)(

twtdvdjikat

twtdvdjikatetapvp

iii. Untuk verteks v V yang belum berlabel permanen, kita cari verteks u yang mempunyai

label jarak p(u) paling kecil dan

beri tdana permanen pada u atau m(u)=* dan p(u)=.

t= verteks terakhir yang diberikan tdana permanen (*), atau t=u.

iv. Jika ada verteks v V yang adjacent dengan t maka ulangi dari langkah ii, jika-tidak-

maka selesai.

2. Langkah pencarian lintasan dan penghitungan panjang lintasan terpendek

Dari hasil pelabelan (graf yang sudah berlabel) langah sebelumnya, dilakukan:

i. Pencarian panjang lintasan terpendek dari verteks s ke verteks v V.

Panjang litasan terpendek dari s ke v adalah d(v).

ii. Pencarian lintasan terpendek dari verteks s ke verteks v V.

Berawal dari v, atau t=v. Dan Litasan Terpendek =’v’;

Selama t s lakukan:

Lintasan terpendek = p(t) digabung dengan Lintasan terpendek;

t=p(t);

Contoh 5.5.3:

Untuk graf pada Gambar 5.5.3, dapatkan lintasan terpendek dari a ke d dan dari a ke c.

a

b

d

c

3 5

7

1

3

Gambar 5.5.3.

Penyelesaian:

Langkah Pemberian label pada verteks.

Verteks awal adalah verteks a, dan beri label pada verteks a dengan [a,0,*]

Label untuk verteks lainnya dapat dilihat langsung pada gambar graf, label ada disebelah

verteks.

Page 33: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 33

[a,0,*]

[b,¥,-]

[c,¥,-]

[d,¥,-]a

b

d

c

3 5

7

1

3

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan a, yaitu vertek b dan

c lakukan:

d(b)=min {d(b), d(a)+ w(a,b)}={ , 0+3} = 3 dan label p(b)=a

d(c)=min {d(c), d(a)+ w(a,c)}={ , 0+7} = 7 dan label p(c)=a

Label graf tampak seperti gambar berikut ini.

[a,0,*]

[a,,-]

[a,,-]

[d,¥,-]a

b

d

c

3 5

7

1

3

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks b.

Verteks b kita beri label permanen, atau m(b)=*. Verteks terakhir yang berlabel permanen

adalah verteks b, dan graf menjadi:

[a,0,*]

[a,,*]

[a,,-]

[d,¥,-]a

b

d

c

3 5

7

1

3

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan b, yaitu vertek c dan

d lakukan:

d(c)=min {d(c), d(b)+ w(b,c)}={7, 3+1} = 4 dan label p(c)=b

d(d)=min {d(d), d(b)+ w(b,d)}={ , 3+5} = 8 dan label p(d)=b

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks c.

Verteks c kita beri label permanen, atau m(c)=*. Verteks terakhir yang berlabel permanen

adalah verteks c, dan graf menjadi:

Page 34: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 34

[a,0,*]

[a,,*]

[b,,*]

[b,,-]a

b

d

c

3 5

7

1

3

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan c, yaitu verteks d,

lakukan:

d(d)=min {d(d), d(c)+ w(c,d)}={8, 4+3} = 7 dan label p(d)=c

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks d.

Verteks d kita beri label permanen, atau m(d)=*. Verteks terakhir yang berlabel permanen

adalah verteks d, dan graf menjadi:

[a,,*]

[b,,*]

[c,,*]a

b

d

c

3 5

7

1

3

Dan sudah tidak ada lagi vertek yang berlabel tidak permanen, langkah pelabelan selesai.

Langkah pencarian lintasan dan penghitungan panjang lintasan terpendek

Lintasan terpendek dari a ke d:

Panjang lintasan terpendeknya adalah d(d) = 7.

Lintasan terpendeknya adalah:

o Dari vertek d buat lintasan: d

o Gabung p(d)=c dengan lintasan sebelumnya, didapat: c-d

o Gabung p(c)=b dengan lintasan sebelumnya, didapat: b-c-d

o Gabung p(b)=a dengan lintasan sebelumnya, didapat: a-b-c-d

Jadi lintasan terpendeknya adalah: a-b-c-d.

Lintasan terpendek dari a ke c:

Panjang lintasan terpendeknya adalah d(c) = 4.

Lintasan terpendeknya adalah:

o Dari vertek c buat lintasan: c

o Gabung p(c)=b dengan lintasan sebelumnya, didapat: b-c

o Gabung p(b)=a dengan lintasan sebelumnya, didapat: a-b-c

Jadi lintasan terpendeknya adalah: a-b-c.

Page 35: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 35

Contoh 5.5.4:

Untuk graf pada Gambar 5.5.4, dapatkan lintasan terpendek dari s ke t.

c

2

3

6

14

-5

12

3

2

6

s

b

c

d

d

t

Gambar 5.5.4.

Penyelesaian:

Langkah Pemberian label pada verteks.

Verteks awal adalah verteks s, dan beri label pada verteks s dengan [s,0,*]

Label untuk verteks lainnya dapat dilihat langsung pada gambar graf, label ada disebelah

verteks.

c

2

3

6

14

-5

12

3

2

6

s

b

c

d

e

t

[s,0,*]

[b,¥,-]

[c,¥,-]

[d,¥,-]

[e,¥,-]

[t,¥,-]

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan s, yaitu vertek b dan

c lakukan:

d(b)=min {d(b), d(s)+ w(s,b)}={ , 0+2} = 2 dan label p(b)=s

d(c)=min {d(c), d(s)+ w(s,c)}={ , 0+6} = 6 dan label p(c)=s

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks b.

Verteks b kita beri label permanen, atau m(b)=*. Verteks terakhir yang berlabel permanen

adalah verteks b, dan graf menjadi:

c

2

3

6

14

-5

12

3

2

6

s

b

c

d

e

t

[s,0,*]

[s,,*]

[s,,-]

[d,¥,-]

[e,¥,-]

[t,¥,-]

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan b, yaitu vertek c dan

d lakukan:

d(c)=min {d(c), d(b)+ w(b,c)}={6, 2+3} = 5 dan label p(c)=b

d(d)=min {d(d), d(b)+ w(b,d)}={ , 2+12 = 14 dan label p(d)=b

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks c.

Verteks c kita beri label permanen, atau m(c)=*. Verteks terakhir yang berlabel permanen

adalah verteks c, dan graf menjadi:

Page 36: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 36

c

2

3

6

14

-5

12

3

2

6

s

b

c

d

e

t

[s,0,*]

[s,,*]

[b,,*]

[b,,-]

[e,¥,-]

[t,¥,-]

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan c, yaitu verteks e,

lakukan:

d(e)=min {d(e), d(c)+ w(c,e)}={∞, 5+14}= 19 dan label p(e)=c

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks d.

Verteks d kita beri label permanen, atau m(d)=*. Verteks terakhir yang berlabel permanen

adalah verteks d, dan graf menjadi:

c

2

3

6

14

-5

12

3

13

6

s

b

c

d

e

t

[s,0,*]

[s,,*]

[b,,*]

[b,,*]

[c,,-]

[t,¥,-]

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan d, yaitu verteks e

dan t, lakukan:

d(e)=min {d(e), d(d)+ w(d,e)}={19, 14+3}= 17 dan label p(e)=d

d(t)=min {d(t), d(d)+ w(d,t)}={∞, 14+13}= 27 dan label p(t)=d

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks e.

Verteks e kita beri label permanen, atau m(e)=*. Verteks terakhir yang berlabel permanen

adalah verteks e, dan graf menjadi:

c

2

3

6

14

-5

12

3

13

6

s

b

c

d

e

t

[s,0,*]

[s,,*]

[b,,*]

[b,,*]

[d,,*]

[d,27,-]

Untuk semua vertek yang tidak berlabel permanen dan adjacent dengan e, yaitu verteks t,

lakukan:

d(t)=min {d(t), d(e)+ w(e,t)}={27, 17+6}= 23 dan label p(t)=e

Untuk verteks yang belum berlabel permanen, kita cari sebuah verteks yang mempunyai

label jarak paling kecil dan didapatkan verteks t.

Verteks e kita beri label permanen, atau m(t)=*. Verteks terakhir yang berlabel permanen

adalah verteks t, dan graf menjadi:

Page 37: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 37

c

2

3

6

14

-5

12

3

13

6

s

b

c

d

e

t

[s,0,*]

[s,,*]

[b,,*]

[b,,*]

[d,,*]

[e,23,*]

Dan sudah tidak ada lagi vertek yang berlabel tidak permanen, langkah pelabelan selesai.

Langkah pencarian lintasan dan penghitungan panjang lintasan terpendek Lintasan terpendek dari s ke t:

Panjang lintasan terpendeknya adalah d(t) = 23.

Lintasan terpendeknya adalah:

o Dari vertek t buat lintasan: t

o Gabung p(t)=e dengan lintasan sebelumnya, didapat: e-t

o Gabung p(e)=d dengan lintasan sebelumnya, didapat: d-e-t

o Gabung p(d)=b dengan lintasan sebelumnya, didapat: b-d-e-t

o Gabung p(b)=s dengan lintasan sebelumnya, didapat: s-b-d-e-t

Jadi lintasan terpendeknya adalah: s-b-d-e-t.

Page 38: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 38

5.6 Kegiatan Belajar VI:

Subgraf, Graf Isomorpik, Dan

Pada bagian ini kita akan membahas tentang suatu graf yang merupakan bagian dari graf lain. Konsep dasar

subgraf ini sangat penting dalam pengembangan teataui graf dan penerapannya. Secara fataumal subgraf

didefinisikan seperti berikut ini.

Definisi 5.6.1. Subgraf

Pandang graf G = G( V, E). Suatu graf H = H( V’, E’) dikatakan sebagai suatu subgraf dari graf G jika

semua verteks dan edge dari H termuat dalam himpunan verteks dan edge dari G, atau

jika V’ X V dan E‘ X E.

Secara khusus:

i. Jika verteks v di G, maka G - v merupakan subgraf dari G yang diperoleh dengan cara menghapus v dari

G dan menghapus semua edge di G yang incedent dengan v.

ii. Jika edge e di G, maka G - e merupakan subgraf dari G yang diperoleh dengan cara menghapus e dari G.

Contoh 5.6.1:

Untuk graf pada Gambar 5.6.1 (b) dan Gambar 5.6.1 (c) merupakan subgraf dari graf pada

Gambar 5.6.1 (a).

(a) (b) (c)

Gambar 5.6.1.

Selanjutnya kita akan melihat dua graf yang serupa akan tetapi keuda graf tersebut tidak sama. Seperti

yang graf G1=({a,b,c,d},{{a,b},{a,d},{b,c},{c,d}) pada Gambar 5.6.2 (a) dan graf

G2=({1,2,3,4},{{1,2},{1,4},{2,3},{3,4}) Gambar 5.6.2 (b) berikut ini.

Page 39: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 39

a b

d c

e1

e2

e3

e4 G1

1 2

3 4

e1

e2

e3

e4 G2

(a) (b)

Gambar 5.6.2 Dua graf yang serupa tapi tak sama

Walaupun secara gambar sama, hanya berbeda penamaan saja, akan tetapi secara definisi graf keduanya

berbeda karena {a,b,c,d} ≠ {1,2,3,4}. Perhatikan juga graf pada Gambar 5.6.3 (a) dan graf pada Gambar

5.6.3 (b). Secara gambar geometrik graf keduanya kelihatan berbeda, akan tetapi kedua graf tersebut

sama.

a

b

d

c

a

b

d

c

(a) (b)

Gambar 5.6.3 Dua graf yang sama

Dari paparan di atas, akan membawa kita pada keserupaan dua buah graf yang disebut dengan

isomorpik.

Definisi 5.6.2. Isomorpik

Graf G=(V,E) dan G*=(V*,E*) dikatakan isomorpik (isomorphic) jika ada korespondensi satu-satu

f:VY V* sedemikian sehingga jika edge {u,v} di G maka edge {f(u),f(v)} juga di G*.

Contoh 5.6.2:

Untuk graf pada Gambar 5.6.4, ada 10 graf yang bentuknya diserupakan huruf. Dapatkan

pasangan graf yang saling isomorpik.

Gambar 5.6.4.

Perhatikan bahwa:

Graf bentuk huruf A dan R adalah isomorpik.

Page 40: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 40

Graf bentuk huruf F dan T adalah isomorpik.

Graf bentuk huruf K dan X adalah isomorpik.

Graf bentuk huruf M, S, V dan Z adalah isomorpik.

Suatu graf dapat diperoleh dari graf lain dengan cara menambahkan verteks ditengah dari suatu

edge pada graf tersebut. Graf yang didapat dengan cara demikian ini dinamakan graf

homeomorpik, dan didefinisikan seperti berikut ini.

Definisi 5.5.3. Homeomorpik

Dua graf G dan G* dikatakan homeomorpik (homeomorphic) jika keduanya diperoleh dari

suatu graf yang sama (atau graf yang isomorpik) dengan cara menambahkan beberapa vertek

pada suatu edge dari graf asalnya.

Contoh 5.6.3:

Untuk graf pada Gambar 5.6.5 (b) dan graf Gambar 5.6.5 (c) adalah homeomorpik karena

keduanya didapat dari graf pada Gambar 5.6.5 (a) dengan cara menambahkan beberapa vertek

pada suatu edge yang sama di graf pada Gambar 5.6.5 (a).

(a) (b) (c)

Gambar 5.6.5

Page 41: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 41

5.7 Kegiatan Belajar VII:

Graf Planar

Pada sub bab ini, kita akan belajar tentang suatu gambar graf yang digamabar dalam suatu

bidang dengan edge satu dengan lainnya tidak saling memotong. Sebagaimana telah disinggung

pada sub bab sebelumnya bahwa suatu graf dapat digambarkan dalam beberapa macam bentuk,

seperti Gambar 5.7.1 berikut ini.

Graf pada Gambar 5.7.1 (a) dan graf pada Gambar 5.7.1 (b) adalah graf yang sama. Pada

Gambar 5.7.1 (a) tidak ada edge yang saling memotong, sedang graf pada Gambar 5.7.1 (b) ada

edge yang saling potong. Hal ini akan membawa kita pada definisi berikut ini.

a

b

d

c

a

b

d

c

(a) (b)

Gambar 5.7.1 Dua graf yang sama, beda representasi

Definisi 5.7.1. Graf Planar

Suatu Graf G dikatakan graf planar jika graf tersebut dapat digambar dalam bidang tanpa ada edge-

edge yang saling memotong.

Gambar graf yang tidak memuat edge-edge yang saling berpotongan dinamakan representasi planar

(planar representation) dari graf planar, atau sering dinamakan juga dengan graf bidang (plane graf).

Suatu graf planar dapat juga mempunyai gambar graf yang memuat edge-edge yang saling

berpotongan. Akan tetapi grafnya tetap planar. Untuk menunjukkan bahwa suatu graf planar,

cukup ditunjukkan representasi planar dari graf tersebut.

Contoh 5.7.1:

Tunjukkan bahwa graf G=({a, b, c, d, e, f, g, h}, E) merupakan graf planar? Dimana hinpunan

edge E = {{a,b}, {a,d}, {a,e}, {b,c}, {b,f}, {c,d},{c,g}, {d,h}{e,f},{e,h},{f,g},{g,h}}.

Page 42: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 42

Graf G di atas dapat dinyatakan dalam bentuk Gambar 5.7.2 (a) dan Gambar 5.7.2 (b). Dalam

representasi pada Gambar 5.7.2 (b) tidak ada edge-edge yang saling berpotongan. Oleh karena

itu, graf G merupakan graf planar.

a b

cd

ef

gh

a b

e f

cd

gh

(a) (b)

Gambar 5.7.2 Dua graf untuk graf G contoh 5.7.1.

Contoh 5.7.2:

Graf lengkap Kn adalah suatu graf sederhana dengan n verteks dan setiap pasang verteks

dihubungkan dengan sebuah edge. Derajat pada setiap verteks adalah n-1.

K1 K2 K3 K4 K5

(a) (b) (c) (d) (e)

Gambar 5.7.3 Graf lengkap K1, K2, K3, K4, K5

Perisalah apakah graf lengkap (complete graph) K1, K2, K3, K4, K5 seperti pada Gambar 5.7.3

merupakan graf planar?.

Penyelesaian:

Terlihat pada Gambar 5.7.3 (a), (b), dan (c) bahwa pada graf lengkap K1, K2, K3 merupakan graf

planar karena tidak ada edge-edge yang berpotongan pada ketiga graf tersebut.

Sedangkan untuk graf lengkap K4 dapat dirubah menjadi gambar graf untuk K4 seperti Gambar

4.7.4 berikut ini.

Page 43: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 43

Gambar 5.7.4 Representasi planar untuk graf lengkap K4.

Untuk graf lengkap K5 bukan merupakan graf planar, ketidak-planaran suatu graf akan dibahas

dibelakang melalui beberapa teorema. Sekarang kita coba untuk menghindarkan perpotongan

antar edge-edge. Untuk memudahkan pembahasan edge-edge pada graf tersebut kita berilabel

seperti Gambar 5.7.5 (a).

e1

e2

e3

e4

e5 e

6

e7

e8

e9

e10

e1

e2

e3

e4

e5 e

6

e7

e8

e9

e10

e1

e2

e3

e4

e5

e6

e7

e8

e9

e10

e1

e2

e3

e4

e5

e6

e7

e8

e9

e10

(a) (b) (c) (d)

Gambar 5.7.5 Dua bentuk graf lengkap K5.

Edge e2 kita coba hindarkan dari berpotongan dengan edge e5 dan edge e6. Begitu juga untuk

edge e3 kita coba hindarkan dari berpotongan dengan edge e5 dan edge e8, menghasilkan suatu

gambar graf K5 Gambar 5.7.5 (b). Masih ada dua edge yang berpotongan, yaitu edge e6 dan

edge e8. Kita coba edge e6 dilewatkan keluar segmen garis edge e8, bisa keluar dari segmen

garis edge e8, akan tetapi akan memotong edge lain e2 atau e4, lihat gambar 5.7.5 (c) dan (d).

Oleh karena itu graf lengkap K5 tidak planar, begitu juga untuk graf lengkap Kn ( dengan n ≥ 5 )

bukan merupakan graf planar.

Definisi 5.7.2 Peta Dan Wilayah

Suatu Peta (map) adalah suatu representasi planar dari suatu multigraf. Jika multigraf dari peta

tersebut terhubung, maka peta tersebut dikatakan terhubung.

Sebuah peta membagi bidang menjadi beberapa wilayah (region). Wilayah satu dengan yang

lainnya dipisahkan oleh sederetan edge-edge yang mebentuk sirkuit/cycle dalam graf tersebut.

Derajat dari suatu wilayah r, deg(r), adalah panjang sirkuit yang membatasi wilayah r.

Page 44: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 44

Representasi planar untuk graf lengkap K4 pada Gambar 5.7.6 (a) dan (b) membagi bidang

menjadi 4 wilayah. Wilayah r1, r2, dan r3 adalah terbatas atau dibatasi oleh edge sekumpulan

edge-edge yang membentuk sikuit/cycle, sedangkan wilayah f4 adalah tak terbatas. Panjang

sirkuit r1, r2, r3, dan r4 masing-masing adalah 3, 3, 3, dan 3.

r1

r2

r3

r4

r1

r2 r

4

r3

(a) (b)

Gambar 5.7.6 Representasi planar K4 membagi bidang menjadi 4 wilayah.

Teorema 5.7.1. Jumlahan dari derajat semua wilayah dari suatu peta sama dengan dua kali

banyaknya edge pada peta tersebut.

Contoh 5.7.3:

Perhatikan peta pada Gambar 5.7.7. Graf tersebut memiliki edge sebanyak 9 buah edge dan

verteks sebanyak 6 buah verteks.

a

b

c

d

fe

r1

r2

r3

r4

r5

Gambar 5.7.7.

Peta tersebut terbagi kedalam wilayah dan batas wilayah berikut ini.

Wilayah Sirkuit Batas wilayah Panjang sirkuit = der (r)

r1 a-b-c-e-a 4

R2 b-c-d-b 3

R3 a-b-d-a 3

R4 c-d-e-c 3

R5 a-d-e-f-e-a 5

18

Page 45: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 45

Teorema 5.7.2. Persamaan Euler

Jika e menyatakan banyaknya edge, dan n menyatakan banyaknya verteks pada suatu map,

maka banyaknya wilayah (r) adalah r=e-n+2.

Contoh 5.7.4:

Perhatikan peta pada Gambar 5.7.6, banyaknya verteks n=4, dan e=6, maka banyaknya wilayah

adalah r=6-4+2=4. Dan pada peta Gambar 5.7.7, banyaknya wilayah adalah r=9-6+2=5.

Jika G merupakan multigraf terhubung planar yang memiliki 3 verteks atau lebih, dan

representasi planar dari G adalah H, maka:

i. Suatu wilayah di H mempunyai derajat 1 jika dan hanya jika batas wilayah tersebut adalah

sebuah loop. Lihat wilayah r3 pada Gambar 5.7.8.

r1

r2

r3

r5

r4

Gambar 5.7.8 Wilayah dengan derajat 1 dan 2.

ii. Suatu wilayah di H mempunyai derajat 2 jika dan hanya jika batas wilayah tersebut adalah

dua multiple edge. Lihat wilayah r5 pada Gambar 5.7.8.

Selanjutnya jika G adalah suatu graf, bukan merupakan multigraf, maka setiap wilayah ri di G mempunyai

derajat 3 atau lebih.

Teorema 5.7.3. Pertidaksamaan Euler

Jika G merupakan graf terhubung planar tidak punya loop dengan banyaknya verteks adalah n

dan banyaknya edge e adalah dua atau lebih, maka e ≤ 3n-6.

Bukti:

Page 46: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 46

Karena graf (bukan multigraf) terhubung planar dan tidak punya loop, setiap wilayah ri mempunyai

batas wilayah paling sedikit 3 edge, deg(ri)≥3, dengan i=1,2, …,r. Dan r menyatakan banyaknya wilayah

pada graf tersebut. Atau dengan kata lain jumlahan derajat dari semua wilayah paling sedikit adalah 3r,

sehingga didapat pertidaksamaan berikut ini.

rrr

i

i 3)deg(1

Brdasarkan teorema sebulumnya bahwa jumlahan derajat semua wilayah sama dengan 2 kali banyaknya

edge. Oleh karena itu didapt:

2e ≥3r

Substitusikan persamaan Euler r=e-n+2, didapat:

2e ≥3(e-n+2)

atau

e ≤3n-6

[Terbukti]

Untuk graf yang terhubung planar dan tidak punya loop, berlaku pertidaksamaan Euler. Sebagai

kontraposisi dari kalimat ini bahwa: untuk suatu graf terhubung, tidak punya loop, yang tidak

memenuhi pertidaksamaan Euler maka graf tersebut tidak planar. Ini bisa dipakai untuk

menentukan ketidak-planaran suatu graf yang terhubung dan tidak punya loop.

Contoh 5.7.5:

Perhatikan graf lengkap K5. Akan kita tunjukkan bahwa K5 tidak planar. Graf ini memenuhi

kriteria pada teorema 5.7.3. Banyaknya verteks n=5 dan banyaknya edge e=10, kalau kita

masukkan ke pertidaksamaan Euler didapat:

10 ≤3(5)-6 atau 10 ≤9

Hal ini tidak mungkin, oleh karena itu graf K5 tidak planar.

Teorema 5.7.4.

Jika G merupakan graf terhubung planar tidak punya loop dengan banyaknya verteks adalah n,

banyaknya edge e, dan tidak memuat sirkuit dengan panjang 3 maka e ≤ 2n-4.

Page 47: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 47

Bukti dari teorema ini mirp dengan bukti pada teorema sebelumnya, dan dipakai untuk latihan.

Contoh 5.7.6:

Perhatikan permasalahan tiga rumah (r1, r2, dan r3) dengan tiga utilitas sambungan listrik(l),

air (a), dan gas (g). Apa mungkin jalur sambungan dari 3 utilitas tersebut tidak saling

berpotongan?. Karena kalau saling berpotongan bisa membahayakan. Lihat Gambar 5.7.9 (a).

r1 r2 r3

g a l

(a) Tiga rumah dan tiga utilitas (b) Graf untuk tiga rumah tiga utilitas

Gambar 5.7.9.

Permasalahan tersebut dapat dinyatakan dalam bentuk graf Gambar 5.7.9 (b), apakah graf

tersebut planar?

Penyelesaian:

Dalam graf 5.7.9 (b) terdapat verteks sebanyak n=6, edge sebanyak e=9, dan tidak memuat

sirkuit dengan panjang 3. Oleh karena itu, graf ini memenuhi kriteria pada teorema 5.7.4. Kalau

kita masukkan ke dalam pertidaksamaan pada teorema 5.7.4 e ≤ 2n-4, didapat:

9 ≤ 2(6)-4 atau 9 ≤ 8

Hal ini tidak mungkin, oleh karena itu graf tersebut tidak planar.

Page 48: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 48

Soal Latihan

Graf Tak Berarah, Graf Berarah, Multigraf dan Graf Berbobot

1. Gambarkan graf tak berarah G=(V, E) dengan himpunan V dan E adalah:

a. V={1, 2, 3, 4, 5} dan E={{1,2}, {1,4}, {2,3}, {2,5}, {3,4}}

b. V={a, b, c, d, e, f} dan E={{a,b}, {a,e}, {a,f}, {b,c}, {b,d}}

2. Gambarkan graf berarah G=(V, E) dengan himpunan V dan E adalah:

a. V={1, 2, 3, 4, 5} dan E={(1,2), (1,4), (2,1), (2,2), (2,5), (3,4), (4,5), (5,4)}

b. V={a, b, c, d, e, f} dan E={(a,b), (a,e), (a,f), (a,e), (b,a), (b,d), (e,f)}

c. V={Cengkareng, Juanda, Polonia, Hasanudin, NgurahRai, Panarung}

E={(Cengkareng,Juanda), (Juanda,Cengkareng), (Cengkareng, Polonia),

(Polonia, Cengkareng), (Juanda, NgurahRai), (NgurahRai, Juanda),

(Juanda, Hasanuddin), (Hasanuddin, Juanda), (NhurahRai, Hasanuddin),

(Hasanuddin, NgurahRai), (Hasanuddin, Panarung), (Panarung, Hasanuddin)}

3. Perhatikan gambar graf berikut ini

a b

cd

e

a b

d e

e1

e2

e3

e4e

5

e6

c

f

e9

e7

e8

(a) (b)

Tuliskan graf tersebut dalam bentuk G=(V, E).

4. Untuk graf pada soal nomor 3 (a), apakah

a. Verteks a adjacent dengan verteks b ?.

b. Verteks a adjacent dengan verteks c ?.

c. Verteks a adjacent dengan verteks d ?.

d. Verteks a adjacent dengan verteks e ?.

Jeslakan alasannya!.

5. Untuk graf pada soal nomor 3 (b), apakah

a. Edge e1 incident dengan verteks a dan b ?.

b. Edge e1 incident dengan verteks b dan a ?.

c. Verteks a incident dengan verteks c ?.

d. Edge e1 incident dengan Edge e2 ?.

Page 49: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 49

e. Verteks a adjacent dengan edge e1 ?.

Jelaskan alasannya !.

6. Untuk graf pada soal nomor 3, hitunglah derajat setiap verteks dan bagaimana hubungan

jumlahan derajat verteks dan banyaknya verteks.

7. Perhatikan gambar graf berbobot berikut ini

a b

d c

3

5

2

44

5

a b

d e

1

2 34

3

c

f

2

5

4

(a) (b)

Tuliskan graf tersebut dalam bentuk G=(V,E).

8. Tentukan derajat masuk, derajat keluar, dan derajat dari setiap verteks pada graf berikut ini.

a b

d c

9. Dalam suatu seleksi bulu tangkis tunggal putra menggunakan sistem setengah kompetisi,

Agus mengalahkan Bedu dalam dua set langsung, Bedu mengalahkan Candra dalam 3 set,

Agus mengalahkan Candra dalam 2 set, Candra mengalahkan Deni dalam 2 set, Deni

mengalahkan Agus dalam 3 set, dan Deni mengalahkan Bedu dalam 3 set. Gambarkan

pertandingan ini dengan menggunakan graf berarah berbobot.

10. Buatlah gambaran dalam bentuk graf dari hubungan antar Kota/Kabupaten di Propinsi

tempat anda berada, hubungan antar kota/kabupaten diberikan bobot yang menyatakan:

a. Jarak dari kedua kota/kabupaten.

b. Lamanya perjalanan dari kota/kabupaten ke kota/kabupaten lain.

c. Biaya perjalanan antar kota/kabupaten.

Lintasan dan Sirkuit

11. Untuk graf tak berarah dan tak berbobot pada gambar berikut ini

Page 50: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 50

a b

d e

e1

e2

e3

e4e

5

e6

c

f

e9

e7

e8

Carilah:

a. Lintasan dari a ke d yang panjangnya masing-masing 1, 2, 3, dan 6?

b. Lintasan dasar dari c ke b yang panjangnya 3?

c. Lintasan sederhana dari c ke b yang panjangnya 3?

d. Sirkuit dasar dari a ke a yang panjangnya 4 ?.

e. Sirkuit dasar dari a ke a yang panjangnya 7?.

f. Sirkuit sederhana dari a ke a yang panjangnya 4 ?.

g. Sirkuit sederhana dari a ke a yang panjangnya 7?.

12. Untuk graf tak berarah dan tak berbobot pada gambar berikut ini

a b

cd

e

Carilah:

a. Lintasan dari a ke d yang panjangnya masing-masing 1, 2, 3, dan 6?

b. Lintasan dasar dari c ke b yang panjangnya 4?

c. Lintasan sederhana dari c ke b yang panjangnya 4?

d. Sirkuit sederhana dari a ke a yang panjangnya 5?

e. Sirkuit sederhana dari a ke a yang panjangnya 3?

13. Untuk graf berarah dan tak berbobot pada gambar berikut ini

a b

d c

Carilah:

a. Lintasan dari a ke d yang panjangnya masing-masing 1, 2, 3, dan 6?

Page 51: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 51

b. Lintasan dasar dari c ke b yang panjangnya 3?

c. Lintasan sederhana dari c ke b yang panjangnya 3?

d. Sirkuit sederhana dari a ke a yang panjangnya 4?

e. Sirkuit sederhana dari a ke a yang panjangnya 4?

14. Perhatikan gambar graf berbobot berikut ini

a b

d e

1

2 34

3

c

f

2

5

4

Carilah beberapa:

a. Lintasan dari a ke d dan tentukan panjangnya?

b. Lintasan dasar dari c ke b dan tentukan panjangnya?

c. Lintasan sederhana dari c ke b dan tentukan panjangnya?

d. Sirkuit sederhana dari a ke a dan tentukan panjangnya?

e. Sirkuit sederhana dari a ke a dan tentukan panjangnya?

15. Perhatikan gambar graf berarah dan berbobot berikut ini

a b

cd

3

2

7

34

6

Carilah beberapa:

a. Lintasan dari a ke d dan tentukan panjangnya ?.

b. Sirkuit dari a ke a dan tentukan panjangnya ?.

c. Apakah vertek u dan d terhubung kuat ?.

d. Apakah graf di atas terhubung kuat ?.

Lintasan Euler dan Hamilton

16. Perhatikan graf berikut ini

a. Dapatkan lintasan Euler ?

b. Dapatkan sirkuit Euler ?

c. Apakah merupakan Eulerian atau Semi Eulerian graf ?.

a

bd

ec

Page 52: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 52

17. Carilah lintasan dan sirkuit Euler pada graf berikut ini.

a

b d

e

f

c

18. Tunjukkan bahwa graf berikut ini mempunyai Sirkuit Hamilton.

19. Graf pada soal nomor 17, apakah mempunyai Sirkuit Hamilton?.

20. Buatlah suatu graf yang mempunyai sifat:

a. Mempunyai Sirkuit Euler dan Sirkuit Hamilton.

b. Mempunyai Sirkuit Euler dan tidak mempuyai Sirkuit Hamilton.

c. Tidak mempunyai Sirkuit Euler dan mempunyai Sirkuit Hamilton.

d. Tidak mempunyai Sirkuit Euler dan Sirkuit Hamilton.

Lintasan Terpendek

21. Gambar graf berikut ini mewakili hubungan antar komputer dalam suatu jaringan komputer

di devisi Marketing dari sebuah perusahaan.

Verteks mewakili sebuah komputer dan edge menyatakan

jalur komunikasi, sedangkan bobot pada edge menyetakan

lamanya (dalam detik) tranfer data per 1 Kbyte. Pada setiap

sore hari komputer a mengirim sebuah file ke semua

komputer yang lain. Dapatkan waktu tercepat pada setiap

komputer.

a

b d

c

e

f g

h

2

36

5

23

4

7 3

5 3

7

Page 53: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 53

22. Gunakan algoritma Dikjstra untuk mendapatkan lintasan terpendek dari verteks a ke vertek

f pada graf berikut ini.

a b

d e

1

2 34

3

c

f

2

5

4

23. Gunakan algoritma Dikjstra untuk mendapatkan lintasan terpendek dari verteks a ke vertek

z pada graf berikut ini.

b f

c g

1

2

2

j

k

5

1

d h

e i

l

m

a z2

2

3

2

1

4

3

2

4

3

2

3

2

3

3

3

3

2

3

1

3

2

3

1

3 2

24. Gunakan algoritma Dikjstra untuk mendapatkan lintasan terpendek dari verteks a ke setiap

verteks pada graf nomor 2.

25. Gunakan algoritma Dikjstra untuk mendapatkan lintasan terpendek dari verteks a ke vertek

z pada graf berikut ini.

2

-1

5

8

-53

4

6

a

b

c

d

d

z

2

Subgraf, Graf Isomorpik

26. Tuliskan dua buah subgraf dari graf G=({a,b,c,d},{{a,b},{a,d},{b,c},{c,d}) ?.

27. Dapatkan dua buah subgraf yang mempunyai verteks {1,2,3,4} dari graf

G=({1,2,3,4},{{1,2},{1,4},{2,3},{3,4}) ?.

Page 54: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 54

28. Dapatkan 4 subgraf yang memuat 10 verteks dari graf berikut ini.

29. Apakah graf G1 dan G2 berikut ini isomorpik ?. Berikan alasan.

a. G1=({a,b,c,d},{{a,b},{a,d},{b,c},{c,d}}) dan G2=({1,2,3,4},{{1,2},{1,4},{2,3},{3,4}}) ?

b. G1=({a,b,c,d,e},{{a,b},{a,d},{b,c},{c,d},{e,a}) dan

G2=({1,2,3,4,5},{{1,5},{2,3},{2,5},{3,4},{4,5}}) ?

30. Apakah graf G1 dan G2 berikut ini isomorpik ?. Berikan alasan.

a.

1 4

2

a b

d c

G1

G2

3

b.

A C

D

a b

d c

G1

G2B

c.

G1

G2

d.

Page 55: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 55

G1 G

2

Graf Planar

31. Tunjukkan bahwa graf G=({a,b,c,d},{{a,b},{a,d},{b,c},{c,d}) merupakan graf planar?

32. Tunjukkan bahwa graf G=({a, b, c, d, e, f, g}, E) merupakan graf planar? Dimana

himpunan edge E = {{a,b}, {a,d}, {a,e}, {b,c}, {b,f}, {c,d}, {c,g}, {e,f}, {f,g}}.

33. Apakah graf berikut ini merupakan graf planar?. Berikan alasan.

34. Apakah setiap graf planar merupakan suatu peta ?.

35. Suatu graf yang bukan multigraf biasa disebut juga graf linear. Tunjukkan bahwa graf

planar linear mempunyai verteks yang berderajat tidak lebih dari 4.

36. Tunjukkan bahwa pada graf planar linear dan terhubung yang mempunyai 6 verteks dan 12

edge, wilayahnya dibatasi oleh 3 edge.

Page 56: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 56

DAFTAR PUSTAKA:

1. GRIMALDI, R.P., “Discrete and Combinatorial Mathematics - An Applied

Introduction”, Addison-Wesley Publishing Co., 1989.

2. Liu, C.L., “Elements Of Discrete Mathemathics”, McGraw-Hill, 1986.

3. ROBERT, F.S., “Applied Combinatorics”, Prentice-Hall Inc., 1984.

4. ROSEN, K.H., “Discrete Mathematics and Its Applications”, McGraw-Hill, 2003.

5. Seymour L., Marc L.L., “Schaum’s Outline of Theory and Problems of Discrete

Mathematics”, Second Edition. McGraw-Hill, 1997.

Page 57: Modul 5 Teori Graf

Oleh: Bandung Arry Sanjoyo 57