Graf Pohon

1. Definisi Pohon (Tree) dan Hutan (Forest)

A. Definisi pohon (tree)

Pohon adalah graf terhubung takberarah yang tidak memiliki sirkuit.

Perhatikan gambar berikut:

Graf G₁ dan G₂ merupakan pohon, sedangkan G₃ bukan pohon karena memiliki sirkuit (contohnya adeba) dan G₄ bukan pohon karena tidak terhubung.

B. Definisi hutan (forest)

Sebarang graf terhubung yang tidak memuat sirkuit adalah pohon. Bagaimana dengan graf yang tidak memuat sirkuit tapi tidak terhubung ? 

Graf yang demikian disebut hutan (forest), boleh juga dikatakan hutan adalah graf tidak terhubung yang komponen terhubungnya adalah pohon-pohon yang saling bebas.

Graf G₄ pada poin A merupakan hutan yang terdiri dari 2 pohon.

2. Pernyataan Ekivalen dengan Definisi Pohon

Misalkan G = (V, E) adalah graf tak-berarah sederhana dan banyak titiknya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

a. G adalah pohon.

b. Setiap pasang titik di dalam G terhubung dengan lintasan tunggal.

c. G terhubung dan memiliki m = n − 1 buah sisi.

d. G tidak mengandung sirkuit dan memiliki m = n − 1 buah sisi.

e. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

f. G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen).

Semua butir pernyataan di atas juga dapat dianggap sebagai definisi lain dari pohon. Kita juga dapat membuktikan bahwa hutan F dengan k komponen mempunyai m = n − k buah sisi.

3. Teorema Seputar Pohon

A. Teorema penambahan dan penghapusan sisi

• Bila suatu sisi dihapus dari pohon (dan titiknya tetap), maka diperoleh graf yang tidak terhubung, dan karenanya graf itu bukan pohon (melainkan hutan).

• Bila sebuah sisi ditambahkan pada pohon (tanpa menambah titik baru), diperoleh graf yang memiliki sikel, dan karena itu graf tersebut bukan pohon.

B. Lintasan terpanjang

Jika P = (v₀, v₁, v₂, ..., vₙ) sebuah lintasan terpanjang di pohon T, maka d(v₀) = d(vₙ) = 1.

4. Pohon Berakar (Rooted Tree)

Istilah pohon berakar (rooted tree) digunakan untuk graf berarah terhubung yang tidak memiliki sirkuit, perbedaannya dengan pohon biasa, yang bisa disebut pohon bebas (free tree), adalah pada keterarahannya.

Pohon yang sebuah titiknya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar dinamakan pohon berakar (rooted tree).

Akar mempunyai derajat-masuk sama dengan nol dan simpul-simpul lainnya berderajat-masuk sama dengan satu. Titik yang mempunyai derajat-keluar sama dengan nol disebut daun atau titik terminal. Titik yang mempunyai derajat-keluar tidak sama dengan nol disebut titik dalam atau titik cabang. Setiap titik di pohon dapat dicapai dari akar dengan sebuah lintasan tunggal (unik).

Arah sisi di dalam pohon tidak perlu digambar, karena setiap titik di pohon harus dicapai dari akar, maka lintasan di dalam pohon berakar selalu dari "atas" ke "bawah".

Sembarang pohon tak-berakar dapat diubah menjadi pohon berakar dengan memilih sebuah titik sebagai akar. Pemilihan titik yang berbeda menjadi akar menghasilkan pohon berakar yang berbeda pula.

5. Terminologi Pohon Berakar

A. Anak (Child) dan Orang Tua (Parent)

Misalkan x adalah sebuah titik di dalam pohon berakar. Titik y dikatakan anak titik x jika ada sisi dari titik x ke y. Dalam hal demikian, x disebut orangtua (parent) y.

Pada graf ini, b,c, dan d adalah anak-anak titik a, dan a adalah orangtua dari anak-anak itu. e dan f adakah anak-anak titik b, dan b adalah orangtua e dan f. g adalah anak titik d, dan d adalah orangtua g. Titik h, i, j, l, dan m tidak mempunyai anak.

B. Lintasan (Path)

Lintasan dari titik v₁ ke titik vₖ adalah runtunan titik-titik v₁, v₂, ..., vₖ sedemikian sehingga vᵢ adalah orangtua dari vᵢ₊₁ untuk 1 ≤ i < k. Dari pohon pada poin (A), lintasan dari a ke j adalah a, b, e, j. Panjang lintasan adalah banyak sisi yang dilalui dalam suatu lintasan, yaitu k – 1. Panjang lintasan dari a ke j adalah 3.

