5 0 224 KB
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.