Soal dan Pembahasan – Struktur Pohon dalam Teori Graf

Pohon merupakan salah satu graf khusus dengan ciri-ciri tertentu. Menurut catatan sejarah, pohon digunakan pertama kali pada tahun 1857 oleh seorang matematikawan berkebangsaan Inggris bernama Arthur Cayley (1821–1895). Cayley menggunakannya untuk menghitung jenis senyawa kimia tertentu. Sejak saat itu, pohon banyak diaplikasikan untuk menyelesaikan berbagai masalah lintas bidang sampai saat ini.

Graf khusus seperti itu diberi nama “pohon” karena model graf tersebut dapat digambarkan sebagai pohon dengan banyak percabangannya. Selain itu, istilah pohon (yang bukan merujuk pada tumbuhan) juga sebenarnya telah kita gunakan dalam kehidupan sehari-hari, misalnya pohon faktor dan pohon keluarga. Pada pohon keluarga, simpul merepresentasikan anggota keluarga, sedangkan sisi merepresentasikan hubungan orang tua dan anak. Sebagai contoh, berikut ini merupakan contoh pohon keluarga Patrick, salah satu karakter dalam animasi serial SpongeBob Squarepants.

Ketika pertama kali belajar pohon, kita akan bertemu dengan banyak terminologi baru yang berhubungan erat dengan botani, seperti akar, cabang, daun, dan sebagainya. Selain itu, istilah kekeluargaan juga akan ditemukan (mungkin terdengar unik), seperti orang tua, anak, saudara kandung, keturunan, leluhur, dan sebagainya.

Berikut ini merupakan definisi formal dari pohon.

Definisi: Pohon

Pohon merupakan graf terhubung dan takberarah yang tidak memuat siklus.

Dari definisi tersebut, kita tahu bahwa semua pohon merupakan graf, tetapi tidak semua graf merupakan pohon. Ada syarat khusus agar graf dapat disebut sebagai pohon, yaitu graf tersebut harus terhubung dan tidak memuat siklus. Contoh graf sederhana yang merupakan pohon adalah graf trivial, yaitu graf yang memiliki satu simpul saja tanpa sisi. Graf lengkap dengan dua simpul juga merupakan pohon. Namun, graf lengkap dengan tiga simpul bukan pohon karena memuat siklus.

Contoh lain diberikan sebagai berikut.

Graf $K$ bukan pohon karena memuat siklus, salah satunya seperti yang ditandai dengan simpul dan sisi berwarna merah. Graf $L$ merupakan pohon. Dapat dilihat bahwa $L$ tidak memuat siklus. Perhatikan bahwa kita dapat menjadikan graf $K$ sebagai pohon dengan menghapus (menghilangkan) sisi pembentuk siklusnya.

Berikutnya, kita definisikan terminologi baru yang berkaitan dengan pohon.

Definisi: Hutan

Hutan merupakan graf yang tidak memuat siklus.

Secara sekilas, kita mungkin menganggap bahwa definisi pohon dan hutan mirip. Yang membedakannya adalah keterhubungan grafnya. Pohon harus berupa graf terhubung, tetapi hutan tidak mengharuskannya. Dari sini, kita tahu bahwa syarat graf untuk menjadi pohon lebih ketat dibandingkan menjadi hutan. Lebih lanjut, semua pohon merupakan hutan, tetapi tidak semua hutan merupakan pohon.

Sebagai contoh, perhatikan dua model graf berikut.
Graf $G$ dan $H$ keduanya merupakan hutan karena sama-sama tidak memuat siklus. Namun, $G$ merupakan pohon, sedangkan $H$ bukan pohon karena grafnya tidak terhubung. Dapat dilihat bahwa $H$ merupakan graf takterhubung dengan $2$ komponen.

Beberapa teorema penting terkait pohon diberikan sebagai berikut.

Teorema: Banyak Simpul dan Sisi pada Pohon

Pohon dengan $n$ simpul memiliki $n-1$ sisi.

Bukti