C. Keturunan (Descendant) dan Leluhur (Ancestor)

Jika terdapat lintasan dari titik x ke titik y di dalam pohon, maka x adalah leluhur dari titik y, dan y adalah keturunan titik x. Pada gambar di poin (A), b adalah leluhur titik h, dan dengan demikian h adalah keturunan b.

D. Saudara Kandung (Sibling)

Titik yang berorangtua sama adalah saudara kandung satu sama lain. Pada gambar di poin(A), f adalah saudara kandung e. Tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda.

E. Sepupu (Cousin)

Titik yang berbeda orang tua tetapi orangtuanya bersaudara kandung, disebut sebagai sepupu. Pada gambar di poin (A), f adalah sepupu g, dimana orangtua dari f adalah b, orangtua dari g adalah d, sedangkan b dan d saudara kandung.

F. Subpohon (Subtree)

Misalkan x adalah titik di dalam pohon T. Yang dimaksud dengan subpohon dengan x sebagai akarnya ialah subgraf T' = (V', E') sedemikian sehingga V' mengandung x dan semua keturunannya dan E' mengandung sisi-sisi dalam semua lintasan yang berasal dari x.

Sebagai contoh, T' = (V', E') adalah subpohon dari pohon pada gambar ini dengan V' = {b, e, f, h, i, j} dan E' = {(b, e), (b, f), (e, h), (e, i), (e, j)} dan b adalah titik akarnya. Terdapat banyak subpohon di dalam pohon T. Dengan pengertian di atas, jika x adalah titik, maka akar tiap-tiap subpohon dari x disebut anak, dan x adalah orangtua setiap akar subpohon.

G. Derajat (Degree)

Ada perbedaan definisi derajat pada pohon berakar dengan definisi derajat pada graf (termasuk pohon tidak berakar). Derajat sebuah titik pada pohon berakar adalah banyak subpohon (atau banyak anak) pada titik tersebut. Pada gambar di poin (A), derajat a adalah 3, derajat b adalah 2, derajat d adalah satu dan derajat c adalah 0. Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.

Derajat maksimum dari semua titik merupakan derajat pohon itu sendiri. Pohon pada poin (A) berderajat 3, karena derajat tertinggi dari seluruh titiknya adalah 3.

H. Daun (Leaf)

Titik yang berderajat nol (atau tidak mempunyai anak) disebut daun. Titik h, i, j, f, c, l, dan m adalah daun.

I. Titik Dalam (Internal Nodes)

Titik yang mempunyai anak disebut simpul dalam. Simpul d,e,g, dan k pada poin (A) adalah titik dalam.

J. Aras (Level) atau Tingkat

Akar memiliki aras 0, sedangkan aras titik lainnya adalah 1 ditambah panjang lintasan dari akar ke titik tersebut.

K. Tinggi (Height) atau Kedalaman (Depth)

Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon. Dapat juga dikatakan tinggi pohon adalah panjang maksimum lintasan dari akar ke daun. Tinggi pohon pada poin (J) adalah 4.

6. Pohon Berakar Terurut (Ordered Tree)

Pohon berakar yang urutan anak-anaknya penting disebut pohon terurut (ordered tree).

A. Sistem Increment

Pada pohon terurut, urutan anak-anak dari titik dalam dispesifikasikan dari kiri ke kanan. Sebagai contoh, dua buah pohon pada gambar ini adalah pohon berakar yang sama, tetapi sebagai pohon terurut, keduanya berbeda. Misalnya urutan anak-anak dari titik 1 pada gambar di sisi kiri adalah 2, 3, 4, sedangkan urutan anak-anak dari titik 1 pada gambar di sisi kanan adalah 3, 4, 2.

Perbedaan ini menjadi penting bila kita merepresentasikan pohon di dalam komputer, karena penelusuran dua buah pohon terurut yang berbeda akan menghasilkan urutan titik yang berbeda pula. Jika pohon berakar terurut pada titik x mempunyai p buah subpohon, kita akan mengacunya sebagai subpohon pertama, subpohon kedua, ..., subpohon ke-p.

B. Sistem Chaptering

Sistem yang universal dalam pengalamatan titik-titik pada pohon terurut adalah dengan memberi nomor setiap titiknya seperti penomoran bab (beserta subbabnya) di dalam sebuah buku. Titik akar diberi nomor 0, titik lain yang segera mengikuti akar diberi nomor 1, 2, 3, dan seterusnya. Anak-anak titik 1 diberi nomor 1.1, 1.2, ...; anak-anak titik 2 diberi nomor 2.1, 2.2, ...; demikian seterusnya. Semua penomoran dimulai dengan aturan dari kiri ke kanan.

