GRAPH PLANAR & SIRKUIT HAMILTON

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.

Lintasan dan Sirkuit Euler

• Lintasan Eulerialah lintasan yang melalui masing-masing sisi di dalam graph tepat satu kali. 

• Sirkuit Eulerialah sirkuit yang melewati masing-masing sisi tepat satu kali. 

• Graph yang mempunyai sirkuit Euler disebut graph Euler(Eulerian graph). Graph yang mempunyai lintasan Euler dinamakan juga graph semi-Euler(semi-Eulerian graph).

TEOREMA

• Graph tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

•  Graph tidak berarah Gadalah graph Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.
• (Catatlah bahwa graph yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya).
•  Graph berarah G memiliki sirkuit Euler jika dan hanya jika Gterhubung 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.

 

  Lintasan dan Sirkuit Hamilton

• Lintasan Hamiltonialah lintasan yang melalui tiap simpul di dalam graph tepat satu kali. 

• Sirkuit Hamiltonialah sirkuit yang melalui tiap simpul di dalam graph tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

• Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.

TEOREMA

• Syarat cukup (jadi bukan syarat perlu) supaya graph sederhana G dengan n(>=3) buah simpul adalah graph Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) n/2 untuk setiap simpul v di G).
• Setiap graph lengkap adalah graph Hamilton
• Di dalam graph lengkap Gdengan nbuah simpul (n>=3), terdapat (n-1)!/2 buah sirkuit Hamilton.
• Di dalam graph lengkap Gdengan nbuah simpul (n>=3 dan n ganjil), terdapat (n -1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika ngenap dan n4, maka di dalam G terdapat (n -2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh :

(Persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?Jumlah pengaturan tempat duduk yang berbeda adalah (9 -1)/2 = 4.

Lintasan dan Sirkuit Hamilton/ Euler

• Beberapa graph dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler maupun lintasan Hamilton, tidak mengandung lintasan Euler namun mengandung sirkuit Hamilton, dan sebagainya!).