MAKALAH MATEMATIKA DISKRITTENTANG GRAP PLANAR

DI SUSUN OLEHKELOMPOK 9NAMA KELOMPOK :1. ROBBY SURYANANPM 40120362. RANI ASNURIDA NPM 40120113. ADI SAPUTRANPM 4012005

DOSEN PENGAMPU : Dr.FADLI,M.Pd

SEKOLAH TINGGI KEGURUAN DAN ILMU PENDIDIKAN PERSATUAN GURU REPUBLIK INDONESIA LUBUKLINGGAUSTKIP PGRI LUBUKLINGGAUTAHUN AJAR 2014 2015

KATA PENGANTARPuji dan syukur marilah Kita ucapkan atas Kehadirat Allah SWT, karena berkat Rahmat dan Hidayah-Nyalah makalah ini dapat tersusun. Makalah matematika dikrit tentang Graf Planar. Pada kesempatan ini penulis mengucapkan terimakasih kepada:1. Bapak Dr. Fadli, M.Pd selaku dosen pengampu dari mata kuliah Matematika Diskrit.2. Rekan-rekan dan pihak yang telah membantu terbentuknya makalah yang berjudul Graf Planar.Demikianlah semoga dengan tersusunnya makalah ini, dapat menambah wawasan serta ilmu pengetahuan pembaca sekalian. Penulis sangat mengharapkan kritik dan saran yang bersifat membangun dari para pembaca. Atas perhatiannya Kami ucapkan terimakasih.

Lubuklinggau, Mei 2015,

Penulis

DAFTAR ISIKATA PENGANTARiiDAFTAR ISIiii

BAB IPENDAHULUAN4A. Latar Belakang4B. Rumusan Masalah4C. Tujuan Penulis4

BAB IIPEMBAHASAN5A. Graf Planar 5B. Rumus Euler 7C. Teorema Kuratowski10

BAB III PENUTUPKESIMPULANDAFTAR PUSTAKA

BAB IPENDAHULUANA. Latar Belakang Pada kehidupan modern sekarang, pengaplikasian ilmu matematika sudah sangat familiar dilakukan. Salah satu ilmu tersebut adalah Teori Graf. Pengaplikasian ilmu ini sudah digunakan pada banyak masalah seperti penentuan rute terpendek dari suatu kota ke kota lainnya, perancangan jalan tol bertingkat, perancangan lintasan lempeng motherboard dan lain sebagainya. Dengan demikian, ilmu matematika semakin berkembang dari hari ke hari hingga dapat diterapkan dalam aplikasi dunia nyata (tidak hanya sebatas perhitungan konvensional). Walaupun ilmu tersebut sudah berkembang cukup pesat, namun banyak orang yang belum mengetahui apa saja hal menarik yang ada dalam teori graf.Secara sederhana graf G = (V, E) didefinisikan sebagai kumpulan titik V = ( V1, V2,) yang dihubungkan oleh garis yang di sebut sisi E = ( E1, E2,). Secaramatematis, graf adalah pasangan himpunan (V,E) dimana Vadalah himpunan tak kosong yang memiliki elemen disebut simpul (vertices) dan Eadalah kumpulan dari himpunan sisi sedemikian sehingga membuat suatu titik yang membentuk berpasanganyangdisebut busur (edges). Simpul direpresentasikan dengan titik dan busur direpresentasikan dengan garis yang menghubungkan dua titik menjadi satu sisi. Graf memiliki beberapa jenis yaitu graf berarah, graf sederhana graf bidang graf planar, graf lengkap, graf bipartite dan masih banyak lagi. Salah satu hal menarik yang dapat dipelajari dari Teori Graf adalah mengenai graf planar terkhusus pada bagaimana cara menentukan suatu graf sembarang merupakan graf planar atau tidak. Untuk menentukan graf planar dapat menggunakan rumus Euler. Dan juga dengan Teorema Kuratowski untuk menentukan keplanaran suatu graf. Graf planar banyak digunakan untuk menentukan suatu perjalan untuk menghubungkan beberapa titik kedalam lintasan dan jalur agar tidak terjadi perpotongan. Berdasarkan hal tersebut, makalah ini berjudul Graf Planar dan Graf Sebidang.

