Makalah Graf Planar [PDF]

Citation preview

TUGAS KELOMPOK



MATEMATIKA DISKRIT BAB 5 GRAF PLANAR



Dewi Apriliana



0401513046



Elisabet Wijaya Prihandini



0401513049



Andhy Tia Saputra



0401513053



PROGRAM PASCASARJANA PROGRAM STUDI PENDIDIKAN MATEMATIKA UNIVERSITAS NEGERI SEMARANG 2014



Bab 5 Graf Planar 5.1Graf PLanar dan Graf Bidang Graf Bidang adalah graf yang digambarkan pada bidang datar (di kertas, papan tulis, dll) sedemikian rupa sehingga setiap pasang sisi bertemu hanya pada simpul akhirnya (jika mereka bertemu sama sekali). Graf Planar adalah graf yang isomorfik dengan graf bidang, yaitu dapat digambar kembali sebagai graf bidang.



Contoh Graf Planar



Gambar 5.1: Lima graf planar Pada gambar di atas semua merupakan Graf Planar, tetapi graf bidang, karena sedangkan



G4



G1



G1



dapat di gambarkan kembali menjadi



dapat di gambarkan kembali menjadi



G5



dan G2



G4 dan



Tidak G3



.



Tidak semua graf adalah Planar.Untuk melihat ini, perlu dibicarakan tentang teorema utama dalam matematika. Sebuah kurva Jordan pada bidang adalah kurva kontinu yang tidak memotong dirinya sendiri dengan asal dan akhirnya bertemu.



Sebagai contoh, pada Gambar 5.2 kurva memotong dirinya sendiri,



C2



c1



dan



bukan kurva Jordan karena



bukanlah kurva Jordan karena asal dan terminalnya tidak



tepat, yaitu dua titik akhir tidak bertemu,



Gambar 5.2:



C1



c2



C3



adalah kurva Jordan.



bukan kurva jordan tetapi



c3



kurva jordan.



Gambar 5.3: Sebuah kurva Jordan . Jika J adalah kurva Jordan pada bidang maka bagian dari bidang yang tertutup oleh J disebut interior J dan dilambangkan dengan int J , dikecualikan untuk int J titik-titik yang benar-benar berada di J. Demikian pula bagian dari bidang yang terletak di luar J disebut eksterior J dan dilambangkan dengan ext J.



Teorema kurva Jordan menyatakan bahwa jika J adalah kurva Jordan, jika x adalah titik di int J dan y adalah titik dalam ext J maka setiap garis (lurus atau melengkung) yang menghubungkan x ke y harus bertemu J pada beberapa titik, yaitu harus menyeberang J. Teorema ini hanyalah intuitif, diilustrasikan dalam Gambar di bawah ini.



Gambar 5.4



Bentuk lain dari teorema ini bahwa jika



x1 , x2



adalah dua titik di int J maka ke



x2



yang terletak



sepenuhnya dalam int J. Sebuah ilustrasi ini diberikan dengan kurva



C4



Gambar 5.3,



dapat ditemukan garis (lurus atau melengkung) hubungan



x1



dengan dua titik digabung dengan sebuah garis internal. Sekarang digunakan Teorema Kurva Jordan untuk membuktikan bahwa ada graf nonplanar. Teorema 5.1 :



K5



graf lengkap pada lima simpul, adalah nonplanar.



Bukti:Ingatlah bahwa salah satu cara yang biasa digunakan menggambar



K5



seperti gambar di bawah ini.



Gambar 5.5 Diasumsikan bahwa



K5



adalah planar dan akan di tunjukkan kontradiksi dengan



asumsi ini. Misal G menjadi graf bidang yang sesuai v1 , v 2 , v3 , v4 , v5



Goleh



membentuk kurva Jordan di bidang. Karena di int C atau ext C. Dianggap bahwa v4



v 4 v3



v4



v4



v1 v2 v3 v1



di G. Kemudian C



tidak terletak di C maka harus terletak



adalah int C. Kemudian (Kemungkinan lainnya,



adalah dalam ext C, memiliki argumen yang sama.) sisi



membagi intC menjadi tiga wilayah int



