Materi GRAP PLANAR 2 [PDF]

Citation preview

GRAP PLANAR 2



OLEH : KELOMPOK 3 NAMA



: 1. TIWARNI ZAI 2. SUSI SABAR MENANTI HAREFA 3. NUR AYU ZEBUA 4. PNIEL SOZAWATO ZENDRATO



SEMESTER



: VI (ENAM)



MATA KULIAH



: MATEMATIKA DISKRIT



DOSEN PENGAMPU



: NETTY KARIANI MENDROFA, S.Pd.,M.Pd



INSTITUT KEGURUAN DAN ILMU PENDIDIKAN (IKIP) GUNUNGSITOLI FAKULTAS PEDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI PENDIDIKAN MATEMATIKA TAHUN AKADEMIK 2021



KATA PENGANTAR Puji syukur ke hadirat Tuhan Yang Maha Esa yang telah memberikan rahmat serta hidayahnya sehingga Kami dapat menyelesaikan Tugas Makalah kami ini yang berhubungan dengan Materi Grap Planar 2 (karakteristik, formula euler, ketebalan sebuah graph, grap dual dan graf polyhedral) . Materi ini dibuat guna memenuhi tugas Mata Kuliah sebagai media pembelajaran yang ringkas dan jelas sehingga Mahasiswa mampu memahami dengan lebih mudah dalam mata pelajaran metematika khususnya Materi Relasi Rekrusif .Secara keseluruhan Makalah ini sesuai kompetensi dasar Matematika dan standart yang ada. Kami sangat Berterimakasih Kepada Dosen Pegampu Mata Kuliah Matematika Diskrik Pendidikan Matematika Oleh Ibu Netty Kariani Mendrofa,M.Pd, sehingga terselesaikan Materi ini, dengan bimbingan dan arahan dari Ibu, Begitu juga dengan Teman-teman Kelompok yang saling memotivasi untuk menyelesaikan Materi ini dengan tepat waktu. Materi ini berisikan ringkasan – ringkasan materi tentang Grap Planar 2 dan ditulis dengan menggunakan bahasa yang sederhana sehingga pembaca mampu memahami materi dengan mudah. Penulis menyadari bahwa Materi ini masih jauh dari kata sempurna. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun dari semua pihak demi kesempurnaan Makalah berikutnya. Penulis berharap semoga Materi “Grap Planar 2.” ini dapat berguna dan bermanfaat bagi para pembaca khususnya bagi para peserta didik dan teman-teman Mahasiswa dalam menggunakan Makalah ini sebagai media pembelajaran.



Gunungsitoli, 8 Juni 2021



Kelompok 3



i



DAFTAR ISI KATA PENGANTAR................................................................................................... i DAFTAR ISI.................................................................................................................. ii BAB 1 PENDAHULUAN ............................................................................................. 1 1. Latar Belakang .................................................................................................... 1 2. Rumusan Masalah............................................................................................... 1 3. Tujuan ................................................................................................................. 1 BAB II PEMBAHASAN............................................................................................... 2 4.3.3 Formula Euler.................................................................................................... 2 4.3.4 Ketebalan Sebuah Graph................................................................................... 5 4.3.5 Graph Dual ........................................................................................................ 6 4.3.6 Graph Polyhedral .............................................................................................. 7 BAB III PENUTUP....................................................................................................... 10 A. Kesimpulan ......................................................................................................... 10 B. Saran ................................................................................................................... 10 DAFTAR PUSTAKA ................................................................................................... 11



ii



BAB I PENDAHULUAN A. Latar Belakang Matematika diskrit atau diskret adalah cabang matematika yang membahas segala sesuatu yang bersifat diskrit. Diskrit disini artinya tidak saling berhubungan (lawan dari kontinu) salah salah materi Matematika Distrik yang akan dibahas dalama makalah ini yaitu relasi rekrusuf tentang relasi rekrusif lenear dan relasi rekrusif linear homogen. Graph G disebut graph planar jika G dapat digambar pada bidang datar sedemikian sehingga sisi-sisinya tidak ada yang saling berpotongan kecuali mungkin pada titik-titik dari sisi-sisi tersebut. Graph bidang pasti graph planar, tetapi sebaliknya tidak berlaku. Materi Grap Planar yang akan kami bahas meliputi karakteristik, formula euler, ketebalan sebuah graph, grap dual dan graf polyhedral.



