BAB 8 GRAPH PLANAR

      

    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.

Graph bidang pasti merupakan Graph Planar, tapi Graph Planar belum tentu Graph Bidang.

Contoh Graph Planar

graph yang termasuk planar anatara lain

• 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 sampai disini dulu ya teman-teman, kalau kalian penasaran, dan mau bertanya-tanya kalian tulis aja dikolom komentar. Minggu depan aku isi materi selanjutnya. 

Semoga bermanfaat bagi pembaca. Akhir kata

Wassalamualaikum 😊