Teorema tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan proposisi bahwa pohon dengan $n$ simpul memiliki $n-1$ sisi.
Langkah Basis:
Untuk $n = 1,$ $P(1)$ benar karena pohon dengan $1$ simpul membentuk graf trivial yang jelas tidak memiliki sisi $($sisinya sebanyak $0).$
Langkah Induktif:
Ambil sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar, yaitu proposisi bahwa pohon dengan $k$ simpul memiliki $k-1$ sisi. Akan dibuktikan bahwa $P(k+1)$ benar, yaitu proposisi bahwa pohon dengan $k+1$ simpul memiliki $k$ sisi.
Misalkan pohon $T$ memiliki $k+1$ simpul. Karena pohon merupakan graf hingga, daun dari $T$ pasti ada, sebutlah $v.$ Misalkan $w$ merupakan induk dari $v.$ Dengan menghilangkan simpul $v$ dan sisi $\{w, v\}$ dari $T,$ diperoleh pohon baru $T’$ yang hanya karena graf yang dihasilkan masih terhubung dan tidak memuat siklus. Jelas bahwa $T’$ memiliki $k$ simpul . Menurut hipotesis induksi, $T’$ memiliki $k-1$ sisi. Akibatnya, $T$ memiliki $k$ sisi karena banyak sisi $T$ satu lebihnya dari $T’,$ yaitu ditambah dengan sisi yang menghubungkan $v$ dan $w$ tadi. Jadi, $P(k+1)$ benar.


Menurut prinsip induksi matematika, $P(n)$ benar untuk setiap bilangan asli $n.$ Dengan kata lain, pohon dengan $n$ simpul memiliki $n-1$ sisi. $\blacksquare$

[collapse]

Teorema: Ketaksamaan Kardinalitas Himpunan Simpul dan Sisi 

Jika $G = (V, E)$ merupakan graf sederhana dan terhubung, maka $|V(G)| \le |E(G)|+1$ dengan $|V(G)|$ dan $|E(G)|$ berturut-turut menyatakan kardinalitas dari himpunan simpul dan himpunan sisi $G.$

Bukti

Misalkan $G = (V, E)$ merupakan graf sederhana dan terhubung. Jika $G$ tidak memuat siklus, $G$ adalah pohon. Dengan menggunakan teorema terkait banyak simpul dan sisi pada pohon, diperoleh $|V(G)| = |E(G)|+1$ sehingga proposisi terbukti benar.
Sekarang misalkan $G$ memuat siklus, katakanlah $C.$ Pilih $e \in E(C)$ dan konstruksi graf $G_1 = G \setminus \{e\},$ yaitu graf $G$ yang tidak memuat sisi $e.$ Asumsikan $G_1$ tidak memuat siklus lagi, artinya $G_1$ merupakan pohon. Karena $e$ merupakan sisi pembentuk siklus, penghapusan sisi $e$ membuat $G_1$ masih tetap terhubung. Jelas bahwa $|E(G_1)| < |E(G)|.$ Akibatnya, diperoleh
$$|V(G)| = |V(G_1)| = |E(G_1)| + 1 < |E(G)| + 1.$$Jadi, $|V(G)| < |E(G)| + 1.$ Lebih lanjut, jika $G_1$ masih memuat siklus, lakukan proses yang serupa dengan menghilangkan sisi pembentuk siklusnya.
Dari sini, terbukti bahwa $|V(G)| \le |E(G)|+1.$ Kesamaan tercapai ketika $G$ merupakan pohon. $\blacksquare$
 

[collapse]

Teorema: Daun pada Pohon Taktrivial

Pohon taktrivial memiliki paling sedikit dua daun.

Bukti

Misalkan $T = (V, E)$ merupakan pohon taktrivial dengan $n \ge 2$ simpul. Dengan menggunakan metode kontradiksi, andaikan $T$ memiliki kurang dari dua daun. Jelas bahwa $T$ pasti memiliki satu daun karena jika tidak, siklus akan muncul sehingga bertentangan dengan definisi pohon. Misalkan daun tersebut dinamai $\ell.$
Tinjau lintasan di $T$ dengan simpul awal $\ell$ dan simpul akhir $v \in V(T).$ Karena diandaikan bahwa $T$ memiliki kurang dari dua daun, jelas $v$ bukanlah daun. Akibatnya, $v$ bertetangga dengan simpul lain, misalkan $u,$ sehingga lintasan dari $\ell$ ke $u$ menjadi semakin panjang. Lakukan hal serupa. Akibatnya, lintasannya menjadi tak hingga panjangnya. Namun, hal ini kontradiksi dengan fakta bahwa pohon merupakan graf hingga sehingga lintasan yang dimuatnya juga pasti memiliki panjang yang berhingga. Jadi, pengandaian salah.
Disimpulkan bahwa pohon memiliki paling sedikit dua daun. $\blacksquare$

