Formula Euler KLP 3 [PDF]

Citation preview

Makalah Matematika Diskrit “Formula Euler”



Kelompok 3: Dewi Mulyana



1705122572



Fisca Dwi Agustin



1705110853



Mu’tiah Silmi



1705121849



Seftia Wulandari



1705110936



Sri Indriyani



1705110952



Siti Nurzakiyah



1705113690



Dosen Pengampu: Dra. Susda Heleni, M.Pd



Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Unversitas Riau 2019



KATA PENGANTAR Puji syukur kami ucapkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya, sehingga kami dapat menyelesaikan makalah yang berjudul “Formula Euler”. Penyusunan makalah ini untuk memenuhi salah satu tugas mata kuliah yaitu Matematika Diskrit. Kami berharap baik penulis maupun pembaca memperoleh wawasan pengetahuan tentang formula euler. Terlepas dari semua itu, kami menyadari sepenuhnya bahwa masih ada kekurangan baik dari segi susunan kalimat maupun tata bahasanya. Oleh karena itu, kami sangat mengharapkan kritikan dan saran dari pembaca untuk melengkapi segala kekurangan dan kesalahan dari makalah ini. Kami juga mengucapkan terima kasih kepada pihak-pihak yang telah membantu selama proses penyusunan makalah ini.



Pekanbaru, Oktober 2019



Penulis



i



DAFTAR ISI



KATA PENGANTAR ............................................................................................ i DAFTAR ISI .......................................................................................................... ii BAB I PENDAHULUAN ...................................................................................... 1 1.1



Latar Belakang ....................................................................................... 1



1.2



Rumusan Masalah .................................................................................. 1



1.3



Tujuan ..................................................................................................... 1



BAB II PEMBAHASAN ....................................................................................... 2 Formula Euler ................................................................................................... 2 DAFTAR PUSTAKA ............................................................................................ 9



ii



iii



BAB I PENDAHULUAN



1.1 Latar Belakang Perkembangan teori graph pernah mengalami kemacetan yang agak lama, namun sejak ditemukannya kriteria kesebidangan untuk raph maka perkembangan teori graph menjadi pesat lagi. Kriteria kesebidangan graph dan sifat-sifatnya pada bidang datar perlu diketahui untuk dapat memahami penerapan maupun untuk mempelajari bagian selanjutnya dari teori graph, salah satunya formula euler.



1.2 Rumusan Masalah Bagaimana cara membuktikan formula euler



1.3 Tujuan Mengetahui pembuktian formula euler



1



BAB II PEMBAHASAN



Formula Euler 2.1 Defenisi 4.3.1 Sebuah graph G membagi bidang menjadi beberapa daerah yang masingmasing disebut muka (face). Lambang (notasi) muka disimbolkan dengan f. Himpunan semua “muka” graph bidang G dilambangkan dengan F(G). 2.2 Definisi 4.3.2 Banyaknya sisi G yang membatasi suatu muka f dari G disebut derajat dari muka f dan dinotasikan dengan 𝑑𝐺 (f) atau d(f). Contoh 1: perhatikan gambar berikut!



b



a 𝒇𝟐 𝒇𝟏 g



i



h



𝒇𝟑



𝒇𝟕



𝒇𝟓



𝒇𝟒



c 𝒇𝟔



f



d



e



Pada gambar tersebut terdapat 9 titik, 14 sisi dan 7 muka yaitu f1, f2, f3, f4, f5, f6, f7. Jadi F(G)={𝑓1 , 𝑓2 , 𝑓3 , 𝑓4 , 𝑓5 , 𝑓6 , 𝑓7 }. Terdapat 4 sisi yang membatasi muka f1 yaitu ai, hi, gh, dan ag, dengan demikian d(f1)=4. Terdapat 3 sisi yang membatasi f2 yaitu ai, bi, dan ab, dengan demikian d(f2)=3. Dan begitu juga untuk yang lainnya. 2.3 Teorema 4.3.1 Formula Euler : jika G graph bidang terhubung maka : |𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 2 Bukti :



2



Pembuktian teorema ini dapat dilakukan dengan induksi pada |𝐸(𝐺)| 



Untuk |𝐸(𝐺)| = 0, diperoleh |𝑉(𝐺)| = 1 dan |𝐹(𝐺)| = 1 Sehingga |𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 1 − 0 + 1 = 2 benar







Asumsikan pernyataan berikut benar : jika G graph bidang terhubung dengan |𝐸(𝐺)| ≥ 1, maka |𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 2







