Assalamualaikum teman teman, kali ini kita (aku *Dewi Asyiyah dan satu teman ku Danang Prasetyo) akan membahas mengenai teori graph, sebelum kita membahas pokok materi, alangkah lebih baik kita mengetahui apa itu teori graph, teori graph adalah kumpulan dari titik (node) dan garis dimana pasangan-pasangan titik (node) tersebut dihubungkan oleh segmen garis. node ini biasa disebut simpul (verteks) dan segmen garis disebut dengan ruas (edge).
nah setelah kita membahasa definisi graph. di dalam bab ke 9 yaitu membahsa mengenai kesebidangan graph.
Kesebidangan
sisi yang saling berpotongan dalam diagram graf membentuk titik potong (titik interseksi atau crossover). Jika G adalah graph yang digambar pada sebuah permukaan S demikian sehingga tiak ada dua sisi yang berpotongan, maka kita katakan bahwa G dibentangkan pada S. Sebuah graph yang dapat dibentangkan pada sebuah bidang tanpa titik interseksi disebut Graph Planar. sebuah graph yang tidak planar disebut Graph Non Planar.
Jika sebuah graph planar yang telah dibentangkan pada sebuah bidang sedemikian sehingga tidak ada interseksi yang terjadi, disebut dengan Graph Datar/ Bidang.
Grap G disebut Graph Planar Maksimal jika penambahan sebuah sisi baru pada G mengakibatkan G menjadi Graph Non Planar.
Contoh Graph Planar
graph yang termasuk planar anatara lain
Pembuktian
Setelah memahami beberapa macam Graph kita akan mengidentifikasi tentang macam-macam teorema yang berkaitan dengan Graph Planar. diantara lain yaitu
1. Teorema Kuratowski
Sebuah Graph adalah planar jika dan hanya jika graph tersebut tidak mengandung sebdivisi dari K5 dan K3,3 sebagai Graph bagian.
2. Teorema Euler
Jika G meriupakan sebuah Graph terhubung dengan n Simpul, dan m sisi, serta f muka, maka
nah setelah kita membahasa definisi graph. di dalam bab ke 9 yaitu membahsa mengenai kesebidangan graph.
Kesebidangan
sisi yang saling berpotongan dalam diagram graf membentuk titik potong (titik interseksi atau crossover). Jika G adalah graph yang digambar pada sebuah permukaan S demikian sehingga tiak ada dua sisi yang berpotongan, maka kita katakan bahwa G dibentangkan pada S. Sebuah graph yang dapat dibentangkan pada sebuah bidang tanpa titik interseksi disebut Graph Planar. sebuah graph yang tidak planar disebut Graph Non Planar.
Jika sebuah graph planar yang telah dibentangkan pada sebuah bidang sedemikian sehingga tidak ada interseksi yang terjadi, disebut dengan Graph Datar/ Bidang.
Grap G disebut Graph Planar Maksimal jika penambahan sebuah sisi baru pada G mengakibatkan G menjadi Graph Non Planar.
Graph bidang pasti merupakan Graph Planar, tapi Graph Planar belum tentu Graph Bidang.
- tree/ pohon
- kubus
- bidang empat
- bidang delapan beraturan
Contoh Graph Non Planar
Pembuktian
Setelah memahami beberapa macam Graph kita akan mengidentifikasi tentang macam-macam teorema yang berkaitan dengan Graph Planar. diantara lain yaitu
1. Teorema Kuratowski
Sebuah Graph adalah planar jika dan hanya jika graph tersebut tidak mengandung sebdivisi dari K5 dan K3,3 sebagai Graph bagian.
2. Teorema Euler
Jika G meriupakan sebuah Graph terhubung dengan n Simpul, dan m sisi, serta f muka, maka
n-m+f=2
Contoh Soal
tentukan jumlah wilayah pada graph planar berikut!
Jawab
kita gunakan rumus euler
f=e-n+2=11-7+2=6
Jadi, jumlah wilayahnya adalah 6
3. Teorema
misalkan G adalag Graph Planar Maksimal dengan n simpul dan m sisi, dan lebih besar sama dengan. maka berlaku
m=3n-6
Akibat
Jika G adalah Graph Planar dengan n simpul dan m sisi, dan n lebih besar sama dengan, maka berlaku m kurang dari sama dengan 3n-6.
Akibat
Setiap graph planar memuat sebuah simpul dengan derajat paling banyak 5.
Nah cukup sampaidisini dulu ya teman-teman, kalau kalian penasaran, dan mau bertanya-tanya kalian tulis aja dikolom kometar. Minggu depan aku isi materi selanjutnya.
Semoga bermanfaat bagi yang pembaca. Akhir kata
Wassalamualaikum 😊
Komentar
Posting Komentar