Graf Planar (Matematika diskrit)
Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)
Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar,jika tidak, maka ia disebut graf tak-planar.
K4 adalah graf planar:
K5 adalah graf tidak planar:
Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).
Aplikasi Graf Planar
Persoalan utilitas (utility problem)
Aplikasi Graf Planar
· Perancangan IC (Integrated Circuit)
· Tidak boleh ada kawat-kawat di dalam ICboard yang saling bersilangan dapat menimbulkan interferensi arus listrik malfunction
· Perancangan kawat memenuhi prinsip graf planar
Ketidaksamaan e = 9, n = 6 tidak berlaku untuk K3,3 karena 9 <= (3)(6) – 6 = 12 (jadi, e <= 3n – 6) padahal graf K3,3 bukan graf planar!
Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit empat buah sisi, Dari penurunan rumus diperoleh e <= 2n – 4
Misalkan graf sederhana planar memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk?
Jawaban:
Diketahui n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 x 4 = 96.
Menurut lemma jabat tangan, jumlah derajat = 2 x jumlah sisi, sehingga jumlah sisi = e = jumlah derajat/2 = 96/2 = 48.
Dari rumus Euler, n – e + f = 2, sehingga f = 2 – n + e = 2 – 24 + 48 = 26 buah.
Jawaban:
Diketahui n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 x 4 = 96.
Menurut lemma jabat tangan, jumlah derajat = 2 x jumlah sisi, sehingga jumlah sisi = e = jumlah derajat/2 = 96/2 = 48.
Dari rumus Euler, n – e + f = 2, sehingga f = 2 – n + e = 2 – 24 + 48 = 26 buah.
Pada graf planar sederhana terhubung dengan f buah wilayah, n buah simpul, dan e buah sisi (e > 2) selalu berlaku: e <= 3n – 6
Ketidaksamaan yang terakhir dinamakan ketidaksamaan Euler, yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana kalau graf planar, maka ia memenuhi ketidaksamaan Euler, sebaliknya jika tidak planar maka ketidaksamaan tersebut tidak dipenuhi.
Contoh:
Pada K4, n = 4, e = 6, memenuhi ketidaksamaan Euler, sebab 6 <= 3(4) – 6. Jadi, K4 adalah graf planar.
Pada graf K5, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab 10 <= 3(5) – 6. Jadi, K5 tidak planar.
Pada graf K5, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab 10 <= 3(5) – 6. Jadi, K5 tidak planar.
Ketidaksamaan e = 9, n = 6 tidak berlaku untuk K3,3 karena 9 <= (3)(6) – 6 = 12 (jadi, e <= 3n – 6) padahal graf K3,3 bukan graf planar!
Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit empat buah sisi, Dari penurunan rumus diperoleh e <= 2n – 4
Contoh
Graf K3,3 pada Gambar di bawah memenuhi ketidaksamaan e <= 2n – 4, karena :
e = 9, n = 6 9 <= (2)(6) – 4 = 8 (salah) yang berarti K3,3 bukan graf planar.
Sangat membantu
BalasHapus