Teori Graf: Jembatan dan Definisi Pohon

Jembatan

• Busur e dalam graf terhubung G disebut jembatan jika G - e tidak terhubung.
• G - e harus memiliki tepat dua komponen, masing-masing mengandung u dan v.
• Busur e adalah jembatan dalam graf tidak terhubung G jika e adalah jembatan pada komponen dari G.
• Teorema menyatakan bahwa busur e pada graf G adalah jembatan jika dan hanya jika e tidak ada di lingkaran G.

Definisi Pohon

• Graf G disebut asiklik jika tidak mengandung lingkaran.
• Pohon didefinisikan sebagai graf terhubung yang asiklik.
• Setiap busur dalam pohon adalah jembatan.
• Pohon dengan tepat 2 simpul non-terminal disebut bintang ganda.
• Ulat (caterpillar) adalah pohon dengan setidaknya 3 simpul yang menjadi lintasan setelah semua simpul terminal dihapus.
• Lintasan yang dihasilkan setelah penghapusan simpul terminal pada ulat disebut tulang belakang/spine.
• Pohon berakar adalah pohon di mana satu simpul telah ditetapkan sebagai akar.
• Setiap pohon dengan akar yang berbeda akan dianggap sebagai pohon berakar yang berbeda.
• Hasil eksperimen dapat direpresentasikan sebagai pohon berakar atau pohon bercabang.
• Graf asiklik disebut hutan.
• Komponen hutan adalah pohon.
• Suatu graf adalah pohon jika dan hanya jika terdapat jalur unik antara sembarang dua simpul.
• Pohon nontrivial memiliki setidaknya dua simpul ujung.
• Pohon berorde n memiliki ukuran n-1.
• Setiap hutan berorde n dengan k komponen memiliki ukuran n-k.
• Jika G adalah graf dengan orde n dan ukuran m, dan jika G memenuhi dua kondisi berikut:
  • G terhubung
  • G asiklik
  • m = n-1
• Maka G adalah pohon.
• Misalkan T adalah pohon dengan orde k. Jika G adalah graf dengan δ(G) ≥ k-1, maka T isomorfik dengan beberapa subgraf dari G.
• Teorema: Definisi lain dari pohon, Misalkan T adalah graf dengan n simpul, maka semua pernyataan berikut adalah ekuivalen.
  • T terhubung dan tidak mengandung lingkaran.
  • T memiliki n-1 busur (edge) dan tidak mempunyai lingkaran.
  • T terhubung dan memiliki n-1 busur.
  • T terhubung dan menghapus 1 busur saja akan membuat T tidak terhubung
  • T memiliki tepat 1 lintasan diantara sembarang dua simpul pada T
  • T tidak memiliki lingkaran, dan jika setiap busur baru ditambahkan akan membentuk lingkaran.

Spanning Tree

• Subgraf H dari G adalah subgraf rentang jika H berisi semua simpul dari G.
• Subgraf rentang H dari graf terhubung G yang berupa pohon disebut pohon rentang dari G.
• Setiap graf terhubung memiliki spanning tree.
• Sebuah graf dapat memiliki banyak spanning tree.
• Graf Petersen memiliki 2000 spanning tree berlabel.

Metode Konstruksi Spanning Tree

• Metode building-up: Pilih busur graf satu per satu tanpa membentuk lingkaran sampai semua simpul disertakan.
• Metode cutting-down: Pilih lingkaran dan hapus satu busurnya; ulangi sampai tidak ada lingkaran yang tersisa.

Masalah Spanning Tree Minimal

• Graf berbobot adalah graf yang busurnya diberi bobot atau biaya.
• Berat subgraf H dari G adalah jumlah semua bobot busur H, dinyatakan sebagai w(H) = Σ w(e) untuk semua e ∈ E(H).
• Spanning tree minimal adalah spanning tree dengan bobot terkecil.
• Masalah Spanning Tree Minimal (MST) adalah masalah mencari spanning tree minimal dari graf terhubung berbobot.

Algoritma Kruskal

• Algoritma ini digunakan untuk menemukan MST.
  1. Mulai dengan himpunan busur kosong T.
  2. Pilih busur uv dengan bobot minimum dan tambahkan ke T.
  3. Pilih busur uv dengan bobot minimum berikutnya yang tidak membentuk lingkaran di T, lalu tambahkan uv ke T.
  4. Ulangi langkah 3 sebanyak n-2 kali.
• Algoritma Kruskal menghasilkan spanning tree minimal dari graf terhubung berbobot.

Algoritma Prim

• Algoritma mencari sebuah MST.
  1. Ambil busur dari graf dengan bobot minimum, masukkan ke dalam T
  2. Pilih busur berbobot minimum yang bertetangga dengan simpul di T, tetapi penambahan busur tersebut tidak membentuk lingkaran di T. Tambahkan tersebut ke T
  3. Ulangi langkah 2 sampai semua simpul ada di T
• Algoritma Prim menghasilkan spanning tree minimal dari suatu graf terhubung berbobot.