Soal dan Pembahasan – Struktur Pohon dalam Teori Graf

Berikut ini merupakan soal dan pembahasan terkait struktur pohon dalam teori graf beserta algoritma yang menyertainya. Semoga bermanfaat!

Today Quote

Apapun 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

Soal Nomor 1
Jelaskan perbedaan dan kesamaan antara graf pohon (tree) dan hutan (forest).

Pembahasan

Kesamaan: merupakan graf asiklik (graf yang tidak memuat sikel).
Perbedaan: pohon merupakan graf terhubung, sedangkan hutan merupakan graf yang boleh terhubung ataupun tidak. Dengan kata lain, semua pohon adalah hutan, tetapi tidak semua hutan adalah pohon.

[collapse]

Soal Nomor 2
Gambarkan sebuah contoh graf dengan ketentuan berikut bila ada.
a. pohon;
b. hutan;
c. hutan yang bukan pohon;
d. pohon yang bukan hutan.

Pembahasan

Jawaban a)
Graf berikut merupakan pohon (graf terhubung yang tidak memuat sikel)

Jawaban b)
Graf $G$ dan komplemennya merupakan contoh hutan (sekaligus pohon).

Jawaban c)
Graf berikut merupakan hutan, tetapi bukan pohon, karena grafnya tak terhubung (terdiri dari $2$ komponen).

Jawaban d)
Tidak ada graf yang demikian karena semua pohon adalah hutan.

[collapse]

Baca: Soal dan Pembahasan – Graf Isomorfik dan Subgraf

Soal Nomor 3
Buktikan bahwa setiap sisi pada graf pohon adalah jembatan.

Pembahasan

Jika ada $2$ lintasan dari titik $A$ ke titik $B$ pada suatu graf, maka ada sikel yang memuat kedua titik itu juga. Oleh karenanya, ketika kita menghilangkan sisi $AB$ pada suatu pohon dan tetap ada lintasan dari $A$ ke $B$, maka graf itu bukan pohon karena memuat sikel. Jadi, setiap sisi pada graf pohon adalah jembatan (terbukti).

[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$). Tapi, di manapun 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]

Soal Nomor 8
Jika $P = \{v_0, v_1, v_2, \cdots, v_n\}$ adalah sebuah lintasan terpanjang di pohon $G$, maka $d(v_0) = d(v_n) = 1$. Buktikan pernyataan tersebut.

Pembahasan

Jika lintasan berakhir pada titik yang masih memiliki sisi yang terkait dengannya, maka kita bisa menambahkan sisi tersebut sebagai bagian dari lintasan itu sehingga lintasannya semakin panjang. Misalkan kita memiliki lintasan terpanjang  $P = \{v_0, v_1, v_2, \cdots, v_n\}$. Andaikan $d(v_n) > 1$, maka ada titik $v_{n+1}$ dan sisi $e = (v_n, v_{n+1})$ yang bukan bagian dari lintasan $P$. Jika tidak, kita akan memperoleh suatu sikel pada pohon. Lintasan $v_1, \cdots, v_n, v_{n+1}$ lebih panjang dari $P$. Ini kontradiksi dengan pernyataan bahwa $P$ lintasan terpanjang. Jadi, pengandaian diingkari, sehingga haruslah $d(v_n) = 1$. Dengan prinsip yang sama, dapat dibuktikan $d(v_1) = 1$.

[collapse]