Matematika Diskrit : Keplanaran Suatu Graf

📋 Daftar Isi

Rumus Euler

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face).

Graf bidang pada gambar di bawah ini terdiri atas 6 wilayah (termasuk wilayah terluar):

Hubungan antara jumlah simpul (n), jumlah sisi (e), dan jumlah wilayah (f) pada graf bidang:

n – e + f = 2 (Rumus Euler)

Pada Gambar di atas, e = 11 dan n = 7, f = 6, maka 7 – 11 + 6 = 2.

Pada graf planar sederhana terhubung dengan f buah wilayah, n buah simpul, dan e buah sisi (e > 2) selalu berlaku:

\[ e ≤ 3n – 6 \]

Dinamakan ketidaksamaan Euler, yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana.

Bila suatu graf planar, maka ia memenuhi ketidaksamaan Euler.

Bila suatu graf tidak planar, maka ia tidak memenuhi ketidaksamaan tersebut.

Contoh :

Pada K₄, n = 4, e = 6, memenuhi ketidaksamaan Euler, sebab 6 ≤ 3(4) – 6. Jadi, K₄ adalah graf planar.

Pada graf K₅, n = 5 dan e = 10, tidak memenuhi ketidaksamaan Euler sebab 10 ≥ 3(5) – 6. Jadi, K₅ tidak planar.

Ketidaksamaan e ≤ 3n – 6 tidak berlaku untuk K_3,3 karena

e = 9, n = 6

9 ≤ (3)(6) – 6 = 12 (jadi, e ≤ 3n – 6)

Padahal, graf K_3,3 bukan graf planar.

Meskipun suatu graf planar sederhana memenuhi ketidaksamaan Euler, itu tidak menjamin keplanaran suatu graf.

Buat asumsi baru: setiap daerah pada graf planar dibatasi oleh paling sedikit empat buah sisi, dari penurunan rumus diperoleh e ≤ 2n – 4.

Contoh:

Graf K_3,3 pada Gambar di bawah memenuhi ketidaksamaan e ≤ 2n – 4, karena

e = 9, n = 6

9 ≤ (2)(6) – 4 = 8 (salah)

yang berarti K_3,3bukan graf planar.

Teorema Kuratoswki

Berguna untuk menentukan dengan tegas keplanaran suat graf.

Keterangan:

(a) Graf Kuratowski pertama (K₅)
(b) Graf Kuratowski kedua (K_3,3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua

Sifat graf Kuratowski:

Kedua graf Kuratowski adalah graf teratur.
Kedua graf Kuratowski adalah graf tidak-planar.
Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi graf planar.
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.

Keterangan: 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 (G₁) yang sama dengan K_3,3

Keterangan: Graf G tidak planar karena ia mengandung upagraf yang sama dengan K_3,3

Graf G tidak planar karena ia mengandung upagraf (G₁) yang homeomorfik dengan K₅ (dengan membuang simpul-simpul yang berderajat 2 dari G₁, diperoleh K₅).