7. Pohon m-ary (M-ary Tree)

A. Definisi umum

Pohon berakar yang setiap titik cabangnya mempunyai paling banyak n buah anak disebut pohon m-ary.

B. Kasus khusus

Jika m = 2, pohon disebut pohon biner (binary tree). Pohon m-ary dikatakan pohon penuh (full m-ary tree) atau pohon teratur jika setiap titik cabangnya mempunyai tepat m buah anak.

C. Penerapan

Pohon m-ary banyak digunakan di berbagai bidang ilmu maupun dalam kehidupan sehari-hari. Dalam terapannya, pohon m-ary digunakan sebagai model yang merepresentasikan suatu struktur. Dua contoh penggunaan pohon m-ary dikemukakan di bawah ini, yaitu penurunan kalimat (dalam bidang bahasa) dan direktori arsip di dalam komputer. Contoh penggunaan pohon m-ary lainnya adalah struktur organisasi, silsilah keluarga (dalam bidang genetika), struktur bab atau daftar isi di dalam buku, bagan pertandingan antara beberapa tim sepakbola, dan sebagainya.

D. Banyak daun pada pohon m-ary

Pohon m-ary penuh adalah pohon yang setiap titiknya tepat mempunyai m buah anak. Pada pohon m-ary penuh dengan tinggi h, banyak daun adalah mʰ. Perhatikan bahwa jika T bukan pohon m-ary penuh, maka jumlah daun akan kurang dari mʰ. Jadi, secara umum banyak daun pada pohon m-ary ≤ mʰ.

Sebagai contoh, pohon 3-ary dengan tinggi 2 memiliki 3² = 9 daun.

E. Banyak titik pada pohon m-ary

Pada pohon m-ary penuh dengan tinggi h,

aras 0 → banyak titik = m⁰ = 1

aras 1 → banyak titik = m¹

aras 2 → banyak titik = m²

...

aras h → banyak titik = mʰ

maka banyak seluruh titik adalah m⁰ + m¹ + m² + ... + mʰ, dengan deret geometri, dapat dirumuskan

adapun untuk pohon m-ary tidak penuh, banyak titik akan kurang dari pohon m-ary penuh.

F. Hubungan banyak daun dan titik pada pohon m-ary penuh

Misalkan sebuah kompetisi diikuti oleh t peserta dengan sistem eliminasi yang melibatkan m peserta di setiap putaran pertandingan, dan hanya satu peserta yang keluar sebagai pemenang dari setiap putaran tersebut. Berapa banyak pertandingan yang terjadi dalam kompetisi tersebut?

Solusi:

Persoalan ini dapat dimodelkan dengan pohon m-ary penuh. Daun menyatakan peserta, titik dalam (termasuk akar) menyatakan putaran pertandingan.

Misalkan i adalah banyaknya titik dalam (banyak pertandingan) dan t adalah banyaknya titik daun (banyak peserta) di dalam pohon m-ary penuh.

Setiap pertandingan melibatkan m peserta dan menghasilkan 1 pemenang, yang berarti m − 1 peserta tereliminasi per pertandingan. Pada akhir kompetisi, semua peserta telah gugur kecuali satu pemenang.

Jadi, total peserta yang tereliminasi dalam seluruh kompetisi adalah t − 1 (semua peserta kecuali sang juara). Karena setiap pertandingan menggugurkan m−1 orang pemain, maka banyak total pemain yang tereliminasi juga dapat dihitung dari banyak pertandingan i dikalikan dengan (m − 1).

Dari sini, diperoleh hubungan:

(m − 1)i = t − 1

Sebagai contoh, berikut ini permasalahan serupa.

Misalkan suatu perkumpulan dihadiri 25 orang dan masing-masing ingin mengecas handphonenya, padahal di tempat kumpul tersebut hanya ada 1 stop kontak. Salahsatu dari mereka berinisiatif untuk meminjam ekstensi (olor) yang masing-masing memiliki 5 colokan. Berapa banyak ekstensi yang dibutuhkan?

Penyambungan semacam itu merupakan pohon 5-ary dengan stop kontak sebagai akar pohon, diperoleh hubungan

(5 − 1)i = 25 − 1

4i = 24

i = 6

Jadi, dibutuhkan sebanyak 6 ekstensi.