Graf Euler dan Hamilton

Graf Euler
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).
(a) dan (b) grafsemi-Euler, (c) dan (d) graf Euler , (e) dan (f) bukan graf semi-Euler atau graf Euler
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) dan (f) tidak mempunyai lintasanmaupun sirkuit Euler

Teorema-teorema
• TEOREMA 6.2. Graf 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.
• TEOREMA 6.3. Graf tidak berarah G adalah graf Euler
(memiliki sirkuit Euler) jika dan hanya jika setiap simpul
berderajat genap.
• (Catatlah bahwa graf yang memiliki sirkuit Euler pasti
mempunyai lintasan Euler, tetapi tidak sebaliknya)
• TEOREMA 6.4. 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 pertamamemiliki derajat-keluar satu lebih besar derajat-
masuk, dan yang kedua memiliki derajat-masuk satu lebih
besar dari derajat-keluar.

Graf Hamilton
Lintasan dan Sirkuit Hamilton
• Lintasan Hamilton ialah lintasan yang melalui
tiap simpul di dalam graf tepat satu kali.
• Sirkuit Hamilton ialah sirkuit yang melalui tiap
simpul di dalam graf tepat satu kali, kecuali
simpul asal (sekaligus simpul akhir) yang dilalui
dua kali.
• Graf yang memiliki sirkuit Hamilton dinamakan
graf Hamilton, sedangkan graf yang hanya
memiliki lintasan Hamilton disebut graf semi-
Hamilton.

Teorema
• TEOREMA 6.5. Syarat cukup (jadi bukan syarat perlu)
supaya graf sederhana G dengan n (³ 3) buah simpul
adalah graf Hamilton ialah bila derajat tiap simpul paling
sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di G).
• TEOREMA 6.6. Setiap graf lengkap adalah graf
Hamilton.
• TEOREMA 6.7. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
• TEOREMA 6.8. Di dalam graf lengkap G dengan n buah
simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit
Hamilton yang saling lepas (tidak ada sisi yang
beririsan). Jika n genap dan n ³ 4, maka di dalam G
terdapat (n - 2)/2 buah sirkuit Hamilton yang saling
lepas.