pohon tree

A.      Pohon (Tree)

POHON (TREE)

Defenisi Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon.

 Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut.  Untuk itu perlu diingat kembali bahwa :

·      Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.

·      Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.

Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.

Karena defenisi pohon mengacu dari teori graf, maka sebuah pohon dapat mempunyai hanya sebuah simpul tanpa sebuah sisipun. Dengan kata lain, jika G=(V,E) adalah pohon, maka V tidak boleh berupa himpunan kosong, namun E boleh kosong. Pada sebagian literatur, pohon yang dimaksudkan oleh Defenisi pohon di atas sering juga disebut pohon bebas (free tree) untuk membedakannya dengan pohon berakar (rooted tree). Pohon berakar akan dibahas lebih lanjut pada materi berikutnya.

Pohon juga seringkali didefinisikan sebagai graf tak-berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasangan simpul. Tinjau kembali graf G₁ di atas. Setiap simpul di G₁ terhubung dengan lintasan tunggal. Sebagai contoh, dari b ke f hanya ada satu lintasan, yaitu b, a, d, f. demikian juga untuk setiap pasangan simpul manapun di G₁

Teorema 1

Jika T pohon, maka untuk setiap dua titik u dan v yang berbeda di T terdapat tepat satu lintasan (path) yang menghubungkan kedua titik tersebut.

Bukti

Misalkan ada lintasan (path) berbeda yang menghubungkan titik u dan titik v di T, katakanlah e1 dan e2, dengan e1≠e2. Maka e1 dan e2 akan menghubungkan titik u dan titik v, sehingga ada dua lintasan yang terhubung pada kedua titik tersebut dan membentuk sikel. Berdasarkan definisi, T tidak memiliki sikel. Dengan demikian, haruslah e1=e2. Hal ini bertentangan dengan pemisalan bahwa e1≠e2. Jadi, terbukti bahwa setiap dua titik yang berbeda di T memiliki tepat satu lintasan yang menghubungkan kedua titik tersebut.

Teorema 2

Banyaknya titik dari sebuah pohon T sama dengan banyaknya sisi ditambah satu atau ditulis:

Jika T pohon, maka |V (T)| = |E (T)| +1

Bukti

Kita buktikan teorema di atas dengan induksi pada |V(T)|. Jika pohon T mempunyai satu titik, jelas banyak sisi T adalah nol. Jadi teorema benar untuk pohon T dengan satu titik. Asumsikan bahwa pernyataan dalam teorema benar untuk pohon dengan k titik, artinya jika pohon T mempunyai paling banyak k titik, maka |V(T)| = |E(T)| + 1. Akan ditunjukkan bahwa jika pohon T mempunyai k + 1 titik maka |V(T)| = |E(T)| + 1. Misalkan T adalah pohon dengan k + 1 titik dan l adalah sebuah sisi T. Maka T – l memiliki tepat dua komponen T₁ dan T₂ , dan masing-masing komponen adalah pohon dengan titik kurang dari k + 1.  Sehingga menurut asumsi, |V(Ti)| = |E(Ti)| + 1 ; i = 1,2.

Selanjutnya |E(T)| = |E(T1)| + |E(T2)| + 1, sehingga

      |V(T)| = |V(T1)| + |V(T2)|

     = |E(T1)| + 1 + |E(T2)| + 1

     = (|E(T1)| + |E(T2)| + 1) + 1

     = |E (T)| + 1

Dengan demikian teorema terbukti.

Teorema 3

a.         Bila suatu sisi dihapus dari pohon (dan titiknya tetap), maka diperoleh graph yang tidak terhubung, dan karenanya graph itu bukan pohon.

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

Bukti

Jika sebuah sisi ditambahkan atau dihapuskan dari pohon, graph baru yang diperoleh tidak lagi merupakan pohon, berdasarkan teorema 2. Karena penghapusan sebuah sisi menjadikan graph itu tidak terhubung, dan penambahan sisi membentuk sikel, maka teorema terbukti.

Hutan (forest) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Dengan kata lain kita dapat katakana  (forest) adalah

-  kumpulan pohon yang saling lepas, atau

-  graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon.                                            

            Pada gambar berikut adalah hutan yang terdiri dari 3 buah pohon

B.       Sifat-sifat Pohon

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

1.      G adalah pohon.

2.      Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

3.      G terhubung dan memiliki m = n – 1 buah sisi.

4.      G tidak mengandung sirkuit dan memiliki m = n – 1  buah sisi.

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

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

C.       Pewarnaan Pohon