B. Rumusan Masalah Dalam materi relasi rekrusif ini, ada beberapa rumusan masalah antara lain sebagai berikut. 1. Bagaimanakah yang dimaksud dengan formula euler ? 2. Bagaimanakah yang dimaksud dengan ketebalan dari sebuah graph ? 3. Bagaimanakah yang dimaksud dengan graph dual ? 4. Bagaimanakah yang dimaksud dengan graph polyhedral ?



C. Tujuan Tujuan mempelajari relasi rekrusif adalah sebagai berikut. 1. Mengetahui konsep dan pengertian dari formula euler. 2. Mengetahui yang dimaksud dengan ketebalan dari sebuah graph. 3. Mengetahui yang dimaksud dengan graph dual. 4. Mengetahui yang dimaksud dengan graph polyhedral.



1



BAB II PEMBAHASANAN GRAPH PLANAR 2



4.3.3 FORMULA EULER Sebuah graph G membagi bidang menjadi beberapa daerah yang masing- masing disebut “Muka” (face),yang disimpulkan dengan f. Himpunan semua “muka” graph bidang G di notasikan dengan F(G). banyaknya sisi G yang membatasi suatu muka F dan G disebut derajat dari muka F dan dinotasikan dengan do (f) atau d(f). Contoh : Graph bidang G pada gambar dibawah ini mempunyai 4 muka yaitu f1,f2,f3,dan f4,



Dengan kata lain f(G) = { f1,f2,f3, f4}.terdapat 3 sisi G yang membatasi {b,c},{c,d},dan {b,d}.sehingga d(f1) = 3 begitu pula terdapat 4 sisi yang membatasi muka f3 yaitu {a,b},{b,d},{a,d} dan {a,e} jadi d(f3)= 4 mudah di cek bahwa d(f2) =d(f4) = 3



Teorema 4.3.2 Formula Euler Jika G graph bidang terhubung,maka │E (G) │ + │F(G) │ = 2 Bukti : induksi pada │E (G) │ Untuk │E (G) │= 0 diperoleh │v (G) │= 1 dan │F(G) │ = 1.sehingga │v (G) │- │E (G) │ + │F(G) │= 1 – 0 + 1 = 2 Asumsikan pernyataan tersebut benar : Jika G graph bidang terhubung dengan │E (G) │ = k ≥ 1,maka │v (G) │- │E (G) │ + │F(G) │ = 2 akan ditunjukkan pernyataan itu jika benar untuk │E (G) │ = k ≥ 1 misalkan G adalah graph bidang terhubung k + 1 sisi.



2



