GRAF- MATDIS

GRAF

matematika diskrit

graf planar

Sebuah graf G = (V,E) disebut graf planar apabila graf tersebut dapat digambarkan dalam sebuah bidang datar tanpa ada sisi/edge yang saling berpotongan (kecuali sisi sisi berpotongan pada sebuah verteks).


Contoh Graf Planar



Contoh Graf Non Planar


graf planer dan graf bidang

a.      Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak, ia disebut graf tak-planar.  

 b.  Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

            Sisi-sisi pada graf planar membagi bidang menjadi beberapa wilayah (region) atau muka(face). Jumlah wilayah pada graf planar dapat dihitung dengan mudah.

Rumus Euler    :   n – e + f = 2

  dimana : f = jumlah wilayah

                    e = jumlah sisi

                    n = jumlah simpul

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.