C1 , C2 ,



dan menunjukkan simpul dari



.Karena G lengkap, setiap pasangan simpul yang berbeda



bergabung dengan sebuah sisi.Misal C adalahsiklus



bahwa



K5



dan



C3



adalah siklus



turut.Perhatikan gambar di bawah ini.



C1 ,



int



v 1 v 2 v 4 v1 , v 2 v 3 v 4 v 2



C2 dan



v 4 v1 , v4 v2



dan



C3



di mana



v1 v3 v4 v1



berturut-



dan int



Gambar 5.6 v5



Titik int



C2



, int



yang tersisa harus terletak pada salah satu dari empat wilayah int



C3



dan ext C. Jika



v5 ∈



Kurva Jordan memberitahu bahwa sisi ini berarti bahwa sisi v3 v1



v 4 v5



ext C kemudian, karena v 4 v5



int C, Teorema



harus melaluiC di beberapa titik. Namun



harus menyeberang salah satu dari tiga sisi



v1 v2 , v2 v3



dan



yang membentuk C. Ini bertentangan asumsi bahwa G adalah grafbidang.



Kemungkinan yang tersisa adalah bahwa C2



v 4∈



C1 ,



, int



C3



V3



merupakan salah satu dari int



C1,



int



.



Dianggap bahwa Sekarang



v5



V 5 pada∫ C1 , dua kasus lainnya yang diperlakukan sama.



adalah di bagian luar Curve Jordan diberikan siklus



C1 =v 1 v 2 v 4 v 1



.



Dengan Teorema Kurva Jordan sisi bergabung dengan titik V 5 ( di ∫ C 1 ) ke v 3 ( di ext C1 ) harus menyeberang kurva v 1 v 2 v 4 v1



C1



dan harus menyeberangi salah satu dari tiga sisi



.sekali lagi bertentangan dengan asumsi bahwa G adalah bidang.kontradiksi



akhir ini menunjukkan bahwa asumsi awal harus salah. Oleh karena itu



K5



tidak planar.



Ingat bahwa cara yang biasa dari gambar K3.3 seperti yang ditunjukkan pada Gambar 5.7. Ini juga adalah nonplanar .



Gambar 5.7 Teorema 5.2Graf bipartit lengkap K3,3 adalah nonplanar.



5.2 FORMULA SebuahEULER graf bidang G membagibidang menjadi beberapa wilayah yang masing masing disebut ”muka”(face) G. Lebih tepatnya, jika x adalah titik pada bidang yang tidak diG, yaitu bukan simpul dari G atau titik di beberapa sisiG, maka didefinisikan muka Gmengandungx yang merupakan himpunan semua titik pada bidang yang dapat dihubungkan dari x menjadi garis (lurus atau melengkung) yang tidak menyeberang sisi G atau melalui simpul dari G.



Contoh, untuk titik x di graph G1 dari Gambar 5.9, muka yang mengandung x ditampilkan sebagai wilayah bertitik. Dalam contoh ini jelas muka G1 mengandung titik y adalah muka yang sama seperti yang mengandung x. Hal ini dibatasi oleh siklus v2 v4 v 3 v6 v5 v4 . Muka G mengandung titik z tidak dibatasi oleh siklus apapun. Hal 1



ini disebut muka eksterior G1



Gambar 5.9: Sebuah graf bidang dengan empat muka Setiap graf bidang memiliki tepat satu muka eksterior. Setiap muka yang lain dibatasi oleh jalan tertutup dalam graf dan disebut muka interior. Sebagai contoh lain, pada Gambar 5.10 memiliki graf G2 dengan sembilan muka f 1,…,f 9 f .Disini 6 adalah muka eksterior.



Gambar 5.10: Sebuah graf bidang dengan sembilan muka Jumlah muka graf bidangG dilambangkan dengan f {G }



atau hanya dengan f .



Dengan demikian, untuk di atas, f (G1) = 4, f (G2) = 9. Akibat selanjutnya, diberikan rumus sederhana yang menunjukkan hubungan antara jumlah simpul, sisi, dan muka dalam graf bidang terhubung.