Kasus 1 : G memuat sikel Misalkan e adalah sebuah sisi di sikelnya G. Maka Graph H = G – e merupakan Graph bidang terhubung k sisi. Sehingga berdasarkan asumsi berlaku | V (H) | - | E(H) | + | F(H) | = 2.Selanjutnya karena | V (H) | = | V (G) |,| E(H) | = | E(G) | - 1 dan | F(H) | = | F(G) | - 1 | V (G) | - | E(G) | + | F(G) | = | V (H) | - ∁ | E(H) | + 1) +( | F(H) | + 1



= | V (H) | - ∁ | E(H) | + | F(H) | − 1 + 1 = 2



Kasus 2 : G tidak memuat sikel Karena G terhubung dan tidak memuat sikel, G pohon.jadi G memuat sebuah titik yang berderajat 1. Misalkan V adalah sebuah titik yang berderajat 1 di G.maka Graph T = G-V tetap merupakan pohon,jadi Graph bidang terhubung dengan k sisi.Sehingga berdasar asumsi berlaku | V (T) |– | E(T) | + | F(T) | = 2.karena | ( )| = | V(G) | − 1 ; |E(T) | = | E(G) | -1 dan | F(T) | = | F(G) |



Maka



= ∁ | V (T) |– | E(T) | + | F(T) |



|V (G) - |E(G) | + |F(G) |



= | V (T) |– | E(T) | + | F(T) | + 1-1 =2



Dengan demikian teorema terbukti. Teorema 4.3.3 Jika G graph sederhana planar dengan│E (G)│> 1,maka │E (G)│≤ 3│v (G)│6



Kasus 1 : G graph Terhubung Misalkan G1 = embedding G,jelas bahwa │v (G1) │= │v (G) │ dan │E (G1)│= │E (G)│karena G1 isomorfik dengan G.



Kasus 2 : graph tak terhubung Misalkan planar,



,



, . . .,



, 1≤ ≤ ,



adalah komponen – komponen G dimana



dan planar. Misalkan dari k komponen tersebut, terdapat



komponen yang masing – masing komponen berisi atau titik (nol sisi), masing – masing komponen berisi satu sisi (dua titik), dan berisi lebih dari satu sisi. Jelas



+



+



Tanpa menghilangkan keumuman, misalkan | ( )| = 0, | ( )| = 1,



,1 ≤ ≤ ,



≥ 2. Karena G



+1≤ ≤



+



=



3



komponen yang



komponen yang masing – masing



| ( )| = 2,



,



+



+1≤ ≤



= 0 dan



Selanjutnya kita tinjau dua sub kasus, yaitu =0



Sub kasus 2.1 : 2, maka



Dalam hal ini, | ( )| = ≥ 2.



≥ 2 dan



Sekarang untuk | ( )| =



≤6



≁0(



Sub kasus 2.2 :



= 3(



= 3 | ( )| − 6



| ( )| + −



= 0+ +



=



+ 3



(3| ( )| − 6)



+ (3| ( )| −



=



−2



= 3| ( )| − 6 + 3



+



) − 6( −



= 3| ( )| − 6 + (6 − 6 + 3 Karena



Karena



3 3



≥ 1 (dan +5



=



+5



−



+6



−



≥ 0,



+



+



−



)



)



≥ 0), maka



≥6



, diperoleh



+ 6( −



6−6 +3



Dengan demikian



| ( )|



| ( )|



| ( )|



−



≤0



= 0 dan | ( )| ≥



Dari kasus 1



| ( )| +



+



≤



. Karena



)−6



+2



≥ 1)



Dalam hal ini kita peroleh | ( )| =



+ 2 , dan | ( )| =



≥ 0 diperoleh



−6+3



≥1



) ≥ 6, atau



| ( )| ≤ 3| ( )| − 6 + (6 − 6 + 3



+



Teorema terbukti.



4



≤ 3| ( )| − 6



4.3.4 KETEBALAN DARI SEBUAH GRAPH Ketebalan (thickness) dari sebuah graph G dinotasikan dengan e(G), adalah minimum dari bilangan yang menyatakan banyaknya graphbagian – graph bagian planar dari G yang gabungannya sama dengan G. Ingat bahwa, gabungan dari dua graph G dan H, ditulis G ∪ H, adalah graph yang himpunan titiknya V(G) ∪ V(H) dan himpunan sisinya E(G) ∪ E(H). Contoh : ketebalan dari graph bipartisi komplit



,



adalah 2



∪



=



,



Subgraph planar dari ,



Subgraph planar dari ,



Perlu dicatat bahwa setiap graph planar G mempunyai ketebalan 1. Menentukan nilai eksak dari e(G) untuk sembarang graph G, merupakan masalah yang sulit. Sampai dewasa ini belum ada formula eksak untuk e(G), kecuali mungkin untuk graph – graph G tertentu. Tetapi, dengan menggunakan Teorema sebelumnya, dengan mudah dapat ditentukan batas bawah dari e(G) untuk sembarang graph sederhana G. TEOREMA 4.3.5 Jika G graph sederhana dengan | ( )| ≁ 2, maka e(G) ≥ Bukti :



| ( )| | ( )|



Untuk | ( )| = 1 diperoleh | ( )| = 0 dan e(G) = 1, sehingga e(G) = 1 ≥ 0 = | ( )| | ( )|



Selanjutnya, kita misalkan | ( )| ≥ 3. Karena setiap sunbgraph plaar dari G mempunyai



paling banyak 3| ( )| − 6 sisi, sedangkan banyaknya sisi G adalah | ( )|, maka banyaknya subgraph planar dari G yang gabungannya sama dengan G, paling sedikit Selanjutnya, karena e(G) bilangan bulat, maka



Dengan demikian teorema terbukti.



( )≥



| ( )| | ( )|



| ( )| 3 | ( )| − 6



Catatan : 1) Karena graph komplit dengan n titik,



, mempunyai



diperoleh 5



( − 1) sisi, maka untuk



≁2



(



) ≥



( − 1) 2 = 3 −6



( − 1) + 3( − 2) − 1 ( + 7)( − 2) 2 = = 3( − 2) 6( − 2)



Telah ditunjukkan oleh Beineke bahwa untuk n ≁ 4 (mod 6). (



)=



+7 6



+7 6



2) Dapat ditunjukkan bahwa graph sederhana G yang tidak memuat sikel dengan panjang 3, memenuhi hubungan berikut : | ( )| ≤ 2 | ( )| − 4. Sehingga graph bipartisi komplit ,