[collapse]

Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang pohon. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.

Baca: Istilah Lengkap dalam Teori Graf


Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Graf Terhubung} & \text{Connected Graph} \\ 1. & \text{Pohon} & \text{Tree} \\ 2. & \text{Pohon Bebas} & \text{Free Tree} \\ 3. & \text{Pohon Berakar} & \text{Rooted Tree} \\ 2. & \text{Hutan} & \text{Forest}  \\ 3. & \text{Daun} & \text{Leaf} \\ 4. & \text{Anak} & \text{Children} \\ 5. & \text{Induk} & \text{Parent} \\ 6. & \text{Saudara Kandung} & \text{Sibling} \\ 7. & \text{Leluhur} & \text{Ancestor} \\ 8. & \text{Keturunan} & \text{Descendant} \\  \hline \end{array}$$

Today Quote

Apa pun perubahan kecil itu, jika setiap orang dari kita melakukan perubahan ke arah yang lebih baik, maka kapal besar bernama Indonesia pasti akan bergerak.

Baca: Soal dan Pembahasan – Teori Dasar Graf

Baca: Istilah Lengkap dalam Teori Graf

Bagian Pilihan Ganda

Soal Nomor 1

Misalkan pohon $T$ memiliki $49$ sisi. Satu sisi dari $T$ dihilangkan sehingga terbentuk dua pohon yang saling lepas, katakanlah $T_1$ dan $T_2.$ Jika $T_1$ dan $T_2$ memuat banyak simpul yang sama, maka banyak sisi dari $T_1$ adalah $\cdots \cdot$
A. $24$                       C. $26$                      E. $49$
B. $25$                       D. $48$

Pembahasan

Misalkan pohon $T$ memiliki $49$ sisi. Ini berarti banyak simpul yang dimuat di $T$ adalah $49 + 1 = 50.$ Karena satu sisi dihilangkan, diperoleh pohon yang saling lepas, yaitu $T_1$ dan $T_2.$ Agar banyak simpulnya sama, $T_1$ dan $T_2$ masing-masing harus memuat $50 \div 2 = 25$ simpul. Akibatnya, $T_1$ memiliki $25-1=24$ sisi.
(Jawaban A)

[collapse]

Bagian Uraian

Soal Nomor 1

Misalkan $T$ merupakan pohon dengan $60$ sisi. Pembuangan suatu sisi tertentu dari $T$ menghasilkan dua pohon $T_1$ dan $T_2.$ Jika banyak simpul pada $T_1$ sama dengan banyak sisi pada $T_2,$ tentukan banyak simpul dan banyak sisi pada $T_1$ dan $T_2.$

Pembahasan

Misalkan pohon $T$ memiliki $60$ sisi. Satu sisi dari $T$ dibuang sehingga diperoleh $T_1$ dan $T_2.$ Karena banyak sisi pada pohon sama dengan satu kurangnya dari banyak simpul, dapat kita misalkan $T_1$ memiliki $m$ simpul dan $m-1$ sisi, sedangkan $T_2$ memiliki $n$ simpul dan $n-1$ sisi. Banyak sisi secara keseluruhan adalah $60-1=59$ sehingga diperoleh persamaan $(m-1)+(n-1) = 59,$ atau $m+n=61.$
Karena diketahui banyak simpul pada $T_1$ sama dengan banyak sisi pada $T_2,$ didapat $m = n-1.$ Dari sini, diperoleh $(n-1)+n = 61$ sehingga haruslah $n = 31.$ Akibatnya, $m = 30.$
Jadi, $T_1$ memiliki $30$ simpul dan $29$ sisi, sedangkan $T_2$ memiliki $31$ simpul dan $30$ sisi.

[collapse]

Soal Nomor 2

Buktikan bahwa setiap sisi dari pohon merupakan jembatan.

Pembahasan

