Graf Planar dan Dual Graf

Posted on

1.Graf Planar (Planar Graph)
Graf Planar adalah Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling berpotongan.
Contoh :

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan dinamakan graf bidang (plane graph).
Contoh:

Gambar Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang
Sebuah graf bidang dapat digambar sebagai graf planar dengan pemetaan dari tiap-tiap simpul ke suatu posisi dalam ruang dua dimensi, dan dari setiap sisi ke sebuah kurva bidang (plane curve), dimana masing-masing kurva memiliki dua titik ekstrim, yang bertepatan dengan posisi dari simpul terakhir, dan semua kurva terpisah kecuali pada titik ekstrimnya.
Kesamaan jenis dalam hal bentuk (topologi) yang padanannya digambar pada sebuah bidang disebut pemetaan planar (planar map). Walaupun graf bidang memiliki wilayah luar atau bidang yang tidak terbatas, tidak ada wilayah dari pemetaan planar yang memiliki keadaan khusus.
Graph planar yang terdiri atas 6 wilayah

TEOREMA KURATOWSKI (Kashimir Kuratowski, Polandia) untuk menentukan keplanaran suatu graf

Teorema Kuratowski :
“ Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya “

Sifat GRAF Kuratowski adalah :
1.kedua graf kuratowski adalah graf teratur
2.kedua graf kuratowski adalah graf non-planar
3.penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4.K5 adalah graf non-planar dengan jumlah simpul minimum, K3,3 adalah graf non-planar dengan jumlah sisi minimum.

2.Dual Graf
“ sebuah graf planar G yang direpresentasikan dalam graf bidang, mempunyai graf G* yang secara geometri merupakan dual dari graf planar G “
contoh:

Cara membuat Dual Graf:
1.Pada setiap wilayah atau muka (face) f di G, dibuat sebuah simpul v* yang merupakan simpul untuk G*
2.Untuk setiap sisi e di G, ditarik sisi e* (yang menjadi sisi untuk G*) yang memotong sisi e tersebut. Sisi e* menghubungkan dua buah simpul v1* dan v2* (simpul-simpul di G*) yang berada di dalam muka f1 dan f2 yang dipisahkan oleh sisi e di G. untuk sisi e yang salah satu simpulnya merupakan simpul berderajat 1 (jadi, sisi e seluruhnya terdapat di dalam sebuah muka), maka sisi e* adalah berupa sisi gelang

One thought on “Graf Planar dan Dual Graf

    ana tri suci said:
    February 28, 2010 at 19:22

    assalamualaikum k,trima kasih k, tulisan kakak dah membantu tugas saya, yaitu mata kuliah matematika diskrit. saya mau nanya, kakak tau g cara membuktikan bahwa K5 bukan merupakan palar graph, tolong kasih tau alasanya ya k?

Terima Kasih Sudah berkunjung ke Blog saya. Dan Jangan Lupa Isi Komentar di Bawah ini.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s