# data[].attributes.body
•Definisi :

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

Bila lintasan tersebut kembali ke simpul asal, membentuk lintasan tertutup (sirkuit), maka lintasan tertutup ini dinamakan sirkuit Euler.

Jadi, sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

Graf yang mempunyai sirkuit Euler dinamakan graf Euler.

Graf yang mempunyai lintasan Euler dinamakan juga graf semi Euler.

# data[].attributes.attachment_link.title
LINTASAN DAN SIRKUIT EULER (EULARIAN GRAPH)

# data[].attributes.body
Graf terhubung tak berarah G adalah:

Graf Euler jika dan hanya jika setiap simpul di dalam graf tersebut berderajat genap.

Graf semi Euler jika dan hanya jika di dalam graf tersebut terdapat tepat dua simpul berderajat ganjil.

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

# data[].attributes.body
Graf terhubung berarah 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 dari derajat masuk, dan yang kedua memiliki derajat masuk satu lebih besar dari derajat keluar.

# data[].attributes.body
Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.

Bila lintasan kembali ke simpul asal membentuk sirkuit maka dinamakan sirkuit Hamilton, atau

Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui 2 kali.

Graf Hamilton : Graf yang memiliki sirkuit Hamilton.

Graf semi Hamilton : Graf yang hanya memiliki lintasan Hamilton.

# data[].attributes.attachment_link.title
LINTASAN DAN SIRKUIT HAMILTON (HAMILTONIAN GRAPH)

# data[].attributes.body
Teorema Dirac
Syarat cukup supaya graf sederhana G dengan n≥3 buah simpul adalah graf Hamilton ialah bila derajat tiap simpul paling sedikit n/2 untuk setiap simpul di G.

Teorema 1
Setiap graf lengkap adalah graf Hamilton.

Teorema 2
Di dalam graf lengkap G dengan n buah simpul n≥3, terdapat (n-1)!/2 buah sirkuit Hamilton.

Teorema 3
Di dalam graf lengkap G dengan n buah simpul n≥3,terdapat (n-1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang bersisian).
Jika n genap n≥4,maka di dalam G terdapat (n-2)/2 buah sirkuit Hamilton yang saling lepas.

# data[].attributes.body
Terdapat beberapa aplikasi yang berkaitan dengan lintasan / sirkuit di dalam graf.

•Lintasan Terpendek (Shortest Path)

•Persoalan Pedagang Keliling.

•Persoalan Tukang Pos China.

•Pewarnaan Graf.