Teorema 5.3 (Formula Euler) :Misalkan G graf bidang terhubung, dan misalkan n,e, dan f masing-masing menunjukkan jumlah simpul, sisi dan muka G. Kemudian n-e + f = 2. Bukti. Bukti Pertama . Dalam bukti ini menggunakan induksi pada f, jumlah muka pada G.Jika f = 1maka G hanya memiliki satu muka, muka eksterior. Jika G mengandung beberapa C siklus kemudian di wilayah yang dibatasi oleh bidangC, ada setidaknya satu muka dibatasi dari G, mungkin karena G hanya memiliki muka eksterior, yang tak terbatas. Jadi G tidak memiliki siklus.Oleh karena itu, karena G terhubung, itu adalah pohon. Kemudian, denganTeorema 2.4, jumlah e sisi G adalah n - 1. Karenanya n-e + f = n-(n-l) + l = 2 dan ini membuktikan teorema dalam kasus ketika f = 1. Sekarang anggaplah bahwa f > 1 dan teorema tersebut benar untuk semua grafbidang terhubung dengan kurang dari f muka. Karena f > 1,G bukanlah pohon ,dengan Teorema 2.8,G memiliki ksisi yang tidak jembatan. Kemudian subgraf G - kmasih terhubung dan karena setiap subgraf dari graf bidang jelas grafbidang, G - k juga grafbidang. Selain itu, karena ksisi harus menjadi bagian dari siklus (lihat Teorema 2.7), memisahkan dua muka G dari yang lain dan selanjutnya di G - k dua muka bergabung untuk membentuk satu mukaG - k. Ini diilustrasikan pada Gambar 5.11.



Gambar 5.11.Dua muka bergabung ketika ujung siklus dihapus. Dengan demikian, pemisalan jumlah



simpul,



sisi



n ( G−k ) , e (G−k ) =e−1 karena G−k



n ( G−k ) , e (G−k )



f (G−k )



dari



menunjukkan



G−k ,



dan



muka



dan



f ( G−k )=f −1 . Selain itu, dengan asumsi induksi,



memiliki kurang dari f



masing-masing



dan



dimiliki



muka, dimiliki



n ( G−k )−e (G−k ) + f (G−k ) =2 dan juga n−( e−1 )+ ( f −1 )=2 yang memberikan



n−e+ f =2 , seperti yang



diperlukan. Oleh karena itu, dengan induksi, akibatnya adalah benar untuk semua grafbidang terhubung.



Bukti Kedua. Kali inidigunakan induksi pada jumlah e dari sisi G. Jika e = 0 maka G harus memiliki hanya satu simpul , yaitu n = 1 dan satu muka, muka eksterior, yaitu f =1. demikian



n−e+ f =1−0+1=2



dan sehingga hasilnya benar untuk e = 0. Meskipun tidak perlu untuk melakukan hal ini, sekarang dilihat kasus ketika e = 1. Kemudian jumlah simpul dari G adalah 1 atau 2, kemungkinan pertama terjadi ketika sisi adalah loop. Kemungkinan kedua menimbulkan dua muka dan satu muka masing-masing, seperti yang ditunjukkan pada Gambar 5.12.



Gambar 5.12: Graf bidang terhubung dengan satu sisi Sehingga, n−e+ f =



1−1+2, dalam kasusloop =2, {2−1+1, dalam kasus bukan loop }



seperti yang dipersyaratkan



Sekarang dianggap bahwa hasilnya adalah benar untuk setiap graf G bidang terhubung dengan e-1.Sisi (untuk e ≥ 1). Misal ditambahkan satu ksisi baru untuk G untuk membentuk supergraph terhubung dari G yang dilambangkan dengan G + k. Ada tiga cara untuk melakukan hal ini: (I) k adalah loop, dalam hal ini telah diciptakan muka baru (dibatasi oleh loop),namun jumlah simpul tetap tidak berubah, atau (II) k terhubung dengan dua simpul yang berbeda dari G, dalam hal ini salah satu muka G dibagi menjadi dua, sehingga sekali lagi jumlah muka telah meningkat sebesar 1, tetapi jumlah simpul tetap tidak berubah, atau (III) k adalah kejadian dengan hanya satu simpuldari G di mana kasus lain simpul harus ditambahkan, meningkatkan jumlah simpul dengan satu, tetapi menyisakan jumlah muka tidak berubah. Sekarang misalkan



