graph planar (planar graph)
Post on 09-Dec-2015
363 Views
Preview:
DESCRIPTION
TRANSCRIPT
GRAPH PLANAR dan Graf bidang (Planar Graph and Plane Graph)
KELOMPOK 8 :
Nur Eva mayasari
1
Dosem pengampu : Dr. Fadli, M.Pd.
GRAPH PLANAR (Planar Graph)DAN
GRAPH SEBIDANG (Plane Graph)
2
Graf yang dapat digambarkan pada bidang datar dengan cara demikian hingga tidak ada rusuk-rusuk yang saling berpotongan kecuali pada simpul-simpulnya maka di sebut graf planar
Sedangkan graf sebidang adalah graf planar yang telah di gambarkan di bidang datar sedemikian rupa sehingga tidak ada lagi rusuk-rusuk yang berpotongan
Contoh Graf planar
Gambar (a) Graf Planar dan (b) graf bidang
3
Contoh planar Contoh non Planar
Perhatikan gambar di atas adalah graph sebidang dan perhatikanlah bagian-bagian bidang datar yang ditinggalkan setelah kita mengangkat rusuk-rusuk dan simpul-simpul dari yang membentuk salah satu bidang disebut wilayah.
G1G2
Graf disamping memiliki yaitu simpulrusuk dandaerah atau wilayah Maka dalam suatu graf planar berlaku rumus euler
4
Salah satu Graf yang termasuk planar antara lain :Tree / Pohon, Kubus, Bidang Empat, Bidang Delapan Beraturan,
RUMUS EULER menentukan suatu jumlah wilayah, jumlah sisi dan jumlah simpul pada graf planar dapat digunakan rumus euler yaitu
Dengan: = jumlah sisi = jumlah simpul daerah
Contoh : Pada gambar Berapa banyak daerah dari graf tersebut ?
5
Penyelesaian : Diketahui = 11 , Dari rumus Euler, , sehingga kita dapatkan
r = 2 – p + q = = 6 buah.r = 6 buah
6
seandainya graf adalah pohon maka berlaku rumus ,dan wilayah yang diciptakan pohon
Contoh : Tentukan atau banyak rusuk dari pohon dibawah jika di ketahui
Penyelesaian :
7
Pada graf planar sederhana terhubung jika G adalah graf sebidang terhubung dengan banyak simpul. dan banyak rusuk maka berlaku . Misalkan = 3 maka yang mungkin paling banyak adalah 3 dan yang mungkin adalah 2. Jadi setiap di batasi oleh 3 rusuk karena rusuk maka :
Suptitusi ke rumus euler
8
Contoh :
Misalkan = 3 dan 2, maka yang mungkin adalah
Untuk maka
Hal ini dinyatakan dengan corallary berikut:
COROLLARY 1 Jika G adalah graf sederhana terhubunga dengan adalah jumlah sisi dan adalah jumlah simpul, yang dalam hal ini , maka berlaku ketidaksamaan Euler
9
Contoh :Tentukan apakah graf lengkap K5 adalah
planar?
Penyelesaian : Diketahui bahwa K5 memiliki dan makasehingga
maka dari hasil tersebut dapat dikatakan bahwa K5 termasuk non planar.
Persamaan ini digunakan untuk menentukan suatu graf terhubung planar atau non planar tetapi persamaan ini hanya syarat perlu agar suatu graf dikatakan planar tetapi bukan syarat cukup
10
Contoh bahwa pernyataan ini benar akan di lakukan uji coba pada graf K3,3 atau graf bipartit.
Dari gambar maka diketahui bahwa K3,3 memiliki dan maka
Padahal graf K3,3 bukan graf planar dilihat dari bukti sebuah gambar
11
COROLLARY 2 : Jika G adalah graf sederhana terhubung dengan q adalah jumlah sisi dan p adalah jumlah simpul, yang dalam hal ini p dan tidak ada sirkuit yang panjangnya 3, maka berlaku q Contoh Soal:
𝑒
𝑎 𝑏
𝑑 𝑐
12
Teorema Kuratowski
Teorema Kuratowski “Sebuah graf G planar jika dan hanya jika G tidak
mengandung sebuah subgraf yang isomorphik dengan K5 dan K3,3”.
Contoh :Tentukan bahwa graf G pada gambar tidak planar dengan
menggunakan teorema kuratowski?
𝑓 𝑏𝑔
h𝑒
𝑑𝑐
13
langkah penyelesaian
Mencari subgrap dengan menghilangkan rusuk
𝑓 𝑏𝑔h
𝑒
𝑑𝑐
𝑎
𝑓 𝑏𝑔h
𝑒
𝑑
𝑐
14
Membuat graf yang isomorphik dengan salah satu graf K5 atau K3,3 dengan melakukan reduksi seri pada graf yaitu jika sebuah graf G mempunyai simpul yang berderajat 2 yaitu rusuk (V,V1) dan (V,V2) maka akan dilakukan penghapusan simpul dari dua rusuk yang menghasilkan satu rusuk yang terhubung yaitu (V1, V2) maka
𝑓 𝑏𝑔h
𝑒
𝑑𝑐
𝑓 𝑏𝑔h
𝑒
𝑑𝑐
top related