Akan ditunjukkan pernyataan itu juga benar untuk |𝐸(𝐺)| = 𝑘 + 1 maka |𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 2.misalkan G adalah sebuah graph bidang terhubung dengan 𝑘 + 1 sisi. Terdapat dua kasus, dalam hal ini : (1) G memuat sikel, (2) G tidak memuat sikel.



Kasus 1 : G memuat sikel Misalkan e adalah sebuah sisi di sikel yang terdapat di G. Maka graph 𝐺1 = 𝐺 − 𝑒 merupakan graph bidang terhubung dengan 𝑘 sisi. Berdasarkan asumsi berlaku |𝑉(𝐺1 )| − |𝐸(𝐺1 )| + |𝐹(𝐺1 )| = 2. Selanjutnya karena : |𝑉(𝐺1 )| = |𝑉(𝐺)| |𝐸(𝐺1 )| = |𝐸(𝐺)| − 1 dan |𝐹(𝐺1 )| = |𝐹(𝐺)| − 1 Maka : |𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = |𝑉(𝐺1 )| − (|𝐸(𝐺)| + 1) + (|𝐹(𝐺)| + 1) = |𝑉(𝐺1 )| − |𝐸(𝐺1 )| − 1 + |𝐹𝐺1 | + 1 = |𝑉|(𝐺1 ) − |𝐸(𝐺1 )| + |𝐹𝐺1 | =2



3



Kasus 2 : G tidak memuat sikel Karena G graph terhubung dan tidak memuat sikel maka G pohon. Karena G pohon maka G memuat sebuah titik yang berderajat satu. Misalkan u adalah titik berderajat satu di G. Maka graph H = G – u tetap merupakan pohon sehingga H graph bidang terhubung dengan k sisi. Berdasarkan asumsi berikut : |V(H)| − |E(H)| + |F(H)| = 2 Karena : |V(H)| = |V(G)| − 1 |E(H)| = |E(G)| − 1 |F(H)| = |F(G)| Maka: |V(G)| − |E(G)| + |F(G)| = 2 (|V(H)| + 1) − (|E(H)| + 1) + |F(H)| = 2 |V(H)| − |E(H)| + |F(H)| = 2 Dengan demikian teorema terbukti



Contoh : Mungkinkah menggambar sebuah graph bidang terhubung yang memiliki 50 titik, 54 sisi dan 7 muka. Penyelesaian : Berdasarkan Formula Euler jika G graph terhubung maka |V(G)| − |E(G)| + |F(G)| = 2 Sehingga 50 − 54 + 7 = 3 3≠2 Jadi tidak mungkin menggambarkan sebuah graph bidang terhubung dengan 50 titik, 54 sisi dan 7 muka Catatan : Formula Euler tidak berlaku untuk graph bidang tak terhubung 4



Misalnya untuk graph bidang tak terhubung G pada gambar berikut



Pada gambar |𝑉(𝐺)| = 5, |𝐸(𝐺)| = 4, dan |𝐹(𝐺)| = 2, sehingga : |V(G)| − |E(G)| + |F(G)| = 2 5−4+2= 3 3≠2



2.4 Teorema 4.3.2 Jika G graph sederhana planar dengan |𝐸(𝐺)| > 1, maka |𝐸(𝐺)| ≤ 3|𝑉(𝐺)| − 6 Bukti : Akan ditinjau dua kasus : G terhubung atau tidak terhubung.



Kasus 1 : G graph terhubung Misalkan G1 = embedding G, jelas bahwa |V(G1 )| = |V(𝐺)| dan |E(G1 )| = |E(𝐺)| , karena G1 isomorfik dengan G. Jika |E(𝐺)| = 2 , maka |V(𝐺)| = 3 (karena G sederhana dan terhubung). Sehingga : |E(𝐺)| = 2 ≤ 3 = 3|V(𝐺)| − 6 Jika |E(𝐺)| ≥ 3, maka |E(G1 )| ≥ 3 Karena G1 sederhana dan |E(G1 )| ≥ 3, d(f) ≥ 3, ∀f F(G1 ) . Dengan demikian :



5