n' , e' dan f ' menunjukkan jumlah simpul, sisi dan muka di



G dan n, e dan f menunjukkan jumlah simpul, sisi dan muka diG + k. Kemudian ' ' ' ' ' ' dalam kasus (i), n−e+ f =n −( e + 1 ) + ( f +1 ) =n −e +f , ' ' ' ' ' ' dalam kasus (ii), n−e+ f =n −( e + 1 ) + ( f +1 ) =n −e +f ,



n ' ' ' ' ' dalam kasus (iii), n−e+ f =(¿¿ ' +1)−( e +1 ) + f =n −e +f , ¿ ' ' ' Dan dengan asumsi induksi, n −e +f =2 Jadi, dalam setiap kasus, n−e+ f =2 .



Sekarang setiap graf bidang terhubung dengan esisi adalah bentuk G + k, untuk beberapa graf bidang terhubung G dengan e−1 sisi dan k sisi baru.Oleh karena itu, dengan induksi bahwa rumus benar untuk semua graf bidang. Konsekuensi 5.4 Misalkan G adalah graf bidang dengan n simpul , e sisi , f muka , dan k komponen terhubung . maka n−e+ f =k +1



Konsekuensi 5.5 Misal G1 dan G2 adalah 2 graf bidang yang keduanya digambarkan untuk Graf planar G yang sama.Maka f (G 1) = f(G2), yaitu, G1 dan G2 memiliki jumlah muka yang sama. Bukti Misal n(G1), n(G2) menunjukkan jumlah simpul dan e(G1), e(G2) jumlah sisi,masing -masing dalam G1, G2. Kemudian, karena G1 danG2 keduanya isomorfis ke Gdimilikin(G1) = n(G2) dan e(G1) = e(G2). Menggunakan Formula Euler didapatkan f(G1) = e(G1) - n (G1) + 2 = e (G2) - n (G2) + 2 = f (G2), Teorema berikutnya memberitahukan bahwa graf planar sederhana tidak dapat memiliki "terlalu banyak" sisi.Dalam bukti digunakan definisi berikut. Misal, φ



sebuah muka dari graf bidang G. didefinisikan derajat dari φ , dinotasikan dengan d( φ ), adalah jumlah sisi yang membatasi φ . Perhatikan bahwa d( φ ) ≥



3 untuk setiap



φ muka interior dari graf bidang



sederhana. Teorema 5.6 Misalkan G graf planar sederhana dengan n simpul dan e sisi , dimana n ≥ 3. maka e ≤ 3 n−6 . Bukti:Dengan menggambar ulang G, diasumsikan bahwa G adalah grafbidang (yang berbeda dari planar). Pertama-tama dimisalkan G terhubung, Jika n = 3, artinya, memiliki tiga simpul, kemudian, karena Gsederhana, G memiliki paling banyak tiga sisi, yaitu, e ≤ 3 . Dengan demikian e ≤ (3 x 3) - 6 = 3n - 6, sehingga hasilnya adalah benar dalam kasus ini.



Jadi sekarang bisa diasumsikan bahwa n ≥ 4. Jika G adalah pohon maka e = n - 1 dan seterusnya, karena n ≥ 4, didapatkan e ≤3n - 6. Jika G tidak pohon, karena terhubung, harus mengandung siklus. Selanjutnya ada siklus di Gpada setiap sisi yang terletak pada batas muka eksteriorG. Kemudian, karena G adalah sederhana, dimiliki d( φ )≥ 3 untuk muka masing-masing φ muka G. b=∑ d (φ) φϵ Φ



di mana Φ



menunjukkan himpunan semua mukaG. Kemudian, karena masing-masing