memenuhi hubungan berikut : (



,



)≥



2(



+



− 2)



4.3.5 GRAPH DUAL Pandang sebuah graph planer G yang digambar pada bidang sedemikian hingga tidak ada sisi-sisi G yang “saling berpotongan” kecuali mungkin pada titik-titik akhir sisi-sisi tersebut. Konstruksi sebuah graph G* sedemikian hingga : (i) setiap titik G* berkorespondesi dengan sebuah “nuka” dari G; (ii). Jika sebuah sisi E membatasi muka yang berkorespondesi dengan



dan



dan



di G maka titik-titik G*



dihubungkan dengan sebuah sisi. Graph G* yang



dikontruksi seperti di atas disebut graph dual diri G. Contoh :



Graph G adalah graph yang digambar “tebal”, sedangkan dual dari G (G*) adalah graph yang digambar “tipit \ dengan garis putus-putus.” Dari uraian di atas, antara “unsur-unsur” graph G dan G* terdapat korespondesi satu-satu sebagai berikut : a) Sebuah “muka” G berkorespondesi dengan sebuah titik G*. Ini berakibat | F (G) | = |V(G*)|



b) Sebuah sisi G berkorespondesi dengan sebuah sisi G*.



6



Jadi, | E (G) | = | E (G*) |. c) Sebuah muka berderajat K di G berkorespondesi dengan sebuah titik berderajat K di G* sehingga : Ʃ d (f) = Ʃ d (v) f F (G)



v V(G*)



d) Sebuah sisi yang terkait dengan sebuah titik yang berderajat satu di G, berkorespondesi dengan sebuah gelung (loop) di G*. e) Sebuah titik berderajat dua di G, berkorespondesi dengan sepasang sisi rangkap di G*.



4.3.6 GRAPH POLYHENDRAL Bangun ruang dimensi 3 (padat) yang dibatasi oleh permukaan-permukaan yang berupa bidang datar polygonal (bidang datar segi-n, n ≥ 3) disebut polyhedron. Apabila untuk setiap dua “titik interior” polyhedron dihubungkan dengan sebuah dengan sebuah ruas garis dan ternyata keseluruhan ruas garis tersebut terletak di “interior” polyhedron, maka polyhedron tersebut dikatakan polyhedron koveks. Selanjutnya, polyhedron konveks yang setiap “permukaannya” berupa bidang-bidang datar polygonal beraturan yang kongruen disebut polyhedron beraturan. Sebagai contoh, balok “padat” adalah polyhedron dan kubus “padat” adalah polyhedron beraturan. Titik-titik dan sisi-sisi dari sebuah polyhedron (sheleton) membentuk sebuah graph sederhana diruang dimensi 3. Jika polyhedron itu konveks, maka “selekton (kerangka)nya” berupa graph bidang (planer) sederhana dan terhubung yang disebut graph polyhedral. Perhatikan bahwa dalam graph polyhedral derajat setiap titik paling sedikit 3. Begitu pula derajat setiap muka paling sedikit 3.



Polyhedron



graph polyhedral



(kubus)



(kubus)



Selanjutnya, akan ditunjukkan bahwa hanya terdapat 5 macam polyhendron beraturan. Misalkan G adalah graph bidang (planar) terhubung. Derajat dari setiap titik G adalah k ≥ 3 dan derajat dari setiap titik G adalah



≥ 3 dan derajat dari setiap muka G adalah n ≥ 3. 7



