Uji planaritas suatu graf
| Main Author: | LusianaEvianti |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2008
|
| Subjects: | |
| Online Access: |
http://repository.ub.ac.id/151922/1/050803424.pdf http://repository.ub.ac.id/151922/ |
Daftar Isi:
- Graf tak berarah G ? ? V,E ? disebut graf planar jika graf tersebut dapat digambar pada bidang datar sedemikian sehingga sisisisinya tidak ada yang berpotongan. Untuk mengetahui suatu graf planar atau tidak, digunakan Teorema Kuratowski, yaitu dengan mengetahui ada tidaknya subdivisi dari K 3,3 atau K 5 pada suatu graf G . Dalam pembuktian Teorema Kuratowski akan digunakan dasar dua lemma dan konsep himpunan bridge B dalam suatu cycle C . Untuk menguji planaritas suatu graf, akan digunakan algoritma Demoucron, Malgrange dan Pertuiset , yaitu dengan menentukan G i ? ~ F(B, untuk tiap bridge B pada i G dengan 1 ? i ? k ? q ? p ? 1 . Jika F(B,G ~ i ) ? 0 maka G adalah graf nonplanar , untuk 0 ~ ? ) i G F(B, dengan i i G ~ H ~ ? adalah G ? admissible dan E ( G ) ? E ( G i ) ? ? , maka G adalah graf planar .