muka memiliki setidaknya tiga sisi pada batasnya, dimiliki b≥3f (Di mana f adalah jumlah mukaG). Namun, ketikadisimpulkan untuk mendapatkanb, masing-masing sisi G dihitung sekali atau dua kali (dua kali ketika terjadi seperti sebuah sisi membtasi dua muka) dan sebagainya b ≤ 2e



Dengan demikian 3 f ≤ b ≤2 e . Secara khusus



3 f ≤ 2e



dan sebagainya −f ≥−2 e /3 . Sekarang, dengan



teorema Euler,n = e - f + 2 dan seterusnya n ≥ e−



2e e +2= +2 3 3



Jadi 3 n ≥ e+6 yaitu 3 n−6 , Sekarang anggaplah G yang tidak terhubung. Misal G1,, ... , Gt komponen yang terhubung dan untuk setiap i, 1≤ i ≤ t, misal ni dan ei Menunjukkan jumlah simpul dan masingG Gi masing sisi dalam i Kemudian, karena masing-masing adalah graf planar, dimiliki, dari argumen di atas, bahwa t



t



i=1



i=1



n=∑ ni dan e=∑ e i dan sebagainya t



t



i=1



i=1



e ≤ ∑ ( 3 ni −6 ) =3 ∑ ni−6 t ≤3 n−6



e i ≤ 3 ni−6



untuk setiap i , 1≤ i≤ t Selain itu.



Konsekuensi 5.7: jika G adalah graf planar sederhana maka G memiliki simpul v dengan derajat kurang dari 6, yaitu, ada sebuah v di V(G) dengan d (v) ≤ 5. Bukti:Jika G hanya memiliki satu simpul, simpul ini harus memiliki derajat 0. Jika G hanya memiliki dua simpul maka keduanya harus memiliki derajatpaling banyak 1.Dengan demikian dapat diduga bahwa n ≥ 3, yaitu, bahwa G setidaknya memiliki tiga simpul. Sekarang jika derajat untuk setiap simpul dari Gadalah setidaknya enam dimiliki



∑



d (v )≥ 6 n



v ∈V (G)



Namun, dengan Teorema 1.1



∑ d ( v ) =2 e . v ∈V



Jadi 2e≥ 6n dan e≥ 3n.karena Ini tidak



mungkin, menurut teorema di atas, e ≤ 3n - 6. Kontradiksi ini menunjukkan bahwa G harus memiliki setidaknya satu simpuldari derajat yang kurang dari sama dengan 6. Konsekuensi 5.8 K5 adalah nonplanar. Bukti Di sini n = 5 dan



e=



5x 4 =10 sehingga 3 n−6=9 . Jadi 2



e ≥ 3 n−6 dan



sebagainya, dengan teorema itu, G = K5 tidak planar. Konsekuensi 5.9 K3,3adalah nonplanar. Bukti KarenaK3,3 adalah bipartit tidak mengandung siklus ganjil (dari Teorema 1.3) dan sehingga tidak ada siklus yang panjangnya tiga. Oleh karena itu, setiap muka dari gambar bidang K3,3, jika seperti itu ada, harus memiliki setidaknya empat sisi batas. Jadi, dengan menggunakan argumen pembuktian Teorema 5.6, didapatkan b≥4 f dan kemudian jika 4f≤ 2e, yaitu, 2f ≤ e = 9. Hal ini memberikan f ≤ 9/2. Namun, dengan Formula Euler, f* = 2-n + e = 2 - 6 + 9 = 5, sebuah kontradiksi. 5.6 DUAL DARI GRAF BIDANG Misalkan G graf bidang. didefinisikan Dual dari G dengan graf G* dibangun sebagai berikut.Untuk masing-masing f muka pada G terdapat simpul yang sesuai f* dari G* dan setiap sisi e pada G ada sisi e* yang sesuai di G* seperti jika sisi e terdapat di perbatasan dari dua muka f dan g kemudian e*gabungan sisidengan simpul yang sesuai f* dan g* di G*. (Jika e adalah sisi jembatan maka diperlakukan seolah-olah terjadi dua kali pada batas muka f di mana itu terletak dan kemudian sisi e* yang sesuai adalah kejadian loop dengan f* titik di G*)