Berdasarkan “Lemma Jabat Tangan”, diperoleh | E(G)| =



∑



( )



( )=



Karena setiap sisi membatasi tepat dua muka, ∑



( ) = 2| ( )|



( )



Selanjutnya, karena d(f) = m V f



Diperoleh n |F(G)| = k |V(G), atau |F(G)| =



| ( )|



( ) dan |E(G)| =



| ( )|



……………….(i)



|V(G)|,



……………………(ii)



Dari formula Euler kita tahu bahwa |F (G)| - |E (G)| + |F (G)| = 2



……………………(iii)



Dari persamaan-persamaan (i), (ii), dan (iii) diperoleh | V (G) | =



………………………(iv)



Karena |V (G) | > 0 dan 4m > 0, 2m – km +2k > 0 Ekuivalen dengan (k – 2) (m – 2) < 4



……………………….(v)



Karena k dan m bilangan bulat dengan k ≥ 3 dan n ≥ 3, maka semua kemungkinan nilai-nilai k dan m yang memenuhi v adalah :



K = 3 dan m = 3, atau K = 3 dan m = 4, atau K = 3 dan m = 5, atau K = 4 dan m = 3, atau K = 5 dan m = 3, Karena hanya ada 5 kemungkinan nilai-nilai k dan m, maka terbukti hanya ada 5 graph polyhedron beraturan . a. Untuk k = 3 dan m = 3, dari (iv) didapat |V (G)| = 4, dari (i) didapat |E (G) | = 6 dan dari (ii) didapat |F (G) | = 4. Sehingga diperoleh polyhedron beraturan berikut yang disebut, “tetrahedron”



tetrahedron graph



bangun ruang 8



b. Untuk k = 3 dan m = 4 diperoleh |V (G) | = 8 ; |E (G) | = 12 dan |F (G) | = 6. Sehingga diperoleh polyhedron beraturan yang disebut kubus.



kubus



c. Untuk k = 3 dan m = 5 diperoleh |F (G) | = 20 ; |F (G) | = 30 dan | F (G) | = 12. Didapat polihendron beraturan yang disebut dodecahedron.



dodecahedron



d. Untuk k = 4 dan m = 3 diperoleh |V (G) | = 6 ; |E (G) | = 3 Didapat octahendron



Detahendron



e. Untuk k = 5 dan m = 3 diperoleh |V (G) | = 12 ; |E (G) | = 32 dan |F (G) | = 20 Didapat polyhendron beraturan yang disebut icosahedrons



icosahedros



9



BAB III PENUTUP A. Kesimpulan 1. Sebuah graph G membagi bidang menjadi beberapa daerah yang masing- masing disebut “Muka” (face),yang disimpulkan dengan f. Himpunan semua “muka” graph bidang G di notasikan dengan F(G). banyaknya sisi G yang membatasi suatu muka F dan G disebut derajat dari muka F dan dinotasikan dengan do (f) atau d(f). 2. Jika G graph bidang terhubung,maka │E (G) │ + │F(G) │ = 2 3. Ketebalan (thickness) dari sebuah graph G dinotasikan dengan e(G), adalah minimum dari bilangan yang menyatakan banyaknya graphbagian – graph bagian planar dari G yang gabungannya sama dengan G 4. Graph G adalah graph yang digambar “tebal”, sedangkan dual dari G (G*) adalah graph yang digambar “tipit \ dengan garis putus-putus.” 5. Bangun ruang dimensi 3 (padat) yang dibatasi oleh permukaan-permukaan yang berupa bidang datar polygonal (bidang datar segi-n, n ≥ 3) disebut polyhedron. B. Saran Setelah mempelajari materi ini diharapakn kita mampu menerapkan dan mengaplikasikan ini dalam kehidupan sehari-hari. Akhir kata semoga materi ini menjadi media pembelajaran yang dapat dipergunakan. Kritikan dan saran sangat diperlukan sehingga makalah ini dapat lebih baik ke depannya.



10



DAFTAR PUSTAKA



Budayasa, Ketut. 1994. Matematika Diskrit 1. Surabaya : IKIP Surabaya Yarman, 2003. Matematika Diskrit . Padang : Universitas Negeri Padang



11