Dalam pewarnaan pohon, dua buah warna sudah cukup mewarnai simpul-simpul dalam pohon sedemikian sehingga tidak ada dua buah simpul bertetangga mempunyai warna sama

Pewarnaan pada pohon T dilakukan dengan cara berikut:

1.      Petakan warna pertama pada sembarang simpul.

2.      Petakan warna kedua pada simpul-simpul yang bertetangga dengan simpul pertama tadi.

3.      Petakan warna pertama ke semua simpul yang bertetangga dengan simpul-simpul yang telah diwarnai.

Sebagai contoh tinjau graf G₁. Simpul-simpul pada graf G₁ akan diberi warna dengan warna kuning dan biru. Simpul a dipilih pertama kali untuk diberi warna kuning. Kemudian simpul-simpul tetangga a, yaitu b dan d diberi warna biru. Selanjutnya simpu-simpul yang bertetangga dengan d yaitu c, e dan f diberi warna kuning. Jadi simpul yang berwarna kuning yaitu a, c, e dan f. Sedangkan simpul yang berwarna biru yaitu b dan d.

D.      Pohon Merentang (spanning tree)

Definisi Misalkan G adalah sebuah graph. Sebuah pohon di G yang memuat semua titik G disebut pohon rentang (spanning tree) dari G.

Contoh

Misalkan kita mempunyai graph G seperti pada gambar 4.6 di bawah ini. Terdapat 3 pohon rentang dari graph G, yaitu graph A, B, dan C. Tampak jelas bahwa graph A, B, dan C masing-masing memuat semua simpul dari graph G serta mengandung sisi-sisi dari G demikian sehingga tidak terbentuk sikel.

Teorema 6

Graph G terhubung jika dan hanya jika G memuat pohon rentang.

Bukti

Jika graph G memuat pohon rentang, jelas G terhubung. Kita buktikan konvers pernyataan ini dengan induksi pada |E(G)|. Jika G terhubung dan |E(G)| = 0, maka G = K1, sehingga jelas G memuat pohon rentang.

Asumsikan: setiap graph terhubung dengan k + 1 sisi, maka G memuat pohon rentang.

Pandang sebuah graph terhubung G dengan k + 1 sisi. Jika G tidak memuat sikel, maka G sebuah pohon rentang. Jika G memuat sikel, dan misalkan e adalah sebuah sisi dari sikel di G, maka graph G1 = G - e terhubung dengan k sisi. Sehingga berdasarkan asumsi, G1 memuat pohon rentang. Sebut T, pohon rentang di G1. Jelas, T adalah juga pohon rentang dari G. Teorema terbukti.

Sebuah graph terhubung mungkin memuat lebih dari satu pohon rentang, seperti terlihat pada Gambar. Graph G memuat pohon rentang T1, T2, dan T3.

Jadi, pohon merentang:

·         Pohon merentang dari graf terhubung adalah subgraf merentang yang berupa pohon.

·         Pohon merentang diperoleh dengan memutus  sirkuit di dalam graf.

                       

                G                             T₁                        T₂                          T₃                   T₄

• Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.
• Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut hutan merentang (spanning forest).

Pohon Rentang Minimum

·         Graf terhubung-berbobot mungkin mempunyai lebih dari 1 pohon merentang

·         Pohon rentang yang berbobot minimum – dinamakan pohon merentang minimum (minimum spanning tree)

Dalam kehidupan nyata, salah satu contoh aplikasi spanning tree adalah menentukan rangkaian jalan dengan jarak total seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain.

Dalam menentukan suatu minimum spanning tree dari suatu graf terhubung, kita dapat menentukannya dengan mengunakan dua cara yaitu algoritma Prim dan algoritma Kruskal.

Algoritma Prim

Langkah 1: ambil sisi dari graf G yang berbobot minimum,  masukkan ke dalam T

Langkah 2:  pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T

Langkah 3:  ulangi langkah 2

CONTOH

Langkah                     Sisi               Bobot                 Pohon rentang

Pohon merentang minimum yang dihasilkan: 

Pohon merentang minimum yang dihasilkan: 

Bobot = 10 + 25 + 15 + 20 + 35 = 105

 

Algoritma Kruskal

 ( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya – dari bobot kecil ke bobot besar)

Langkah 1:  T masih kosong

Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk  sirkuit di T. Tambahkan (u, v) ke dalam T.

Langkah 3:   ulangi langkah 2

Contoh:

Sisi-sisi diurut menaik:

Pohon merentang minimum yang dihasilkan :

 

E.       Pohon Berakar