≥ 3|F(G1 )| ... (1) Karena setiap sisi G1 membatasi paling banyak dua muka, ∑𝑓∈𝐹(G1 ) d(f) ≤ 2|E(G1 )| ... (2) Dari (1) dan (2) diperoleh : 3|F(G1 )| ≤ 2|E(G1 )| ... (3) Dari teorema 4.3.1 diperoleh : |F(G1 )| = 2 + |E(G1 )| − |V(G1 )| Sehingga (3) menjadi : 3(2 + |E(G1 )| − |V(G1 )|) ≤ 2|E(G1 )| Ekivalen dengan : |E(G1 )| ≤ 3|V(G1 )| − 6 Karena |E(G1 )| = |E(𝐺)| dan |V(G1 )| = |V(𝐺)| , maka : |E(G)| ≤ 3|V(G)| − 6 Jadi teorema terbukti untuk kasus G graph terhubung.



Kasus 2: G graph tak terhubung Misalkan 𝐺1 , 𝐺2 , . . . , 𝐺𝑘 adalah komponen-kompenen G dimana k≥ 2. Karena G planar ∀𝑖, 1 ≤ 𝑖 ≤ 𝑘, 𝐺𝑖 terhubung dan planar. Misalkan dari k komponen tersebut,terdapat 𝑘1 ,Komponen yang masingmasing komponen berisi satu titik (nol sisi), 𝑘2 komponen yang masingmasing komponen berisi satu sisi (dua titik), dan 𝑘3 komponen yang maisng-masing berisi lebih dari satu sisi. Jelas bahwa: 𝑘1 + 𝑘2 + 𝑘3 = 𝑘 6



Misalkan: |𝐸 (𝐺1 )| = 0 , ∀𝑖, 1 ≤ 𝑖 ≤ 𝑘1 |𝐸 (𝐺1 )| = 1 , ∀𝑖, 𝑘1 + 1 ≤ 𝑖 ≤ 𝑘1 + 𝑘2 |𝐸 (𝐺1 )| ≥ 2 , ∀𝑖, 𝑘1 + 𝑘2 + 1 ≤ 𝑖 ≤ 𝑘 Akan ditinjau 𝑘3 =0 dan 𝑘3 ≥ 1



Sub kasus 2.1 : 𝑘3 =0 Dalam hal ini, |𝑉 (𝐺)| = 𝑘1 + 2𝑘2 , dan |𝐸 (𝐺)| = 𝑘2 Karena 𝑘3 = 0 dan |𝐸 (𝐺)| ≥ 0 didapatkan |𝐸 (𝐺)| = 𝑘2 ≤ 6𝑘2 − 6 + 𝑘1 =3 (𝑘1 + 2) − 6 = 3|𝑉 (𝐺)| − 6



Sub kasus 2.2 : 𝑘3 ≠ 0(𝑘3 ≥ 1) Dalam hal ini, 1 1 + 𝑘2 |𝐸 (𝐺)| = ∑𝑘𝑖=1 |𝐸 (𝐺𝑖 )| + ∑𝑘𝑖=𝑘 |𝐸 (𝐺𝑖 )| + ∑𝑘𝑖=𝑘1 +𝑘2 +1 |𝐸 (𝐺𝑖 )| 1 +1



= 0 + 𝑘2 + ∑𝑘𝑖=𝑘1 +𝑘2 +1 |𝐸 (𝐺𝑖 )| ≤ 𝑘2 + ∑𝑘𝑖=𝑘1 +𝑘2 +1 (3|𝐸 (𝐺𝑖 )| − 6) = 3|𝑉 (𝐺)| − 6𝑘 + 3𝑘1 + 𝑘2 = 3|𝑉 (𝐺)| − 6 + (6 − 6𝑘 + 3𝑘1 + 𝑘2 ) Karena 𝑘3 ≥ 1 (dan 𝑘1 ≥ 0, 𝑘2 ≥ 0 maka: 3𝑘1 + 5𝑘2 + 6𝑘3 ≥ 6 Karena 𝑘3 = 𝑘 − 𝑘1 -𝑘2 , didapatkan: 7



3𝑘1 + 5𝑘2 + 6(k-𝑘1 − 𝑘2 ) ≥ 6



Jadi |𝐸 (𝐺)| ≤ 3|𝑉 (𝐺)| − 6 + (6 − 6𝑘 + 3𝑘1 + 𝑘2 ≤ 3|𝑉 (𝐺)| −6 Jadi teorema terbukti untuk kasus G graph tidak terhubung.



8



DAFTAR PUSTAKA



Heleni, Susda, dan Zulkarnain. 2006. Matematika Diskrit. Pekanbaru: Universitas Riau.



9