Teori graf: latihan soal dengan penyelesaian langkah demi langkah

1Simpul, sisi, dan derajat

Sebuah graf terdiri dari simpul (titik) dan sisi (garis di antara dua simpul). Pada graf sederhana tidak ada gelang dan tidak ada sisi ganda.

Derajat sebuah simpul adalah banyaknya sisi yang bertemu di simpul itu. Setiap sisi punya dua ujung, jadi ia menambah 1 pada derajat tiap ujungnya. Dari sini diperoleh lema jabat tangan:

Dua akibatnya: jumlah derajat selalu genap, dan banyaknya simpul berderajat ganjil juga genap.

• Graf lengkap K_n menghubungkan setiap pasangan: n(n − 1)/2 sisi.
• Graf bipartit lengkap K_m,n menghubungkan setiap simpul di satu sisi dengan setiap simpul di sisi lainnya: m·n sisi.
• Graf beraturan-k dengan n simpul memiliki n·k/2 sisi.

Matriks ketetanggaan memiliki angka 1 pada (i, j) jika i dan j terhubung. Untuk graf tak berarah matriks ini simetris, jumlah baris adalah derajat, dan entri (i, j) dari Mᴸ menghitung jalan dengan panjang L dari i ke j.

2Euler dan Hamilton

Sebuah sirkuit Euler memakai setiap sisi tepat satu kali dan kembali ke titik awal. Sebuah lintasan Euler memakai setiap sisi satu kali tetapi boleh berakhir di tempat lain. Untuk graf terhubung:

• semua derajat genap: sirkuit Euler ada;
• tepat dua derajat ganjil: lintasan Euler ada, dari satu simpul ganjil ke simpul ganjil lainnya;
• lebih dari dua derajat ganjil: tidak ada keduanya.

Sebuah sirkuit Hamilton mengunjungi setiap simpul tepat satu kali. Tidak ada uji derajat sederhana untuknya. Di K_n terdapat (n − 1)!/2 sirkuit Hamilton yang berbeda: tetapkan titik awal, urutkan n − 1 simpul lainnya, dan bagi 2 untuk dua arah.

3Pohon

Sebuah pohon adalah graf terhubung tanpa siklus. Setiap pohon dengan n simpul memiliki tepat n − 1 sisi. Menambah sisi apa pun membentuk siklus; menghapus sisi apa pun memutus keterhubungan.

Hutan dari c pohon dengan n simpul memiliki n − c sisi. Graf terhubung dengan m sisi masih memiliki pohon rentang setelah m − n + 1 sisi dihapus.

Lema jabat tangan menghitung daun: Σ deg = 2(n − 1). Bentuk singkatnya L = 2 + Σ (d − 2) atas simpul berderajat d ≥ 3. Pohon dengan dua simpul berderajat 3 dan sisanya daun memiliki 2 + 1 + 1 = 4 daun.

4Dijkstra dan pohon rentang minimum

Algoritma Dijkstra mencari jarak terpendek dari simpul awal pada graf dengan bobot tak negatif.

1. Beri simpul awal jarak 0 dan setiap simpul lain ∞.
2. Tetapkan simpul yang belum tetap dengan jarak terkecil; jaraknya kini final.
3. Untuk setiap tetangga v, perbarui d(v) = min(d(v), d(u) + w(u, v)).
4. Ulangi sampai simpul tujuan ditetapkan.

Pohon rentang minimum menghubungkan semua simpul dengan total bobot terkecil. Kruskal mengurutkan sisi dari yang ringan ke berat dan mengambil setiap sisi kecuali yang membentuk siklus. Prim menumbuhkan satu pohon dari simpul awal, selalu menambahkan sisi teringan yang keluar dari pohon itu. Keduanya berhenti setelah n − 1 sisi.

5Kesalahan umum

• Lupa membagi jumlah derajat dengan 2 untuk mendapatkan banyaknya sisi.
• Menguji sirkuit Euler tanpa memeriksa bahwa graf terhubung.
• Menetapkan simpul dalam Dijkstra sebelum simpul itu memiliki jarak sementara terkecil.
• Mengambil n − 1 sisi teringan tanpa memeriksa siklus.
• Menghitung sirkuit Hamilton K_n sebagai n! dan bukan (n − 1)!/2.

6Seperti apa soal ujiannya

• Mudah: derajat dan sisi. Anda memakai lema jabat tangan, menghitung sisi K_n, K_m,n, graf beraturan dan pohon, membaca matriks ketetanggaan, atau mengeklik simpul dengan derajat tertentu.
• Sedang: lintasan Euler dan pohon. Anda menentukan apakah graf memiliki sirkuit atau lintasan Euler, menghitung daun pohon, menghitung sisi yang dihapus untuk pohon rentang, atau menghitung sirkuit Hamilton di K_n.
• Sulit: lintasan terpendek dan pohon rentang. Anda menjalankan algoritma Dijkstra, mencari simpul yang ditetapkan pada putaran tertentu, mencari bobot pohon rentang minimum, mengeklik sisi yang ditambahkan Kruskal atau Prim berikutnya, atau menghitung jalan dengan matriks ketetanggaan.