Graf Eulerian dan Graf Hamiltonian
Karakterisasi Graf Eulerian (melalui setiap sisi tepat sekali) dan Graf Hamiltonian (melalui setiap titik tepat sekali).
1. Graf Eulerian
Sebuah graf dikatakan memiliki lintasan Euler jika terdapat lintasan yang melalui setiap sisi tepat satu kali. Jika lintasan tersebut tertutup, disebut Sirkuit Euler.
Sebuah graf terhubung memiliki sirkuit Euler jika dan hanya jika setiap titik di memiliki derajat genap.
Graf terhubung memiliki lintasan Euler (tetapi bukan sirkuit) jika dan hanya jika memiliki tepat dua titik berderajat ganjil.
2. Graf Hamiltonian
Sebuah graf dikatakan memiliki lintasan Hamilton jika terdapat lintasan yang melalui setiap titik tepat satu kali. Jika tertutup, disebut Siklus Hamilton.
Jika adalah graf sederhana dengan titik () dan setiap titik memenuhi , maka memiliki siklus Hamilton.
Contoh Soal & Pembahasan
Diberikan papan catur berukuran . Mungkinkah seekor kuda catur (knight) bergerak mengunjungi setiap kotak tepat satu kali dan kembali ke kotak asal?
Latihan Soal
Tunjukkan mengapa penduduk kota Königsberg tidak bisa berjalan melewati 7 jembatan masing-masing tepat satu kali dan kembali ke tempat semula.
💡 Tampilkan Pembahasan / Solusi Sembunyikan Pembahasan ▾
Pembahasan: Representasi graf jembatan Königsberg memiliki 4 titik dengan derajat (semua berderajat ganjil). Berdasarkan Teorema Euler, graf dapat memiliki sirkuit Euler jika dan hanya jika seluruh titik berderajat genap. Karena ada titik berderajat ganjil, perjalanan tersebut tidak mungkin.
Navigasi Sub-Topik
- ← Sub-Topik Sebelumnya: Definisi dan Struktur Dasar Graf
- Sub-Topik Selanjutnya: Matching dan Teorema Hall →
Materi Terkait (Linked References) (2)
Definisi dan Struktur Dasar Graf (Handshaking Lemma)
Pengantar struktur graf G=(V,E), derajat titik, Handshaking Lemma, lintasan (path), siklus (cycle), dan konektivitas.
Matching dan Marriage Theorem (Teorema Hall)
Graf bipartit, penentuan matching lengkap (complete matching), dan Teorema Hall (Marriage Theorem) |N(S)| >= |S|.
Diskusi & Tanya Jawab
Punya pertanyaan atau diskusi terkait materi ini? Tuliskan komentar Anda di bawah.
Komentar ini mendukung penulisan notasi matematika LaTeX dan format Markdown. Seluruh pesan dimuat secara terisolasi di dalam iframe aman sehingga tidak akan merusak layout halaman website:
- Inline Math: Gunakan
$...$(contoh:$a \in G$). - Display Math: Berikan baris baru (enter) di sebelum & sesudah
$$atau gunakan blok kode```math(contoh:$$\n\frac{a+b}{2} \ge \sqrt{ab}\n$$).