Download - 03 Graf Planar
![Page 1: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/1.jpg)
Sistem Informasi
Universitas Gunadarma
2012/2013
![Page 2: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/2.jpg)
Suatu graph disebut planar jika dapatdigambarkan dalam bidang tanpa adanya ruasberpotongan.
Sebuah graf dikatakan graf planar bila graftersebut dapat disajikan (secara geometri) tanpaadanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa adanya ruas yang berpotongandisebut dengan penyajian planar/map/peta.
![Page 3: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/3.jpg)
Graf yang termasuk planar :
1. Tree/Pohon
2. Kubus
3. Bidang Empat
4. Bidang Delapan Beraturan
Pada penyajian planar/map, dikenal istilah region. Derajat darisuatu region adalah panjang walk batas region tersebut.
Graf planar yang digambarkan dengan sisi-sisi yang tidak salingberpotongan disebut graf bidang (plane graph).
Sisi-sisi pada graf planar membagi bidang menjadi beberapawilayah (region) atau muka (face). Jumlah wilayah pada grafplanar dapat dihitung dengan mudah.
![Page 4: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/4.jpg)
Sebuah graf yang tidak dapat disajikan (secarageometri) tanpa adanya ruas yang berpotongandikenal sebagai graf non-planar.
![Page 5: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/5.jpg)
Jika G adalah graph planar denganv = banyaknya simpul
e = banyaknya ruas
f = banyaknya bidang/region (termasuk bidangyang terluar)
Maka berlaku :
v – e + f = 2
![Page 6: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/6.jpg)
Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.
Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.
Graf yang mempunyai sirkuit Euler disebut graf Euler(Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Euleriangraph).
![Page 7: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/7.jpg)
Teorema Kuratoswki berguna untuk menentukandengan tegas keplanaran suat graf.
Sifat graf Kuratowski adalah :
1. Kedua graf Kuratowski adalah graf teratur.
2. Kedua graf Kuratowski adalah graf tidak-planar.
3. Penghapusan sisi atau simpul dari graf Kuratowskimenyebabkannya menjadi graf planar.
4. Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan grafKuratowski kedua adalah graf tidak-planar denganjumlah sisi minimum.
![Page 8: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/8.jpg)
Graf G bersifat planar jika dan hanya jika ia tidakmengandung upagraf yang sama dengan salah satugraf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.
![Page 9: 03 Graf Planar](https://reader036.vdokumen.com/reader036/viewer/2022071702/55cf9b00550346d033a45ab7/html5/thumbnails/9.jpg)
TERIMA KASIH