graph planar

Graph Planar (Planar Graph) dan Graph Bidang (Plane Graph)

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

Graph Planar (Planar Graph)

Graph Planar

Graph K4

Graph tidak planar

Graph K5


K3,3 bukan graph planar

H2 H3

W G E

H2 H3

W G E

H1 H1


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

Graph planar yang terdiri atas 6 wilayah

R1

R2 R3

R5

R4R6

Subdivision grap G’ adalah

subdivision dari graph G jika G’ diperoleh dari graph G dengan menambahkan satu atau lebih titik berderajat dua pada sisi-sisi di G.

Subdivisions

Setiap subdivision dari graph planar adalah planar

Setiap subdivision graph non-planar adalah non-planar

Teorema Kuratoswki

Berguna untuk menentukan dengan tegas keplanaran suatu graph.

(a) (b) (c)

(a) Graph Kuratowski pertama (b) dan (c) Graph Kuratowski kedua (keduanya isomorfik)

TEOREMA Kuratowski

Graph G bersifat planar jika dan hanya jika ia tidak memuat graph bagian yang sama dengan salah satu graph Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

v

x

y

G1 G2 G3

Tiga buah graph yang homeomorfik satu sama lain

TEOREMA Kuratowski

Graph di bawah ini bukan graph planar karena mengandung graph bagian(G1) yang sama dengan K3,3.

a bc

def

a bc

def

GG1

TEOREMA Kuratowski

G tidak planar karena mengandung graph bagian (G1) yang homeomorfik dengan K5 (dengan membuang

simpul-simpul yang berderajat 2 dari G1, diperoleh K5). a

b

c

d

efg

h

a

b

c

d

efg

h

ii

a

c

eg

h

G G1 K5


Formula Euler

Jika G grap bidang terhubung

maka n – e + f = 2

Dengan :

f = banyaknya muka n = 7

e = banyaknya sisi e = 11

n = banyaknya titik f = 11-7+2 = 6

R1

R2 R3

R5

R4R6

Theorem

Jika G graph bidang dengan k komponen, maka n – e + f = k +1

Bukti: dibuktikan dengan induksi matematika

Untuk k =1

G adalah graph planar dan terhubung

Sehingga berdasarkan teorema euler diperoleh n – e + f = 2 = 1 + 1

Diasumsikan benar untuk k = n.

Yaitu jika G graph bidang dgn n komponen maka n – e + f = n +1

Akan ditunjukkan benar untuk k = n +1

Pandang graph G dengan n + 1 komponen

Misalkan u dan v adalah titik-titik di graph G

yang terletak pada komponen berbeda

Jika titik u dan v di hubungkan oleh sebuah sisi maka terbentuklah graph bidang baru yaitu H dengan n komponen.

Jika H graph planar dengan n komponen maka berdasarkan asumsi diperoleh:

│V(H)│-│E(H)│+│F(H)│= n + 1

Karena │V(G)│=│V(H)│ dan E(G)│=│E(H)│-1 dan │F(G)│=│F(H)│, maka

│V(G)│-│E(G)│+│F(G)│=│V(H)│-(│E(H)│-1)+│F(H)│

= │V(H)│-│E(H)│+│F(H)│+1

= n + 1 + 1

= (n + 1)+1

= k+1

graph planar

Documents