Minggu ke V DEFINISI JALUR, LINTASAN, DAN SIRKUIT GRAF. Suatu trayek yang semua sisinya berbeda disebut jalur (trail). Sedangkan suatu jalur yang semua simpulnya berbeda disebut lintasan (path). Suatu trayek, jalur, atau lintasan disebut tertutup kalau simpul awal sama dengan simpul akhir. Lintasan tertutup biasanya disebut sirkuit. Sedangkan sirkuit dengan panjang tiga disebut segitiga
z
Pada gambar 5.1 trayek v w y v z y x adalah jalur karena simpul v dan y muncul dua kali, sedangkan trayek u v w y x tidak mengandung simpul
y
u
x v
w
Gambar 5.1
berulang, sehingga merupakan lintasan. Selanjutnya trayek tertutup u v w y v z u adalah jalur tertutup, tetapi bukan sirkuit karena simpul v terulang dua kali. Akan tetapi jalur tertutup seperti z z , v w y z v dan v y x w v adalah. Suatu sirkuit yang panjangnya tiga
seperti pada w x y w atau v z y v merupakan segitiga. Dalam merinci suatu trayek kita dapat mempertukarkan kedudukan simpul awal dan simpul akhir dan membalik susunan sisinya karena arahnya tidak dipersoalkan, misalnya trayek u v w identik dengan w v u . Akibatnya rincian sisi-sisi trayek tertutup dapat dimulai dari sembarang simpulnya, misalnya segitiga w x y w dapat dicatat sebagai x y w x , w y x w , x w y x , dan masih ada lagi yang lain (sebutkan).
Apabila untuk dua simpul sembarang pada suatu graf selalu dapat dibuat lintasan yang menghubungkan keduanya, maka graf tersebut disebut graf terhubung. Dengan demikian semua graf yang telah diulas pada pasal-pasal sebelumnya adalah graf terhubung. Sekarang bayangkan terjadi bencana alam yang menghancurkan jembatan-jembatan dan jalan yang menghubungkan tempat B dan C dan C dengan D pada Gambar 4.5. Tampak bahwa daerah C menjadi terpencil karena tidak dapat berkomunikasi dengan daerah lainnya. Dalam hal ini sisi grafnya menjadi berkurang dua buah, sedangkan banyaknya simpul tetap seperti semula. Graf terakhir ini menjadi graf terputus. Banyak sekali situasi semacam ini yang biasa dijumpai, misalnya hambatan/gangguan pada jaringan telekomunikasi atau komunikasi antar kelompok jaringan komputer, jaringan distribusi aliran listrik, dan air minum. DEFINISI GRAF TERHUBUNG. Suatu graf G disebut terhubung jika untuk setiap dua simpul sembarang v dan w di G ada lintasan (path) dari v ke w. Dalam hal lainnya, G disebut terputus. 24
Kiranya jelas graf terputus mempunyai paling sedikit dua graf-bagian terhubung; masingmasing graf-bagian ini disebut komponen graf terputus itu. Misalnya graf pada Gambar 5.2 mempunyai dua komponen. Dari Gambar 5.2 dapat diamati bahwa himpunan simpul-simpul graf terputus dapat disekat menjadi dua himpunan yang saling menyisihkan sedemikian sehingga kedua simpul ujung setiap sisinya selalu merupakan anggota himpunan bagian yang sama. Kedua himpunan ini ialah X a,b,c dan
Y t,u,v,w,
dengan
X Y
c
a
v
b
t
w
u
dan
Gambar 5.2. G = (V, E) terputus, V = XY, X X Y V dan tidak ada sisi berbentuk {p,q} Y = , X = {a, b, c}, Y = {t, u, v, w} dengan p X dan q Y. Oleh karena itu dapat diperlihatkan teorema berikut. TEOREMA 5.1. Suatu graf G = (V, E) adalah terputus jika dan hanya jika himpunan simpul V dapat disekat menjadi dua himpunan bagian saling menyisihkan dan tidak kosong. X dan Y, sedemikian sehingga tidak ada sisi yang satu simpul ujungnya anggota X dan simpul ujung yang lain anggota Y. Sebagai akibat Teorema 5.1 dan Teorema 1.1 maka diperoleh teorema berikut : TEOREMA 5.2. Jika suatu graf mempunyai tepat dua simpul berderajat ganjil, maka ada lintasan yang melalui kedua simpul tersebut. Misalnya pada Gambar 5.2 d(t) = d(w) = 1 dan lintasannya ialah t u v w . Bencana alam yang menyebabkan hancurnya sarana perhubungan antara C dan B dan D dengan C tidak dengan sendirinya menghancurkan kota C pada Gambar 4.5. Dengan demikian penghapusan sisi-sisi suatu graf tidak menyebabkan simpul-simpul yang hadir pada sisi itu terhapus. Akan tetapi hancurnya sebuah kota dengan sendirinya menyebabkan tidak berfungsinya sarana perhubungan yang melalui kota tersebut; misalnya porak-porandanya kota B akibat perang yang melumpuhkan jalan AB, BC, BD dan BE. Oleh karena itu penghapusan simpul suatu graf menyebabkan semua sisi yang bertemu dengan simpul itu juga terhapus. DEFINISI PENGHAPUSAN SISI DAN SIMPUL GRAF (1) Jika e suatu sisi sembarang pada graf G = (V, E), maka G – e adalah grafbagian G yang diperoleh dengan menghapus sisi e dari G (2) Jika v suatu simpul sembarang pada graf G = (V, E), maka G – v adalah graf-bagian G yang diperoleh dengan menghapus v dan semua sisi yang mencakup v sebagai suatu simpul ujungnya. 25
Apabila graf G pada Gambar 5.3 merupakan model sistem jaringan listrik dengan simpul mewakili gardu listrik dan sisi mewakili jalur kabelnya, maka rusaknya gardu v dicerminkan oleh graf G – v. Sedangkan terputusnya jalur kabel e dicerminkan oleh graf G – e. Dari Gambar 5.3 dapat diamati bahwa kerusakan pada kabel e tidak mengganggu kelancaran arus listrik antar gardu. Akan tetapi kerusakan pada tiga kabel, yaitu e, e1 dan e2 menyebabkan jaringannya tidak berfungsi. Oleh karena itu pengertian keterhubungan graf dapat ditafsirkan sebagai banyaknya sisi yang harus dihapus dari suatu graf terhubung agar diperoleh graf terputus. Ada dua pengertian dasar yang dimanfaatkan dalam membahas konsep tersebut. y u
y
e e1
x
u
y x
.
z
u
x
z
z
u2 v
w
w
v
G–v
G = (V, E)
w
G–e
Gambar 5.3 DEFINISI HIMPUNAN PEMUTUS DAN HIMPUNAN PEMISAH, Misalkan G = (V, E) merupakan sembarang graf terhubung. (1) Himpunan E1, yang merupakan himpunan bagian E, disebut himpunan pemutus graf G jika dan hanya jika graf-bagian G1 = (V, E – E1) merupakan graf terputus. (2) Himpunan pemutus yang tidak mempunyai himpunan bagian yang merupakan himpunan pemutus disebut himpunan pemisah (himpunan pemutus minimal). Dengan perkataan lain suatu himpunan pemutus graf terhubung G adalah himpunan sisi-sisi graf G yang dapat dihapus sehingga G menjadi graf terputus. Misalnya, pada Gambar 5.4, E1 = {e3, e6, e7, e8} merupakan himpunan pemutus G; graf terputus yang diperoleh dengan cara menghapus semua sisi yang terdapat pada himpunan E2 diperlihatkan pada Gambar 5.5. Dalam hal ini E1 bukan merupakan himpunan pemisah karena ada himpunan bagian E1 yang juga merupakan himpunan pemutus G, yaitu E11 = {e1, e2}. Selanjutnya mudah diperiksa bahwa E2 merupakan himpunan pemisah G. Jika himpunan pemisah hanya mencakup satu sisi, maka sisi ini disebut jembatan seperti tampak pada Gambar 5.6. y e1
e5 e2
u
e3 e6
y
x e7
e8 v Gambar 5.4
e4
e1
x e5
e4
e2 w
u 26
v Gambar 5.5
w
e w
v
E = {v, w} adalah jembatan Gambar 5.6 Jelas bahwa himpunan pemutus sembarang graf G (boleh graf terputus) adalah himpunan sisi-sisi graf G. Akan tetapi pengertian himpunan pemisah adalah sama seperti yang telah diuraikan sebelumnya. Dalam hal ini perlu disadari bahwa penghapusan semua sisi anggota himpunan pemisah graf G mengakibatkan banyaknya komponen G selalu bertambah satu buah. Soal-soal Latihan (1) Periksalah apakah trayek-trayek yang diberikan merupakan jalur, lintasan, atau sirkuit pada graf berikut. Tentukanlah panjang, simpul awal dan simpul akhirnya
x wv y w v
x y z u v z z u z v v y
w
u
u v w x y w y
x z
y w z u v y
y w
w v y x w
(2) Perhatikanlah graf di samping ini e5
Tentukanlah suatu jalur (trail) dengan panjang 5 dan 6
v4
Tentukanlah suatu lintasan (path) dengan panjang 1, 2, dan 3
v2
e1
v1
Tentukanlah suatu trayek (walk) dengan panjang 7 dan 8
e3 e4
e8
e2 e6 e7
v3
Tentukanlah suatu sirkuit dengan panjang 1, 2, 3, dan 4. (3) Daftarkanlah semua lintasan antara simpul x dan u pada graf di samping ini. Berapakah panjang lintasannya yang terpendek dan terpanjang ? Ada berapa banyak masing-masing lintasan tersebut ?.
z w
u y
x (4) Pada graf di samping ini tentukanlah suatu trayek tertutup yang bukan jalur tertutup, dan suatu jalur tertutup yang bukan sirkuit.
t t
s
w x
u v
27
v
s
y
z
(5) Periksalah apakah himpunan berikut inimerupakan himpunan pemutus atau himpunan pemisah bagi graf di samping ini. a) {su, sv, uv}
u
w
y t
s
b) {ux, uw, wx, xz} v
c) {yt, yz}
x
z
d) {xz, xw, uw} e) {wy, wx, yz} f) {su, uv, wx, yz, vx}
(6) Amatilah graf Petersen pada soal latihan 7 halaman 21 ! Tentukanlah semua trayek yang panjangnya 4 ! Tentukanlah sirkuit dengan panjang 5, 6, 8, dan 9 .! Tentukanlah semua lintasan yang panjangnya 5.! Tentukanlah himpunan pemisah yang mempunyai 3 dan 5 sisi .!. (7) Berikan contoh graf terhubung yang menjadi terputus apabila suatu simpul sembarang dihapus. Tafsirkanlah maknanya apabila graf ini merupakan model bagi hubungan persahabatan antar manusia. (8) Jelaskan apakah ada graf terhubung G dengan n simpul dan n sisi serta mempunyai jembatan. (9) Jelaskan bahwa suatu jembatan pada graf terhubung G tidak mungkin merupakan sisi sirkuit G. (10) Misalkan a, b, dan c adalah tiga buah simpul berbeda pada graf G. Jika ada lintasan dari a ke b dan dari b ke c, perlihatkan bahwa ada lintasan dari a ke c.!. (11) Jelaskan bahwa banyaknya sisi pada sembarang graf sederhana yang terhubung dengan n simpul dan m sisi memenuhi ketaksamaan n – 1 m ½n(n - 1).! (12) Jelaskan bahwa graf terhubung G = (V, E) dengan n simpul mempunyai lintasan yang panjangnya tidak lebih dari n – 1. Tafsirkanlah maknanya apabila graf ini mewakili penyebaran gosip di antara ibu-ibu rumah tangga.! (13) Jelaskan bahwa jika banyaknya sisi suatu graf melebihi banyaknya simpul, maka graf itu mempunyai sirkuit.! (14) Jelaskan bahwa jika banyaknya sirkuit jika setiap simpulnya berderajat tidak kurang dari dua.!
28
(15) Jelaskan ada berapa komponen pada graf di bawah ini. Daftarkan pula simpul-simpul masing-masing komponennya. Susun pula matriks ikatan dan matriks kehadiran masingmasing graf; adakah hal yang istimewa ?. v5 a c (a) (b) v6 v4 b x u v
w dv
v3
v1 v2 (c)
(d)
v1 v2
.x
v3
z d
v6 a
v7
t
v4
x
v b
c
u
w
v5 (16) Daftarkanlah himpunan pemisah yang banyak anggotanya minimum pada graf-graf berikut.! 1 3
2
4
5
1 2
6
7
4
2
7
3 6
6
5 3
1
8
7
4 5
8 (17) Hitunglah panjang setiap sirkuit pada graf bipartit lengkap K2,3, K3,3 dan K4,3. Adakah hal yang istimewa ?.
29