Ternyata G* ganda dari graf bidang Gjuga planar.Ditunjukkan mengapa demikian adalah dapat digambarkanG* sebagai grafbidang. Diberikan gambar bidang dari G, tempatkan simpul f* dariG*di dalam muka yang sesuai f. Jika esisi terletak di perbatasan dua muka f dan gpada G, bergabung dengan dua simpul f* dan g* oleh sisi e* menggambarkan sehingga melintasi sisi e tepat satu kali dan tidak ada melintasi sisi lain dari G. (Prosedur ini masih memungkinkan jika e adalah sisi jembatan.) digunakan prosedur ini pada Gambar 5.35. Jika sisi eadalah loop dalam G maka sisi hanya pada batas umum dari dua muka, salah satunya, katakanlah f, terletak dalam wilayah bidangyang dikelilingi oleh e dengan lainnya, katakanlah g, terletak di luar daerahini. Muka f tidak mungkin satu-satunya muka tertutup oleh e tetapi, jelas dari definisi G*, setiap lintasan dari simpul h*, sesuai dengan mukah, ke simpulg* harus menggunakan sisi e* .Jadi e* adalah sebuah jembatan di G*. Sebaliknya, jika sisie* adalah jembatan di G*, bergabung dengan simpul f* dan g*, maka e* adalah satu-satunya jalan di G*dari f* untukf* ke g*. Ini berarti, dari definisi G*, bahwa esisi dalam G harus menyertakan salah satu fmuka dan g dan jugae harus loop. Untuk meringkas, esisi adalah loop dalam G jika dan hanya jika e* adalah sebuah jembatan di G*.



Gambar 5.35: Sebuah graf bidang dan dualnya Terjadinya sisiparallel padaG* mudah dijelaskan.Sebuah pikiran sejenak harus meyakinkan bahwa, mengingat dua muka f dang padaG, maka ada ksisi paralel antara f* dan g*di G* jika dan hanya jika f dang memiliki ksisi pada batas umum mereka. Mungkin disadari bahwa telah didefinisikan dual dari grafbidang bukan graf planar. G1 G2 Alasan ini adalah bahwa berbedanyabidang gambar dan dari graf planar G ¿ ¿ yang sama dapat menyebabkan non-isomorfik duals G1 dan G2 .



Teorema 5.16 Misalkan G menjadi graf bidang terhubung dengan n simpul, e sisi danf fakta.misalkan n*, e* dan f * menunjukkan jumlah simpul-simpul, sisi dan muka masing-masing dari G*. Kemudian n* = f, e* = e dan f* = n. BuktinyaYang pertama dua persamaan mengikuti dari definisi G*.Yang ketiga kemudian mengikuti dari Formula Euler karena kedua G dan G* yang terhubung grafbidang. Sekarang anggaplah bahwamuka φ dari graf bidangG, sesuai dengan titik v dari G, dimiliki



e ¿1 , ...,



e ¿n



sebagai sisi batasnya. Kemudian, dengan konstruksi dariG*,



masing-masing e* sisimelintasi sisi yang sesuai



ei



dari G, seperti yang diilustrasikan



pada Gambar 5.35, sisi ini semua kejadian dengan simpulv. Oleh karena itu,



φ



mengandung vtitik. Karena G* adalah grafbidang, juga dapat dibangun dual dari G*, yang disebut dual ganda G dan dilambangkan dengan G**.Dari pembahasan paragraf sebelumnya, hasil berikut ini mungkin tidak mengejutkan. Teorema 5.17 Misalkan G menjadi graf bidang terhubung.Kemudian G isomorfis ke G** bisa dilakukan dual. Bukti Seperti yang terlihat di atas, setiap muka φ dari dualG** mengandung setidaknya satu titik dari G, yaitu yang sesuai titikv. Sebenarnya ini adalah satu-satunya titik dari G yang mengandung φ karena, menurut Teorema 5.16, jumlah muka dari G*adalah sama dengan jumlah simpul dari G. Oleh karena itu, dalam pembangunan dual ganda G**, dapat memilih titik v menjadi titik di G** sesuai dengan φ muka dariG*. Pilihan ini memberi isomorfisma dibutuhkan.