Misalkan $T$ merupakan pohon. Dengan menggunakan metode kontradiksi, andaikan terdapat sisi $T$, katakanlah $\{v, w\},$ yang bukan jembatan. Akibatnya, penghapusan sisi tersebut membuat $T$ tetap terhubung. Dengan kata lain, jika $G’$ merupakan graf $G$ dengan sisi $\{v, w\}$ yang dihilangkan, maka $G’$ terhubung. Dengan demikian, terdapat suatu lintasan yang menghubungkan simpul $v$ dan $w$ di $G’.$ Lintasan tersebut bersama-sama dengan $\{v, w\}$ membentuk siklus di $G.$ Hal ini kontradiksi dengan definisi pohon sebagai graf yang tidak memiliki siklus. Jadi, pengandaian salah. Disimpulkan bahwa setiap sisi dari pohon merupakan jembatan. $\blacksquare$

[collapse]

Soal Nomor 3

Buktikan bahwa jika $P = \{v_0, v_1, v_2, \cdots, v_n\}$ merupakan lintasan terpanjang dari pohon $T,$ maka $\text{deg}(v_0) = \text{deg}(v_n) = 1.$

Pembahasan

Misalkan $P = \{v_0, v_1, v_2, \cdots, v_n\}$ merupakan lintasan terpanjang dari pohon $T.$ Dengan menggunakan metode kontradiksi, andaikan $\text{deg}(v_0) \neq 1$ atau $\text{deg}(v_n) \neq 1.$ Jelas bahwa $v_0$ dan $v_n$ bukan simpul terpencil sehingga $\text{deg}(v_0) \neq 0$ atau $\text{deg}(v_n) \neq 0.$
Sekarang andaikan $\text{deg}(v_0) > 1.$ Akibatnya, terdapat simpul $v_{k}$ selain $v_1$ sehingga $v_0$ bertetangga dengan $v_k.$ Dengan kata lain, terdapat sisi $e = \{v_k, v_0\}$ yang bukan sisi pembentuk lintasan $P.$ Ini artinya ada lintasan lain di pohon $T$ yang lebih panjang dari $P,$ yaitu $\{v_k, v_0, v_1, v_2, \cdots, v_n\}.$ Namun, hal ini kontradiksi dengan fakta bahwa $P$ merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dengan cara yang serupa, andaikan $\text{deg}(v_n) > 1.$ Akibatnya, terdapat simpul $v_{n+1}$ selain $v_{n-1}$ sehingga $v_n$ bertetangga dengan $v_{n+1}.$ Dengan kata lain, terdapat sisi $e = \{v_n, v_{n+1}\}$ yang bukan sisi pembentuk lintasan $P.$ Ini artinya ada lintasan lain di pohon $T$ yang lebih panjang dari $P,$ yaitu $\{v_0, v_1, v_2, \cdots, v_n, v_{n+1}\}.$ Namun, hal ini kontradiksi dengan fakta bahwa $P$ merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dari sini, disimpulkan bahwa $\text{deg}(v_0) = \text{deg}(v_n) = 1.$ $\blacksquare$

[collapse]

Soal Nomor 4

Buktikan bahwa graf pohon dengan paling sedikit dua titik adalah graf bipartisi.

Pembahasan

Teorema graf bipartisi menyatakan bahwa suatu graf disebut graf bipartisi jika dan hanya jika graf itu tidak memuat sikel ganjil.
Karena pohon tidak memiliki sikel (termasuk sikel ganjil), maka dengan menggunakan teorema tersebut, terbukti bahwa pohon dengan paling sedikit $2$ titik merupakan graf bipartisi. 

[collapse]

Soal Nomor 5

Suatu sisi $e$ dari graf $G$ adalah jembatan jika dan hanya jika $e$ bukan merupakan bagian dari sikel dalam $G$. Buktikan pernyataan tersebut.

Pembahasan

Pembuktian dengan menggunakan kontradiksi.
$(\Rightarrow)$
Misal $e$ jembatan di $G$ dan merupakan bagian dari sikel $G$. Ketika $e$ dihapus, kita tahu bahwa akan ada lintasan di antara dua titik ujung sisi $e$, dan jelas ini kontradiksi dengan definisi jembatan.
$(\Leftarrow)$
Misalkan $e$ bukan bagian dari sikel di $G$. Hapus sisi $e$ dari $G$, dan kita misalkan ada lintasan pada titik-titik ujung $e$ setelah sisi $e$ dihapus karena $e$ bukan jembatan. Sekarang, tambahkan sisi $e$ kembali. Karena ada lintasan di antara dua titik ujung $e$ yang tidak melalui sisi $e$, maka ada sikel di $G$ yang melewati sisi $e$, yang ternyata kontradiksi karena diasumsikan bahwa $e$ bukan jembatan. Pengandaian diingkari. Berarti, $e$ jembatan. (Terbukti)

