Graf planar

GRAF PLANAR

Suatu graph disebut planar jika dapat digambarkan dalam bidang tanpa adanya ruas berpotongan.

Sebuah graf dikatakan graf planar bila graf tersebut dapat disajikan (secara geometri) tanpa adanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa adanya ruas yang berpotongan disebut dengan penyajian planar/map/peta.

Graf yang termasuk planar :

        1.Tree/Pohon
       2.Kubus
       3.Bidang Empat
       4.Bidang Delapan Beraturan.

·         Pada penyajian planar/map, dikenal istilah region. Derajat dari suatu region adalah panjang walk batas region tersebut.

·         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.  

·         FORMULA EULER

·         JikaG adalahgraph planardengan

v = banyaknyasimpul
          e = banyaknyaruas
          f = banyaknyabidang/region (termasuk bidang yang terluar)

·         Maka berlaku:

v –e + f = 2

       Lintasan dan Sirkuit Euler

·         Lintasan Euler ialah lintasan yang melalui masing-masing sisi didalam graf tepat satu kali.

·         Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

·         Graf yang mempunyai sirkuit Euler disebut graf Euler (Euleriangraph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Euleriangraph).

 TEOREMA KURATOSWKI

Berguna untuk menentukan dengan tegas keplanaran suatu graf.

Gambar :

(a) Graf Kuratowski pertama (K5)
(b) Graf Kuratowski kedua (K3, 3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua

Sifat graf Kuratowski adalah:
1. Kedua graf Kuratowski adalah graf teratur.
2. Kedua graf Kuratowski adalah graf tidak-planar
3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi graf planar.
4. Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.

TEOREMA Kuratowski. Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

Gambar Tiga buah graf yang homemorfik satu sama lain.

Contoh: Kita gunakan Teorema Kuratowski untuk memeriksa keplanaran graf. Graf G di bawah ini bukan graf planar karena ia mengandung upagraf (G1) yang sama dengan K3,3.

Graf G tidak planar karena ia mengandung upagraf yang sama dengan K3,3.
Graf G tidak planar karena ia mengandung upagraf (G1) yang homeomorfik dengan K5 (dengan membuang simpul-simpul yang berderajat 2 dari G1, diperoleh K5).

Gambar Graf G, upagraf G1 dari G yang homeomorfik dengan K5.