Pada kebanyakan aplikasi pohon, simpul tertentu diperlakukan sebagai akar (root). Sekali sebuah simpul ditetapkan sebagai akar, maka simpul-simpul lainnya dapat dicapai dari akar dengan memberi arah pada sisi-sisi pohon yang mengikutinya.

Definisi:

Pohon yang sebuah simpulnya 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 derajat-masuk sama dengan satu. Simpul yang mempunyai derajat-keluar sama dengan nol disebut daun atau simpul terminal. Simpul yang mempunyai derajat-keluar tidak sama dengan nol disebut simpul dalam atau simpul cabang. Setiap simpul di pohon dapat dicapai dari akar dengan sebuah lintasan tunggal (unik). Gambar 9.9(a) adalah contoh pohon berakar dengan  adalah simpul akarnya. Sebagai konvensi, arah sisi di dalam pohon tidak perlu digambar, karena setiap simpul di dalam pohon berakar selalu dari  atas ke bawah. Gambar 9.9(b) menunjukkan hal ini

Gambar 9.9 (a) pohon berakar, (b) sebagai konvensi, arah panah pada sisi dapat dibuang.

Sembarang pohon tak-berakar dapat diubah menjadi pohon berakar dengan memilih sebuah simpul sebagai akar. Pemilihan simpul yang berbeda menjadi akar menghasilkan pohon berakar yang berbeda pula. Gambar 9.10 memperlihatkan dua pohon akar yang berbeda dari pengubahan sebuah pohon tak-berakar. Pohon berakar pertama memilih  sebagai akar sedangkan pohon akar kedua memilih  sebagai akar.

Gambar 9.10 (kiri) Pohon dan (kanan) dua buah pohon berakar yang dihasilkan dari pemilihan dua simpul berbeda sebagai akar.

F.       Terminologi Pada Pohon Berakar

Keseluruhan sisa bab ini akan menggunakan istilah “pohon berakar” untuk membedakannya dengan “pohon” tidak berakar (free tree).

Sebagaimana pada graf, kita akan sering menggunakan terminologi yang berhubungan dengan pohon. Di bawah ini didaftarkan beberapa terminologi yang penting pada pohon berakar. Untuk ilustrasi, pohon pada Gambar 9.12 dipakai sebagai untuk menjelaskan terminologi yang dimaksudkan. Simpul-simpul pada pohon diberi label untuk mengacu simpul mana yang dimaksudkan. Kebanyakan terminologi pohon yang ditulis di bawah ini diadopsi dari terminologi botani dan silsilah keluarga.

Anak (child atau children) dan Orangtua (parent)

Misalkan  adalah sebuah simpul di dalam pohon berakar. Simpul  dikatakan anak simpul  jika ada sisi dari simpul  ke . Dalam hal demikian,  disebut orangtua (parent) . Pada Gambar 9.11, , , dan  adalah anak-anak simpul , dan  adalah orang tua dari anak-anak itu.  dan  adalah anak-anak simpul , dan  adalah orangtua dari  dan .  adalah anak simpul , dan  adalah orangtua dari . Simpul , , , , dan  tidak mempunyai anak

Gambar 9.11 Pohon berakar yang digunakan untuk menjelaskan terminologi pohon.

Lintasan (path)

Lintasan dari simpul  ke simpul  adalah runtutan simpul , , ...,  sedemikian sehingga  adalah orang tua dari  untuk . Dari pohon pada Gambar 9.11, lintasan dari   ke  adalah , , , . Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu . Panjang lintasan dari  ke  adalah 3.

Keturunan (descendant) dan Leluhur (ancestor)

Jika terdapat lintasan dari simpul  ke simpul  di dalam pohon, maka  adalah leluhur dari simpul , dan  adalah keturunan dari simpul . Pada gambar 9.11, b adalah leluhur simpul , dan dengan demikian  adalah keturunan dari .

Saudara Kandung (sibling)

Sampul yang berorangtua sama adalah saudara kandung . Tetapi,  bukan saudara kandung , karena orangtua mereka berbeda.

Upa Pohon (subtree)

Misalkan  adalah simpul di dalam pohon . Yang dimaksud dengan upapohon dengan  sebagai akarnya ialah upagraf  sedemikian sehingga  mengandung  dan semua keturunannya dan  mengandung sisi-sisi dalam semua lintasan yang berasal dari . Sebagai contoh,  adalah upapohon dari pohon pada gambar 9.12 dengan  dan  dan  adalah simpl akarnya. Terdapat banyak upapohon . Dengan pengertian di atas, jika  adalah simpul, maka akar tiap-tiap upapohon dari  disebut anak, dan  adalah orangtua setiap akar pohon.

Gambar 9.12 Upapohon