GRAF PLANAR

DEFINITION..

A planar drawing of a graph is a drawing of the graph in the plane without edge-crossings.

A graph is said planar if there exists a planar drawing of it.

Ex:

A non planar drawing of K4

A planar drawing of K4

CONTOH LAIN... Apakah graf dibawah ini merupakan graf

planar?

TEOREMA

Graf komplit merupakan graf tidak planar. Bukti:

i) Misalkan 5 verteks pada adalah , .

ii) Karena merupakan graf komplit, maka setiap pasang verteks di dihubungkan oleh satu edge, sedemikian hingga terdapat sebuah sirkuit dari . (seperti pentagon).

iii) Sirkuit ini membatasi dua daerah (inside dan outside) ( Jordan Curve Theorem).

iv) Karena verteks harus dihubungkan dengan oleh sebuah edge, maka edge tersebut dapat digambarkan inside atau outside dari pentagon ( tanpa bersilangan dengan 5 edge yang telah digambarkan sebelumnya). Misalkan kita pilih inside, berarti edge dari ke didalam pentagon.v) Selanjutnya untuk edge dari ke dan edge dari ke , karena tak satupun dari kedua edge ini yang dapat digambarkan didalam (inside) pentagon tanpa terjadi edge yang bersilangan maka kedua edge tersebut diletakkan diluar (outside) pentagon.vi) Edge yang menghubungkan ke tidak dapat digambarkan diluar pentagon, karena akan bersilangan dengan edge dari ke atau edge dari ke maka edge dari ke digambarkan didalam pentagon.vii) Untuk edge yang terakhir, yakni ke edge tidak dapat digambarkan didalam maupun diluar pentagon tanpa ada edge yang bersilangan, karena itu graf komplit nonplanar.

REGION (DAERAH/MUKA)... Edge pada graf planar membagi bidang menjadi beberapa

daerah (muka). r1 adalah daerah yang dibatasi oleh lintasan tertutup a, e, b, a

dengan panjang lintasannya adalah 3, maka derajat dari r1 adalah 3 (ditulis: der(r1)=3

r2 ....

a

e

fg

c

b

g

r1

r2r3

r4

Selidikilah apakah pada graf tersebut berlaku dengan e adalah banyaknya edge dan R adalah himpunan daerah pada graf planar G.

Jawab: ...................................................................

TEOREMA (EULER) Misalkan G adalah graf planar terhubung dengan V, E, dan R

menunjukkan banyaknya verteks, edge dan daerah dari G. Maka V – E + R = 2.

Bukti:Dibuktikan dengan induksi berdasarkan banyaknya jalur pada G.(i) Jika E=0, maka V=1 (karena G terhubung) dan R=1

(daerah tak terbatas).(ii) Andaikan teorema diatas benar untuk semua graf yang

mempunyai paling banyak (V – 1) edge.(iii) Misalkan G adalah graf yang mempunyai E edge.Kalo G tree maka E= V – 1 dan R=1, sehingga V – E + R = 2 seperti yang diperlukan.Kalo G bukan tree, misalkan e adalah edge yang terdapat dalam beberapa cycle pada G, maka G – e adalah graf bidang terhubung dengan V verteks, (E-1) edge, dan (R-1) daerah, dengan hipotesis induksi diperoleh bahwa V – (E – 1) + (R – 1) = 2 seperti yang diperlukan. Jadi, rumus V – E + R = 2 terbukti.

Dengan menggunakan Teorema Euler, tunjukkan bahwa graf tidak planar.

Bukti:

i) karena merupakan graf bipartit komplit maka banyaknya verteks, V=6 dan banyaknya edge, E = 9.

ii) Andaikan graf planar berarti teorema Euler berlaku. Ini mengakibatkan mempunyai 5 daerah.

iii) Karena merupakan graf bipartit komplit dengan banyak verteks 6 dan banyak edge 9, maka lintasan tertutup minimum yang ada pada adalah 4, sehingga jumlah minimum derajat daerah/muka pada graf ini adalah 4 x 5 = 20. Menurut teorema yang menyatakan bahwa berarti graf ini mempunyai edge 10 atau lebih. Hal ini bertentangan dengan langkah i) yang menyatakan bahwa E = 9. jadi pengandaian salah, graf tidak planar.

BEBERAPA DEFINISI...

Graf Isomorfik ; two graphs G and H are said to be isomorphic ( to each other) if there is a one-to-one correspondence between their vertices and between their edges such that the incidences relationship is preserved.

Dua graf yang saling isomorfik mempunyai sifat:a. jumlah verteks samab. jumlah jalur samac. Jumlah verteks dengan derajat tertentu sama. Graf Homomorfik; dua graf dikatakan homomorfik

jika salah satu dari kedua graf tersebut diperoleh dengan memodifikasi (menambah atau menghapus) sederetan verteks-verteks berderajat dua.

BEBERAPA TEOREMA

Graf yang isomorfik dengan atau merupakan graf tidak planar.

Teorema Kuratowski; suatu graf tidak planar jika dan hanya jika graf itu memuat subgraf yang homomorfik dengan atau

Selidikilah ke-planar-an dari graf berikut !