Tjoetjoe Soelaiman: TI Politala Matdis 1 C

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

Ø Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar,

Ø jika tidak, maka ia disebut graf tak-planar.

Ø K₄ adalah graf planar:

Ø K₅ adalah graf tidak planar:

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

Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang.

Ø Aplikasi Graf Planar

Persoalan utilitas (utility problem) :

(a) Graf persoalan utilitas (K3,3), (b) graf persoalan utilitas bukan graf planar.

ØPerancangan IC (Integrated Circuit)

ØTidak boleh ada kawat-kawat di dalam IC–board yang saling bersilangan → dapat menimbulkan interferensi arus listrik → malfunction

ØPerancangan kawat memenuhi prinsip graf planar

Lintasan dan Sirkuit Euler

Ø Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

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

Ø Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

Contoh.

Ø Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1

Ø Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3

Ø Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

Ø Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a

Ø Graf (e) tidak mempunyai lintasan maupun sirkuit Euler. Graf (f) mempunyai lintasan Euler

(a), (b), dan (f) graf semi-Euler

(e) bukan graf semi-Euler atau graf Euler

Ø TEOREMA. Graf tidak berarah memiliki lintasan Euler jika (graf semi-Euler) dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

Ø TEOREMA. Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.

Ø TEOREMA :

· Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama.

· G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.