Minggu ke IV DEFINISI GRAF BIDANG DAN GRAF PLANAR. Jika pada sajian geometrik suatu graf ternyata setiap pasangan sisinya saling berpotongan hanya pada simpul ujungnya, maka graf ini disebut graf bidang. Suatu graf G yang isomorfik dengan graf bidang disebut graf planar. Dalam hal lainnya G disebut graf tak planar. Kiranya jelas bahwa graf sirkuit merupakan graf planar. Contoh lainnya, misalnya graf lengkap K4 yang sajian geometriknya diwakili oleh keempat graf pada Gambar 4.1 adalah graf planar, tetapi hanya graf kedua, ketiga, dan keempat yang merupakan graf bidang.
4
2
3
1
1
3
1
2 4
2 3
4 Gambar 4.1 Dari setiap graf bidang pada Gambar 4.1 dapat diamati bahwa bidang datar tempat graf terbagi menjadi 4 daerah yang dinomori dari 1 sampai dengan 4. Daerah seperti ini disebut muka. Grafn tersebut mempunyai 4 simpul dan 6 sisi, dan memenuhi hubungan (banyaknya simpul) – (banyaknya sisi) + (banyaknya muka) = 2. Pada tahun 1750 hubungan ini telah diperlihatkan berlaku untuk sembarang graf bidang dan dikenal sebagai rumus Euler. TEOREMA 4.1. RUMUS EULER. Pada graf bidang G = (V, E) dengan n simpul, m sisi, dan f muka berlaku hubungan n – m + f = 2. Contoh populer graf tak-planar ialah K5 dan K33. Oleh karena itu, pada sistem “sarana” tersebut di atas sudah dapat dipastikan ada sepasang pipa yang saling tumpang-tindih seperti dijelaskan berikut ini. Pada Gambar 4.2 tampak bahwa K33 mengandung graf sirkuit, misalnya dengan rangkaian simpul dan sisi seperti tampak pada Gambar 4.3. b a a a c u u v
c w u
v w Gambar 4.2
b
v
c w Gambar 4.3
19
b
Sekarang kita harus menempatkan sisi-sisi ub, vc, dan wa. Dari Gambar 4.3 mudah dilihat bahwa hanya satu di antara ketiga sisi ini dapat digambar di dalam heksagon, karena dalam hal lainnya akan saling berpotongan. Dengan alasan serupa tampak bahwa hanya satu sisi saja yang dapat digambar di luar heksagon. Dengan demikian tidak mungkin menempatkan ketiga sisi tersebut tanpa menghasilkan titik potong, sehingga akibatnya K33 bukan graf planar. Karena graf terdiri atas himpunan simpul dan sisi, maka kita dapat pula mendefinisikan pengertian graf-bagian suatu graf. Hal ini berarti kita memilih sebagian diagram yang dianggap penting dari model yang disusun. DEFINISI GRAF BAGIAN. Graf G’(V’,E’) disebut graf-bagian graf G = (V, E) jika semua simpul dan sisi G’ juga terletak di G, dan setiap sisi G’ mempunyai simpul ujung yang sama dengan di G. Dengan demikian V’ merupakan himpunan bagian V dan E’ merupakan himpunanbagian E. Misalnya graf pada Gambar 4.4(a) dan (b) adalah graf-bagian graf pada Gambar 4.4(c) V6
V4
V3
V4
V3
V5
V6 V6 V5 V2 (a)
(b)
V2
V1
Gambar 4.4
V2 (c)
Sebagai akibat langsung definisi himpunan bagian dan graf, maka berlaku teorema berikut: TEOREMA 4.2. Jika G = (V, E) merupakan graf sembarang, maka 1) Setiap graf adalah graf-bagian dari dirinya 2) Graf-bagian dari suatu graf-bagian G adalah juga graf-bagian G; sifat ini biasa dikenal sebagai sifat menghantar (transitif) 3) Satu simpul pada graf G merupakan graf-bagian G 4) Satu sisi, termasuk kedua simpul ujungnya, juga merupakan graf-bagian G.
Soal-soal Latihan (1) Berikan sajian geometrik, matriks ikatan, dan matriks kehadiran graf lengkap dengan dua, tiga, empat, lima, dan enam simpul ! (2) Periksa apakah graf bipartit lengkap K2,2 dan K3,2 merupakan graf bidang; kemudian susunlah matriks ikatan dan matriks kehadirannya, serta periksa pula kebenaran Rumus Euler !. 20
(3) Berapakah banyaknya sisi Graf bipartit lengkap Km,n ? Graf teratur berderajat r dengan n simpul ? (4) Berikan contoh sajian geometrik a) Graf teratur berderajat 2 yang bukan graf lengkap b) Graf bipartit teratur (5) Periksa apakah graf dengan 11 simpul, dua simpul berderajat satu, dan simpul lainnya berderajat dua, merupakan graf bipartit ? Jika “ya”, susunlah sajian geometriknya sehingga sifat bipartit ini tampak dengan jelas dan berikan pula komplemennya. (6) Periksalah apakah graf-graf di bawah ini bipartit ? Jika ya, susunlah sajian geometriknya sehingga sifat bipartit ini tampak dengan jelas. a) V 4
V2
b)
V3
c)
V1 V5
V3
V4
V3
V6 V8 V7
V1 d)
V4
V5
V2
V6
V5
V8
V7
V1
V2
V3 V6 V4
4
V5
V1
V2
7 5
(7) Perhatikan graf teratur berderajat 3 yang dikenal sebagai graf Petersen di samping ini. Julis Petersen (1839 – 1910) adalah matematikawan berkebangsaan Denmark. Di antara graf di halaman berikut ini, periksalah graf yang mana saja yang merupakan graf-bagian graf Petersen. 4 6 8 10 1
9
10 1
2
4
7 5
8
6
3
3
5
9 2
7 7 6 8
9
10
10 1
2 21
9
3
(8) Berikan komplemen graf berikut a)
b)
•
4.1 Keterhubungan Graf Sekarang amati kembali graf pada Gambar 4.5 yang identik dengan graf pada Gambar 3(c) dan mewakili denah jalan Gambar 1.2 B B A B E C E A C A E C D A D B E C D D B Gambar 4.5 Gambar 4.6 Dalam kehidupan sehari-hari ada banyak cara bagi seseorang yang tinggal pada daerah pemukiman A untuk pergi ke daerah C, tiga di antaranya diperagakan berikut ini. Ia dapat melewati jalan-jalan yang diwakili sisi AB dan BC. Akan tetapi untuk menghabiskan waktu senggangnya atau karena alasan lain ia dapat pula menempuh perjalanan yang agak panjang, misalnya sisi-sisi AD, DB, BE, ED, dan DC. Selain itu mungkin pula perjalanan yang ditempuhnya lebih panjang lagi, seperti sisi AE, EB, BD, DE, EB, dan BC. Dalam bahasa teori graf perjalanan semacam ini dikenal sebagai trayek. Suatu trayek yang pernah melewati kembali lokasi yang sama, tetapi tidak pernah melewati kembali jalan yang sama, disebut jalur, misalnya trayek kedua. Sedangkan suatu trayek yang tidak pernah melewati kembali jalan dan lokasi yang sama disebut lintasan, misalnya trayek pertama. Selanjutnya lintasan yang lokasi awalnya sama dengan lokasi akhirnya disebut lintasan tertutup atau sirkuit, misalnya sisi-sisi AB, BC, CD, dan DA. Trayek AB, BC dikatakan mempunyai panjang 2 karena hanya mencakup dua sisi, sedangkan dua trayek lainnya masingmasing mempunyai panjang 5 dan 6 seperti tampak pada Gambar 4.6. Definisi selengkapnya tentang trayek dan jenis-jenisnya diberikan di bawah ini : DEFINISI TRAYEK GRAF. Misalkan G = (V, E) adalah suatu graf dengan n simpul. Suatu trayek antara simpul u dan z pada graf G ialah sekuens sisi-sisi yang saling berikatan pada G berbentuk {u, v}, {v, w}, {w, x}, …, {y, z} atau dicatat sebagai u v wx … y z Simpul u dan z masing-masing disebut simpul awal dan simpul akhir trayek. Panjang trayek (walk) ialah banyaknya sisi pada sekuens itu. 22
Dalam definisi ini tidak disyaratkan semua sisi harus berbeda. Jadi, misalnya, untuk graf pada Gambar 5.1, sekuens sisi
u v y w v z y w x y adalah trayek dengan panjang 9 antara u dan y, melintasi sisi {y, w} dua kali, simpul v, w dua kali, dan y tiga kali
23
