Minggu ke I 1.1 Pemodelan dengan Graf Dalam pengertian umum model merupakan gambaran sederhana dalam dimensi lebih kecil dari objek yang diwakilinya, misalnya: model rumah, mobil atau pesawat terbang. Dalam nuansa ini gagasan manusia merancang peta sebagai pencerminan sederhana keadaan geografi lingkungannya dapat dianggap sebagai pemodelan. Pada hakekatnya pemodelan dengan graf serupa dengan pembuatan peta, dan diperkenalkan berikut ini. Pada Gambar 1.1 dan 1.2 disajikan jaringan listrik dan denah jalan sekitar lokasi A, B, C, D dan E. A
B
A
B
C E
C
D
E
D
Gambar 1.1
Gambar 1.2
Tanpa mengubah strukturnya bentuk hubungan aliran listrik dan jalan yang ada di antara ke lima lokasi tersebut dapat disederhanakan menjadi salah satu di antara diagram titik dan garis pada gambar 1.3. Dalam hal ini lokasi diwakili oleh titik dan keterhubungannya diwakili oleh garis yang menghubungkan sepasang titik. A
A
B
B
C E
D (a)
B C
E
A
D (b)
C
E (c)
D
Gambar 1.3 Ketiga diagram pada gambar 1.3 disebut graf dan diperlakukan sebagai model bagi jaringan listrik dan denah jalan. Titik-titik A, B, C, D dan E disebut simpul dan garis-garis yang menghubungkan sepasang simpul disebut sisi. Naluri kita dapat menerima bahwa struktur ketiga graf ini identik. Oleh karena itu perpotongan antara garis AD dan BE pada Gambar 1.3 (a) bukan merupakan simpul pada graf. Derajat simpul menyatakan banyaknya sisi yang bertemu pada simpul tersebut, misalnya: derajat simpul C dan A, masing-masing ialah 2 dan 3, serta ditafsirkan sebagai banyaknya cabang aliran listrik atau persimpangan jalan di lokasi yang sepadan dengan simpul ini.
1
Di samping itu graf pada Gambar 1.3 dapat pula menjelaskan situasi yang lain. Misalnya A, B, C, D dan E mewakili nama-namagrup bola basket, maka sisi mencerminkan kedua grup yang sepadan dengan sisi itu sudah saling bertanding dan derajat simpul mencerminkan banyaknya pertandingan yang telah dilakukan oleh grup yang sepadan dengan simpul tersebut. Dari diagram ini terungkap, antara lain A dan C belum saling bertanding, B dan D telah menyelesaikan seluruh pertandingan, C baru bertanding dua kali. Andaikan sekarang jalan yang menghubungkan tempat B dan D pada Gambar 1.3 terlalu sarat dengan kendaraan sehingga lalu-lintasnya sering macet. Salah satu penyelesaiannya ialah dengan membangun jalan baru yang menghubungkan kedua tempat tersebut. Salah satu model grafnya diperlihatkan pada Gambar 1.4. Kedua sisi yang menghubungkan simpul B dengan D disebut ya sisi ganda. Apabila selanjutnya diinginkan pula membangun tempat parkir di lokasi A, maka hal demikian dapat pula dinyatakan oleh graf dengan menggambar sebuah sisi yang berasal dari A ke dirinya sendiri. Sisi semacam ini disebut gelang seperti tampak pada Gambar 1.5 dan dianggap berderajat 2. B B A
A
C
E D Gambar 1.4
C
E D Gambar 1.5
Jalan satu arah seringkali juga merupakan alternatif pemecahan dalam masalah lalu-lintas. Dengan demikian diperlukan graf berarah atau disingkat digraf; misalnya seperti diperlihatkan pada Gambar 1.6 (tanda panah menyatakan arah lalu-lintas). Dalam hal jalan antara B dan D boleh dua arah, kita dapat menyusun digrafnya dengan menggambar dua sisi berarah, yang masing-masing mempunyai arah berlawanan seperti tampak pada Gambar 7. Sisi berarah biasanya disebut busur. Dalam bidang sosiologi digraph dikenal dengan sebutan sosiogram dan digunakan untuk mengkaji struktur sosial suatu masyarakat atau kelompok. Individu-individu diwakili oleh simpul-simpul, sedangkan busur-busurnya yang mencerminkan hubungan antar-individu, dapat ditafsirkan sebagai, misalnya “mempengaruhi”, “menguasai”, “mengagumi” atau “mengendalikan”. B A
B C
E
A
D
C
E D
Gambar 1.6
Gambar 1.7 2
1.2 Konsep Dasar Graf Dari kajian dalam Pasal 1, terungkap bahwa satu graf dapat merupakan model bagi lebih dari satu macam masalah. Selain itu ketiga diagram pada Gambar 1.3 sesungguhnya mempunyai struktur yang identik dalam pengertian diagram yang satu dapat diperoleh dari diagram yang lain melalui penempatan kembali simpul-simpul dan/atau sisi-sisinya. Dengan perkataan lain ketiga diagram merupakan sajian geometrik dari satu graf. Oleh karena itu, kita perlu mendefinisikan graf yang lepas dari sajian geometriknya. Pada dasarnya diagram simpul sisi pada setiap gambar yang telah dipaparkan dapat dibuat setelah kita mengetahui simpul-simpulnya dan sisi-sisinya yang menghubungkan sepasang simpul. Misalnya: ketiga diagram pada Gambar 1.3 mempunyai himpunan simpul dan sisi yang identik, yaitu {A, B, C, D, E} dan {AB, AD, AE, BC, BD, CD, DE}. Oleh karena itu suatu graf hanya dicirikan oleh daftar simpul-simpulnya dan sisinya dan bukan oleh bentuk sajian geometriknya. DEFINISI, Graf, dilambangkan dengan G= (V, E), terdiri atas dua himpunan terhingga V dan E. Himpunan V bukan himpunan kosong dan unsur-unsurnya disebut simpul, sedangkan unsur-unsur himpunan E disebut sisi, sedemikian sehingga setiap sisi menghubungkan dua simpul, yang dinamakan simpul ujung sisi tersebut. Simpul biasanya dilambangkan dengan huruf-huruf u, v, w atau v1, v2, …, meskipun adakalanya dengan n bilangan asli pertama, 1, 2, …. Sisi dilambangkan dengan e1, e2, …, atau dengan kedua simpul ujungnya, misalnya {u, v} atau {v, u}, {v1, v3} atau {v3, v1}. Pada Gambar 1.8 disajikan bentuk geometrik graf G= {V, E} dengan 5 simpul dan 7 sisi. Himpunan simpulnya V = {v1, v2, v3, v4, v5} dan himpunan sisinya E = {e1, e2, e3, e4, e5, e6, e7}. V1
e1
e3
e5 e4
V3 V5
e6 e7
e2 V2
V4 Gambar 1.8
Dalam definisi graf ini telah tercakup kemungkinan adanya sisi-ganda, yaitu beberapa sisi yang menghubungkan sepasang simpul; graf semacam ini disebut graf ganda. Selain itu ada pula sisi yang menghubungkan sebuah simpul dengan dirinya sendiri; sisi semacam ini disebut gelang. Graf G= (V, E) yang tidak mempunyai sisi-ganda dan gelang disebut graf-sederhana, misalnya graf pada Gambar 1.3.
3
Dalam beberapa ulasan selanjutnya kita memanfaatkan Gambar 1.8 sebagai teladan. Dua buah simpul sembarang v dan w disebut berikatan kalau kedua simpul ini merupakan simpul ujung suatu sisi e. Dalam hal ini simpul v dan w disebut hadir pada sisi e. Misalnya simpul v4 berikatan dengan simpul v5, tetapi tidak demikian halnya dengan simpul-simpul v1 dan v4; simpul v4 hadir pada sisi-sisi e2, e6, e7. Sisi-sisi yang bukan sisi-ganda disebut berikatan kalau keduanya mempunyai satu simpul persekutuan; misalnya sisi e2 dan e7. Banyaknya sisi yang bertemu pada simpul v disebut derajat simpul v, dilambangkan dengan d(v). Dalam hal ini dibuat kesepakatan bahwa setiap gelang dianggap berderajat dua. Selain itu simpul yang berderajat nol disebut simpul terpencil dan simpul yang berderajat satu disebut simpul terminal. Misalnya graf pada Gambar 1.8 memiliki satu simpul berderajat 1, tiga simpul berderajat 3, dan satu simpul berderajat 4. Apabila kita jumlahkan derajat semua simpul graf tersebut akan diperoleh d(v1) + d(v2) + d(v3) + d(v4) + d(v5) = 3 + 4 + 3 + 3 + 1 = 14 = 2(7) = 2 x banyaknya sisi graf G. Sifat demikian untuk graf sembarang sudah diketahui oleh Euler lebih dari dua ratus tahun yang lalu, dan dikenal sebagai Lemma Persalaman. Dikatakan demikian karena apabila ada beberapa orang saling bersalaman, jelas kiranya banyaknya tangan yang bersalaman haruslah genap, tepatnya ada dua tangan pada setiap salaman. Jadi dapat disimpulkan lemma (teori “kecil”) berikut : LEMMA PERSALAMAN. Untuk sembarang graf dengan n simpul dan m sisi berlaku sifat berikut n
d( vi ) 2.m
i 1
Himpunan simpul V dapat disekat menjadi dua himpunan yang saling menyisihkan (saling lepas), X dan Y, masing-masing merupakan himpunan simpul-simpul berderajat genap dan berderajat ganjil. Karena jumlah derajat simpul-simpul di X merupakan bilangan genap, katakanlah 2p, maka dengan Teorema 1.1 haruslah jumlah derajat simpul-simpul di Y juga bilangan genap, yaitu 2(m-p). Akan tetapi setiap simpul v di Y berderajat ganjil, maka haruslah banyaknya simpul di Y (banyaknya bilangan yang dijumlahkan) itu genap agar jumlahnya menghasilkan bilangan genap. Dengan demikian diperoleh teorema berikut sebagai akibat Lemma 1. TEOREMA 1.1. Banyaknya simpul berderajat ganjil dalam Graf G= (V, E) selalu merupakan bilangan genap.
4
Graf pada Gambar 1.8 mempunyai empat simpul berderajat ganjil, masing-masing ialah v1, v3, v4, dan v5. Contoh 1.1. Graf pada gambar di samping ini mempunyai 6 simpul dan 7 sisi. Derajat masing-masing simpulnya ialah d(v2) = d(v3) = 3, d(v2) = 5, d(v4) = 2, d(v5) = 1, dan d(v6) = 0. Dalam hal ini v5 merupakan simpul terpencil; banyaknya simpul berderajat ganjil ada 4 buah (bilangan genap); jumlah derajat semua simpulnya sama dengan 14 atau 2 kali banyaknya sisi, yaitu 7 buah.
V1
V4 V5 V2
• V6
V3
Sekarang kita akan sedikit mengulas makna yang agak cermat tentang dua graf dikatakan mempunyai struktur identik seperti diteladankan pada Gambar 1.3. Dalam istilah teori graf keadaan ini disebut isomorfik. Istilah ini berasal dari bahasa Yunani: iso bermakna “sama” dan morphe bermakna “struktur”. DEFINISI. Misalkan G = (V, E) merupakan graf dengan V = {v1, v2, …, vn }. Graf G’ = (V’, E’) dikatakan isomorfik dengan G, jika kita dapat memberi nama simpul-simpul di G’ dengan v1’, v2’, …, vn’ sedemikian sehingga (1) Setiap simpul di G’ hanya mempunyai satu dan hanya satu nama (2) Jika dua simpul berbeda vi dan vj di G terhubungkan oleh k(k >1) sisi, maka demikian pula halnya dengan simpul-simpul padanannya vi’ dan vj’. (3) Jika dua simpul berbeda vi’dan vj’ di G tidak terhubungkan oleh suatu sisi, maka demikian pula halnya dengan simpul-simpul padanannya vi’ dan vj’. Jika persamaan ini tidak dimungkinkan, maka G dan G’ tidak isomorfik. Sebagai akibatnya diperoleh teorema berikut TEOREMA 1.2. Jika G dan G’ dua graf isomorfik dan vi di G berpadanan dengan vi’ di G’, maka d(vi) = d(vi’). Contoh 1.2. Periksa apakah penamaan simpul pada G dan G’ pada Gambar 1.9 memperlihatkan keduanya isomorfik. V2
V3
V’4 V’5
V1 V5
V’3
V4 Gambar 1.9 5
V’2
V’1
Penyelesaian. Dalam hal ini harus diperiksa apakah banyaknya sisi yang menghubungkan pasangan simpul-simpul vi dan vj di G sama dengan banyaknya sisi yang menghubungkan pasangan simpul-simpul vi’ dan vj’ di G’. Hasil pemeriksaan tercantum dalam tabel berikut : Simpul-simpul di G v1 dan v2 v1 dan v3 v1 dan v4 v1 dan v5 v2 dan v3 v2 dan v4 v2 dan v5 v3 dan v4 v3 dan v5 v4 dan v5
Banyaknya sisi di G 1 0 0 0 1 0 1 2 0 1
Simpul-simpul di G’ v1’ dan v2’ v1’ dan v3’ v1’ dan v4’ v1’ dan v5’ v2’ dan v3’ v2’ dan v4’ v2’ dan v5’ v3’ dan v4’ v3’ dan v5’ v4’ dan v5’
Banyaknya sisi di G’ 1 0 0 0 1 0 1 2 0 1
Karena kolom 2 dan 4 identik, maka G dan G’ isomorfik. Selain itu kebenaran Teorema 1.2 dapat diperiksa pada kedua graf ini. Contoh 1.3. Periksa apakah kedua graf pada Gambar 1.10 isomorfik.
( b) G’ = (V’, E’)
( a) G = (V, E) Gambar 1.10
Penyelesaian. Kita mulai dengan menamai simpul-simpul graf G seperti tampak pada Gambar 16(a). V’1 V1 V6
V5
V4
V3
V’3
V2
(b) G’ = (V’, E’)
(a) G = (V, E) Gambar 1.11
Karena simpul v3 berderajat 3 dan G’ hanya mempunyai satu simpul berderajat 3, maka menurut Teorema 3 simpul v3’ haruslah seperti tampak pada Gambar 10(b). Akan tetapi simpul v3 berikatan dengan dua simpul terminal, yaitu v1 dan v2, sedangkan pada graf G’ simpul v3’ hanya berikatan dengan satu terminal, yaitu v1’ seperti pada Gambar 11(b). Dengan demikian penamaan simpul di G’ yang memenuhi Definisi tidak dapat dilanjutkan. Hal ini berarti graf G tidak isomorfik dengan G’. 6
Teladan ini menunjukkan tidak berlakunya konvers pernyataan berikut: Jika graf G = (V,E) isomorfik dengan G’= (V’, E’), maka simpul-simpul di V dan V’ sama banyaknya dan demikian pula dengan banyaknya sisi di E dan E’.
7