B. Rumusan MasalahBerdasarkan latar belakang diatas, rumusan masalah yang akan dibahas oleh penyusun didalam makalah ini, antara lain:1. Apa yang dimaksud dengan graf planar dan graf bidang?2. Bagaimana menentukan suatu graf sembarang merupakan graf planar?C. Tujuan PenulisPada dasarnya tujuan penulisan makalah ini terbagi menjadi dua. Adapun tujuan umumnya adalah memenuhi salah satu tugas mata kuliah Matematika Diskrit. Sementara tujuan khususnya adalah:1. Dapat mengetahui perbedaan graf planar dan graf bidang2. Dapat menentukan suatu graf sembarang merupakan graf planar atau graf non planar

BAB IIPEMBAHASAN A. Grap Planar Graf yang dapat digambarkan pada bidang datar dengan cara demikian hingga tidak ada dua rusuk yang saling berpotongan kecuali pada simpul-simpulnya maka disebut graf planar. Sedangkan graf sebidang adalah graf planar yang telah di gambarkan di bidang datar sedemikian rupa sehingga tidak ada lagi rusuk-rusuk yang berpotongan.

Contoh :G1G2

Gambar G1 adalah suatu graf dan gambar G2 adalah graf planar dari G1

Perhatikan gambar di atas G2 adalah graph sebidang dan perhatikanlah bagian-bagian bidang datar yang ditinggalkan bidang datar yang ditinggalkan setelah kita mengangkat rusuk-rusuk dan simpul-simpul dari G (boleh dibayangkan bahwa bidang tempat gambar dibuat dari karton Potongan-potongan bidang terhubung ini disebut daerah atau region dari G. Simpul-simpul dan rusuk-rusuk dari G yang bertemu dengan daerah R membangun suatu batas dari R. Marilah kita ingat konsep ini.Graph sebidang pada Gambar G2 mempunyai (simpul), (rusuk), dan (daerah). G2 mempunyai = 5, = 9, dan = 6. Maka dalam suatu graf planar berlaku rumus euler yaitu p - q + r = 2. Graf yang termasuk graf planar juga antara lain : Tree / Pohon, bangun ruang segi empat, Bidang Delapan Beraturan.

B. Rumus Euler Rumus euler digunakan dalan graf planar untuk menentukan suatu jumlah wilayah , jumlah sisi dan jumlah simpul . Rumus Euler adalah

.Dengan: = jumlah sisi = jumlah simpulContoh : Misalkan graf sederhana planar memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk?Penyelasaian : Diketahui n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 4 = 96. Menurut lemma jabat tangan, = sehingga = 96/2 = 48 Dari rumus Euler, , sehingga r = 2 v + q = 2 24 + 48 = 26 buah.r = 26 buah seandainya graf adalah pohon maka berlaku rumus ,dan wilayah yang diciptakan pohon

Contoh : Tentukan atau banyak rusuk dari pohon disamping jika di ketahui

Penyelesaian :

Pada graf planar sederhana terhubung jika G adalah graf sebidang terhubung dengan banyak simpul . dan banyak rusuk maka berlaku . Misalkan = 3 maka yang mungkin paling banyak adalah 3 dan yang mungkin adalah 2. Jadi setiap di batasi oleh 3 rusuk karena rusuk maka :

Dalam hal ini jika kita masukkan kedalam rumus euler maka menjadi :

Contoh :

Misalkan = 3 dan 2, maka yang mungkin adalah

Untuk maka

Hal ini dinyatakan dengan corallary berikut.COROLLARY 8.1 Jika G adalah graf sederhana terhubunga dengan e adalah jumlah sisi dan v adalah jumlah simpul, yang dalam hal ini v , maka berlaku ketidaksamaan Euler e

Contoh :Tentukan apakah graf lengkap K5 adalah planar?Penyelesaian :

Diketahui bahwa K5 memiliki dan maka sehingga maka dari hasil tersebut dapat dikatakan bahwa K5 termasuk non planar.Persamaan ini digunakan untuk menentukan suatu graf terhubung planar atau non planar tetapi persamaan ini hanya syarat perlu agar suatu graf dikatakan plana tetapi bukan syarat cukup maksudnya meskipun suatu graf planar sederhana memenuhi persamaan tetapi tidak menjamin keplanaran suatu graf. Contoh bahwa pernyataan ini benar akan dilakukan uji coba pada graf K3,3 atau graf bipartit.

Dari gambar maka diketahui bahwa K3,3 memiliki dan maka

Padahal graf K3,3 bukan graf planar ! untuk menunjukkan bahwa K3,3 bukan graf planar, kita membuat asumsi baru bahwa setiap wilayah pada graf bidang dibatasi oleh paling sedikit empat buah sisi ( jadi, bukan 3 sisi seperti pembuktian ketidaksamaan di atas). Dengan demikian, total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi, karena suatu sisi berada pada batas paling banyak dua wilayah, maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi,2qatauq/2

Berdasarkan rumus Euler, kita perolehp q+ q/2 atau q hal ini dinyatakan dengan corollary berikut :COROLLARY 8.2 Jika G adalah graf sederhana terhubung dengan q adalah jumlah sisi dan p adalah jumlah simpul, yang dalam hal ini p dan tidak ada sirkuit yang panjangnya 3, maka berlaku q

maka K3,3 dapat dibuktikan sebagai berikut :Graf K3,3 tidak memenuhi ketidaksamaan , karena = 9 , = 69 = 8 (salah)Yang berarti K3,3 bukan graf planar

C. Teorema KuratowskiBerikut ini diberikan teorema dari Kuratowski yang memungkinkan kita menentukan dengan tegas keplanaran suatu graf.Dalam literatur tentang graf, dikenal dua buah graf tidak planar yang khusus yaitu graf Kuratowski, setelah metematikawan Polandia, Kasimir Kuratowski, menemukan sifatnya yang unik 1. Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul ( K5) adalah graf tidak planar.

dengan wilayah, buah simpul, dan buah sisi maka setiap wilaya atau daerah yang dibatasi (dengan > 2 ) selalu berlaku pertidaksamaan berikut :

e 3/2

DEFINISI. Graf yang digambarkan pada bidang datar dengan sisi sisi yang sejajar tidak saling memotong (bersilangan) disebut graf planar, jika tidak maka disebut graf tak planar .Contoh Graf K4 adalah graf planar, biasanya digambarkan dengan sisi yang bersilangan seperti ditunjukkan pada gambar 8.42 (a) . Kita dapat menggambarkan graf itu kembali tanpa ada sisi sisi yang berpotongan, seperti pada gambar 8.42 (b) . K5 pada gambar 8.43 bukan graf planar

(a) Gambar 8.42 (b)

Gambar 8.43 K5 bukan graf planarContoh 8.32Tinjau kembali persoalan utilitas : terdapat tiga buah rumah (gambar 8.44 (a), H1, H2, H3 masing masing dihubungkan dengan tiga buah pipa utilitas air (W), gas (G), dan juga listrik (E) dengan alat pengantar (pipa,kabel,ds). Graf pada gambar 8.44(a) tersebut juga graf bipartit lengkap, K3,3 . Mungkinkah jaringan utilitas sehingga tidak ada pengantar yang saling berpotongan ? (sebab kalau ada saling berpotongan, dikhawatirkan timbul masalah yang serius, misalnya bila kabel listrik berpotongan dengan pipa gas dapat terjadi ledakan)

H1H2H3H1H2H3

E W G (a)EWG (b)Gambar 8.44 (a) Graf persoalan utilitas, (b) graf persoalan utilitas bukan planar , karena apabila graf digambarkan kembali dalam bidang datar maka masih terdapat simpul yang berpotongan

Representasi graf planar yang digambarkan dengan sisi sisi yang tidak saling berpotongan disebut graf bidang (plane graph). Pada gambar 8.46, ketiga buah graf adalah graf planar, tetapi graf (a) bukan graf bidang, sedangkan graf (b) dan (c) adalah graf bidang. Ketiga graf ini isomorfik. Untuk selanjutnya, kita tetap menggunakan istilah graf planar baik untuk graf yang dapat digambar (ulang) pada bidang datar tanpa ada sisi sisi yang berpotongan maupun graf yang memang sudah tergambar tanpa sisi sisi yang berpotongan (graf bidang) .

(a)(b)(c)Gambar 8.46 Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang Sisi sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face). Jumlah wilayah pada graf bidang dapat dihitung dengan mudah. Graf bidang pada Gambar 8.47 terdiri atas 6 wilayah (termasuk wilayah terluar) :R2R3 R4R6R1 R5

Gambar 8.47 Graf planar yang terdiri atas 6 wilayah

D. Rumus Euler Jumlah wilayah (f) pada graf planar sederhana juga dapat dihitung dengan rumus Euler sebagai berikut :n- e + f = 2 atau f = e n + 2 , yang dalam hal ini : e = jumlah sisi n = jumlah simpulpada gambar 8.47 diatas , e = 11 dan n = 7 , maka f = 11 7 + 2 = 6Pada graf planar sederhana terhubung dengan f wilayah , n buah simpul, dan e buah sisi (dengan e > 2 ) selalu berlaku pertidaksamaan berikut :e 3f/2dan e 3n 6 dua ketidaksamaan yang terakhir ini dapat kita buktikan sebagai berikut : Setiap daerah pada graf planar dibatasi oleh tiga atau lebih sisi. Jadi, total banyaknya sisi lebih besar atau sama dengan 3f. Tetapi, karena suatu sisi berada pada batas paling banyak dua wilayah, maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi ,2e 3fatau2e/3 Berdasarkan rumus Euler, kita perolehn- e + 2e/3 atau e Ketidaksamaan yang terakhir dinamakan ketidaksamaan Euler, yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana ( kalau graf planar, maka ia memenuhi ketidaksamaan Euler, sebaliknya jika tidak planar maka ketidaksamaan tersebut tidak dipenuhi) . ini dinyatakan dengan corallary berikut :COROLLARY 8.1 Jika G adalah graf sederhana terhubunga dengan e adalah jumlah sisi dan v adalah jumlah simpul, yang dalam hal ini v , maka berlaku ketidaksamaan Euler e .Contoh 8.36Pada graf K4 ( Gambar 8.48 (a) ), n = 4, e = 6, memenuhi 6 . Dengan kata lain , K4 adalah graf planar .

Contoh 8.37Perlihatkan bhawa K5 (Gambar 8.48 b) tidak planar dengan ketidaksamaan Euler.Penyelesaian : Pada graf K5 , n = 5 dan e = 10. K5 tidak memenuhi ketidaksamaan Euler , sebab 10 3(5) 6. Hal ini menunjukkan bahwa K5 tidak planar.

a K4b K5c K3,3Gambar 8.48 (a) graf lengkap K4, b K5, dan graf bipartit c K3,3Sayangnya, ketidaksamaan Euler hanyalah sayarat perlu agar suatu graf dikatakan planar, akan tetapi bukan syarat cukup. Artinya meskipun suatu graf planar sederhana memenuhi kedua ketidaksamaan itu, tetapi tidak selalu menjamin keplanaran suatu graf. Misalnya graf K3,3 (gambar 8.48 c) memenuhi ketidaksamaan Euler tersebut ,e = 9, n = 6 9 = 12 (jadi, e Padahal graf K3,3 bukan graf planar ! untuk menunjukkan bahwa K3,3 bukan graf planar, kita membuat asumsi baru bahwa setiap wilayah pada graf bidang dibatasi oleh paling sedikit empat buah sisi ( jadi, bukan 3 sisi seperti pembuktian ketidaksamaan di atas). Dengan demikian, total banyaknya sisi lebih besar atau sama dengan 4f. Tetapi, karena suatu sisi berada pada batas paling banyak dua wilayah, maka total banyaknya sisi lebih kecil atau sama dengan 2e. Jadi,2e ataue/2

Berdasarkan rumus Euler, kita perolehn e + e/2 atau e hal ini dinyatakan dengan corollary berikut :COROLLARY 8.2 Jika G adalah graf sederhana terhubung dengan e adalah jumlah sisi dan v adalah jumlah simpul, yang dalam hal ini v dan tidak ada sirkuit yang panjangnya 3, maka berlaku e Contoh Graf K3,3 tidak memenuhi ketidaksamaan e , karena e = 9 , n = 69 = 8 (salah)Yang berarti K3,3 bukan graf planar

E. Teorema KuratowskiBerikut ini diberikan teorema dari Kuratowski yang memungkinkan kita menentukan dengan tegas keplanaran suatu graf.Dalam literatur tentang graf, dikenal dua buah graf tidak planar yang khusus yaitu graf Kuratowski, setelah metematikawan Polandia, Kasimir Kuratowski, menemukan sifatnya yang unik [ DEO74]2. Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul ( K5) adalah graf tidak planar.3. Graf Kuratowski kedua, yaitu graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar.Sifat graf Kuratowski adalah :1. Kedua graf Kuratowski adalah graf teratur.2. Kedua graf Kuratowski adalah graf tidak planar3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkan menjadi graf planar4. Graf Kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. Keduanya adalah graf tidak planar paling sederhana.Teorema 8.2 ( Teorema Kuratowski) graf G adalah tidak planar jika dan hanya jika ia mengandung upagrap yang isomorfik dengan K5 atau K3,3 atau homeomorfik (homeomorphic) dengan salah satu dari keduanya .Graf Isomorfik dan Graf HomeomorfikGraf dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya. Hanya penggambaran saja yang berbeda .3dc4

12abGambar 5. Dua buah graf yang saling isomorfikGraf dikatakan homeomorfik jika salah satu dari kedua graf dapat diperoleh dari graf lainnya dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat dua.yvx

G1G2G3Gambar 6. Tiga graf yang saling homeomorfik

Gambar 8. Graf KuratowskiGambar 1 dan 2 adalah graf Kuratowski, gambar 3 adalah graf yang isomorfik dengan gambar 2 sehingga gambar 3 merupakan graf tidak planarTinjau gambar 8.51 . Graf G tidak planar karena ia mengandung upagraf (G1) yang homoemorfik dengan K5 (dengan membuang simpul simpul yang berderajat 2 dari G1, diperoleh K5)

GG1K5Gambar 8.51 graf tidak planar karena upagrafnya G1 homoemorfik dengan K5

Contoh Perlihatkanlah dengan terorema Kuratowski bahwa graf Petersen ( gambar 8.52 (a) ) tidak planar !

Penyelesaian :Dari graf Petersen(Gamabar 8.52 (a)), buatlah sebuah upagrafnya, misalkan G1 .dengan membuang simpul berderajat 2 dari G1, kita dapatkan G2 yang homeomorfik dengan G1. Jika G2 digambar ulang , kita dapat G2 isomorfik dengan K3,3. Rangkaian proses ini menunjukkan bahwa graf Petersen tidak planar.

(a) Graf Petersen, G(b) G1(c) G2

Gambar 8.52(d) K3,3(a).Graf Petersen, (b).G1 adalah upagraf dari G, (c).G2 homoemorfik dengan G1,(d).G2 isomorfik dengan K3,3. Teorema Kuratowski lebih mudah digunakan untuk menentukan bahwa sebuah graf tidak planar. Untuk membuktikan suatu graf planar relatif lebih sulit, karena kita harus mencoba semua kemungkinan upagraf yang memiliki 5 simpul dengan 10 sisi atau upagraf yang memiliki 6 simpul dan 9 sisi, dan memeriksa apakah upagraf tersebut sama atau homoemorfik dengan K5 dan K3,3DAFTAR PUSTAKAMunir, Rinaldi. 2012. Matematika Diksrit ( Edisi Revisi Kelima ). Bandung : Informatika Bandung .Drs. Suryadi, Didi, M.Ed , Dr. Sugeng Mardiyono, M.Sc.Ap, dan Drs. Nanang Priatna, M.Pd. 2002. Pengantar Teori Graph. Jakarta : Universitas Terbukahttp: //informatika.stie.itb.ac.id/ -rinaldi.munir/ Matdis/ 2006-2007/ Makalah / Makalah 0607- 34.pdf diakses pada tanggal 26 april 2015