[collapse]

Soal Nomor 6

Nyatakan pernyataan berikut apakah benar atau salah, serta berikan alasannya.

  1. Sebuah titik $v$ dari pohon $T$ adalah titik potong jika dan hanya jika $d(v) \geq 1$
  2. Jika $G$ adalah sebuah graf yang tepat memiliki sebuah spanning tree, maka $G$ adalah pohon.

Pembahasan

Jawaban a)
Pernyataan salah. Titik $v$ pada pohon merupakan titik potong jika dan hanya jika $d(v) \geq 2$. Ini terjadi karena penghilangannya mengakibatkan sisi yang bersisian dengan titik itu juga hilang, padahal sisi tersebut merupakan jembatan sehingga membuat graf menjadi tak terhubung. Di lain pihak, titik pada pohon dengan derajat $1$ (titik ujung) bukan titik potong karena penghilangan titik ini beserta satu sisinya tidak membuat graf menjadi tak terhubung.
Jawaban b)
Pernyataan benar. Pohon merentang (spanning tree) dari suatu graf adalah pohon yang memuat semua titik pada graf itu. Karena spanning tree pada graf itu tunggal (berarti semua titik dan semua sisi dilewati), maka graf itu sendiri adalah pohon.

[collapse]

Baca: Soal dan Pembahasan – Keterhubungan Graf

Soal Nomor 7

Misalkan $T$ adalah pohon dengan $n$ titik, $n \geq 4$, dan $v$ sebuah titik berderajat maksimum dalam $T$.
Tunjukkan bahwa $T$ adalah lintasan (path) jika dan hanya jika $d(v) = 2$.

Pembahasan

Pernyataan yang akan dibuktikan berbentuk biimplikasi sehingga harus dibuktikan $2$ arah.
Premis 1: Jika $T$ lintasan, maka $d(v) = 2$.
Premis 2: Jika $d(v) = 2$, maka $T$ lintasan.
Pembuktian premis 1:
Untuk $d(v) < 2$ jelas tidak mungkin karena diberikan bahwa $n \geq 4$. Andaikan $d(v) > 2$. Lintasan $T$ (yang melewati titik $v$) akan bercabang (padahal lintasan seharusnya linear) sehingga kontradiksi dengan pengandaian yang ada. Jadi, haruslah $d(v) = 2$.
Pembuktian premis 2:
Gunakan induksi. Misalkan $T_n$ adalah suatu pohon dengan $n$ titik, $n \geq 4$, dan maksimum derajat titiknya $2$. Untuk $n = 4$, hanya ada $2$ kemungkinan untuk $T_4$ termasuk isomorfiknya yaitu sebagai berikut.

Pohon pada gambar kiri merupakan suatu lintasan dengan derajat maksimum titiknya 2, sedangkan pohon pada gambar kanan bukan lintasan (derajat maksimum titiknya 3). Sekarang, misalkan $n \geq 5$ dan asumsi ini berlaku untuk semua $n$ bilangan asli. Untuk mengonstruksi $T_{n + 1}$, kita harus menambah satu titik lagi pada $T_n$. Karena hipotesisnya kita memiliki titik dengan derajat maksimum tidak lebih dari $2$, maka hanya ada $2$ pilihan untuk menambahkan titik tersebut, yaitu di awal dan akhir lintasan $T_n$ (bila tidak, $T_{n + 1}$ akan memiliki derajat maksimum $3$). Namun, di mana pun kita meletakkan titik itu baik di awal maupun akhir lintasan, $T_{n+1}$ adalah lintasan dan dengan menggunakan induksi, bukti ini berlaku untuk semua $n$.

[collapse]

5 1 vote
Article Rating

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini jika ada kesalahan pengetikan sekecil apa pun, seperti kesalahan pengetikan, kode LaTeX yang tidak berjalan, atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x