Graf Euler dan Hamilton
Definisi Graf Euler
Lintasan Euler : Lintasan yang melalui masing-masing sisi didalam graf G tepat satu kali. Graf yang mempunyai Lintasan Euler disebut Graf Semi-Euler.
Sirkuit Euler : Sirkuit dimana setiap vertex dalam graf G muncul paling sedikit satu kali dan setiap sisi muncul tepat satu kali. Graf yang mempunyai Sirkuit Euler disebut Graf Euler.
Teorema 1 : Sebuah graf terhubung tak berarah paling sedikit dengan dua titik(vertex) mempunyai sirkuit euler jika dan hanya jika titik titik tersebut berderajat genap.
Teorema 2 : Sebuah graf terhubung tak berarah yang mempunyai lintasan euler tetapi tidak memiliki sirkuit euler jika dan hanya jika graf tersebut tepat mempunyai dua titik yang berderajat ganjil.
Teorema 3 : Graf berarah G memiliki lintasan euler jika dan hanya jika G terhubung dan setiap titik memiliki derajat masuk dan derajat keluar sama kecuali dua titik, yang pertama memiliki derajat masuk satu lebih banyak dari pada digit keluarnya dan titik yang kedua memiliki derajat keluar satu lebih banyak dari pada derajat masuknya. Sedangkan graf berarah G memiliki sirkuit euler jika dan hanya jika G terhubung dan setiap titik memiliki derajat masuk dan derajat keluar yang sama.
Definisi Graf Hamilton
Lintasan Hamilton : Sebuah lintasan sederhana di graf G yang melalui setiap titik tepat satu kali. Graf yang mempunyai Lintasan Hamilton disebut Graf Semi-Hamilton.
Sirkuit Hamilton : Sebuah sirkuit sederhana di graf G yang melalui setiap titik tepat satu kali (kecuali titik awal yang boleh dilalui dua kali). Graf yang mempunyai Sirkuit Hamilton disebut Graf Hamilton.
Teorema Diracs : Jika G adalah graf sederhana yang mempunyai n vertex dengan n≥3. Misalkan derajat di setiap vertex nya di G minimal n/2 maka G adalah Sirkuit Hamilton.
Teorema Direcs merupakan syarat cukup bukan syarat perlu.
Teorema Ore : Jika G adalah graf sederhana yang mempunyai n vertex dengan n≥3. Misalkan deg(u)+deg(v)≥n untuk setiap pasangan vertex non adjacent u dan v di G, maka G mempunyai Sirkuit Hamilton.
Teorema Ore merupakan syarat cukup bukan syarat perlu.
Lintasan Euler : Lintasan yang melalui masing-masing sisi didalam graf G tepat satu kali. Graf yang mempunyai Lintasan Euler disebut Graf Semi-Euler.
Sirkuit Euler : Sirkuit dimana setiap vertex dalam graf G muncul paling sedikit satu kali dan setiap sisi muncul tepat satu kali. Graf yang mempunyai Sirkuit Euler disebut Graf Euler.
 |
| Graf Semi-Euler |
 |
| Graf Euler |
Teorema 1 : Sebuah graf terhubung tak berarah paling sedikit dengan dua titik(vertex) mempunyai sirkuit euler jika dan hanya jika titik titik tersebut berderajat genap.
Teorema 2 : Sebuah graf terhubung tak berarah yang mempunyai lintasan euler tetapi tidak memiliki sirkuit euler jika dan hanya jika graf tersebut tepat mempunyai dua titik yang berderajat ganjil.
Teorema 3 : Graf berarah G memiliki lintasan euler jika dan hanya jika G terhubung dan setiap titik memiliki derajat masuk dan derajat keluar sama kecuali dua titik, yang pertama memiliki derajat masuk satu lebih banyak dari pada digit keluarnya dan titik yang kedua memiliki derajat keluar satu lebih banyak dari pada derajat masuknya. Sedangkan graf berarah G memiliki sirkuit euler jika dan hanya jika G terhubung dan setiap titik memiliki derajat masuk dan derajat keluar yang sama.
Definisi Graf Hamilton
Lintasan Hamilton : Sebuah lintasan sederhana di graf G yang melalui setiap titik tepat satu kali. Graf yang mempunyai Lintasan Hamilton disebut Graf Semi-Hamilton.
Sirkuit Hamilton : Sebuah sirkuit sederhana di graf G yang melalui setiap titik tepat satu kali (kecuali titik awal yang boleh dilalui dua kali). Graf yang mempunyai Sirkuit Hamilton disebut Graf Hamilton.
 |
| Graf Semi-Hamilton |
 |
| Graf Hamilton |
Teorema Diracs : Jika G adalah graf sederhana yang mempunyai n vertex dengan n≥3. Misalkan derajat di setiap vertex nya di G minimal n/2 maka G adalah Sirkuit Hamilton.
Teorema Direcs merupakan syarat cukup bukan syarat perlu.
Teorema Ore : Jika G adalah graf sederhana yang mempunyai n vertex dengan n≥3. Misalkan deg(u)+deg(v)≥n untuk setiap pasangan vertex non adjacent u dan v di G, maka G mempunyai Sirkuit Hamilton.
Teorema Ore merupakan syarat cukup bukan syarat perlu.
3 komentar untuk "Graf Euler dan Hamilton"