Definisi Jembatan dan Pohon dalam Graf

Jembatan

• Busur e dalam graf terhubung G disebut jembatan jika penghapusan e mengakibatkan graf menjadi tidak terhubung.
• Busur e harus menghubungkan tepat dua komponen yang terpisah, dengan satu komponen berisi simpul u dan komponen lainnya berisi simpul v.
• Jika G adalah graf tidak terhubung, busur e adalah jembatan jika dan hanya jika e adalah jembatan dalam komponen yang sesuai dari G.
• Sebuah busur e pada graf G adalah jembatan jika dan hanya jika e tidak berada pada lingkaran di G.

Pohon

• Graf G disebut asiklik jika tidak mengandung lingkaran.
• Pohon adalah graf terhubung yang asiklik.
• Setiap busur dalam pohon adalah jembatan.
• Pohon dengan tepat dua simpul yang bukan simpul akhir disebut bintang ganda.
• Ulat (caterpillar) adalah pohon dengan tiga simpul atau lebih yang, setelah semua simpul akhirnya dihapus, menghasilkan lintasan.
• Lintasan yang dihasilkan setelah menghapus simpul akhir dari ulat disebut tulang belakang (spine/backbone).
• Pohon berakar terbentuk ketika satu simpul dari pohon T dipilih sebagai akar.
• Pohon dengan akar yang berbeda dianggap sebagai pohon berakar yang berbeda.
• Hasil eksperimen dapat direpresentasikan sebagai pohon berakar atau pohon bercabang.
• Kumpulan graf asiklik disebut hutan.
• Setiap komponen dari hutan adalah pohon.
• Sebuah graf adalah pohon jika dan hanya jika terdapat lintasan unik antara setiap pasangan simpul.
• Pohon nontrivial memiliki setidaknya dua simpul ujung.
• Pohon dengan n simpul memiliki n - 1 busur.
• Dalam hutan dengan n simpul dan k komponen, terdapat n - k busur.
• Jika G adalah graf dengan orde n dan ukuran m, dan G memenuhi dua kondisi berikut, maka G adalah pohon:
  • G terhubung
  • G asiklik
  • m = n - 1
• Jika T adalah pohon dengan orde k, dan G adalah graf dengan δ(G) ≥ k − 1, maka T isomorfik dengan subgraf dari G.
• Misalkan T graf dengan n simpul, maka semua pernyataan berikut adalah ekivalen:
  • T terhubung dan tidak mengandung lingkaran.
  • T mempunyai n-1 busur dan tidak mempunyai lingkaran.
  • T terhubung dan mempunyai n-1 busur.
  • T terhubung dan menghapus salah satu busur membuat T tak terhubung.
  • Sembarang dua simpul pada T dihubungkan oleh tepat satu lintasan
  • T tidak mengandung lingkaran, tapi penambahan sembarang busur baru akan membentuk satu lingkaran

Spanning Tree

• Subgraf H dari G disebut spanning subgraf jika H mencakup semua simpul G.
• Spanning subgraf H dari graf terhubung G disebut spanning tree jika H adalah pohon.
• Setiap graf terhubung memiliki spanning tree.
• Jumlah spanning tree dalam sebuah graf bisa sangat besar, contohnya graf Petersen memiliki 2000 spanning tree berlabel.

Cara Mengkonstruksi Spanning Tree

• Building-up method: pilih busur graf satu per satu tanpa membentuk lingkaran hingga semua simpul disertakan.
• Cutting down method: pilih lingkaran dan hapus salah satu busurnya; ulangi sampai tidak ada lingkaran yang tersisa.

Masalah Spanning Tree Minimal (MST)

• Graf berbobot adalah graf yang busur-busurnya diberi bobot atau biaya.
• Bobot subgraf H dari G adalah jumlah bobot semua busur dalam H.
• Spanning tree minimal adalah spanning tree dengan total bobot busur terkecil.
• Masalah Spanning Tree Minimal adalah mencari spanning tree minimal dari graf terhubung berbobot.

Algoritma Kruskal

1. Mulai dengan T kosong.
2. Pilih busur uv dengan bobot minimum, tambahkan uv ke T.
3. Pilih busur uv dengan bobot minimum berikutnya yang tidak membentuk lingkaran di T, tambahkan uv ke T.
4. Ulangi langkah 3 sebanyak (n - 2) kali.

• Algoritma Kruskal menghasilkan spanning tree minimal dari graf terhubung berbobot.

Algoritma Prim

1. Ambil busur dari graf dengan bobot minimum dan masukkan ke dalam T.
2. Pilih busur berbobot minimum yang bertetangga dengan simpul di T, tapi penambahan busur tersebut tidak membentuk lingkaran di T; tambahkan busur tersebut ke T.
3. Ulangi langkah 2 sampai semua simpul ada di T.

• Algoritma Prim menghasilkan spanning tree minimal dari graf terhubung berbobot.