Soal dan Pembahasan – Pohon/Tree (Graf ~ Matematika Diskrit)

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

Penyelesaian

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

Penyelesaian


(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 (semua pohon adalah hutan).

[collapse]

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

Penyelesaian

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.

[collapse]

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

Penyelesaian

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.

Penyelesaian

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.
a. Sebuah titik v dari pohon T adalah titik potong jika dan hanya jika d(v) \geq 1
b. Jika G adalah sebuah graf yang tepat memiliki sebuah spanning tree, maka G adalah pohon.
c. Jika T adalah spanning tree dari graf G yang memuat sisi e, maka T.e adalah spanning tree dari G.e

Penyelesaian Belum Lengkap

(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.
(Jawaban c) –

[collapse]

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

Penyelesaian

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.

Penyelesaian

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]

Soal Nomor 9
Gunakan Algoritma Prim untuk mendapatkan pohon rentang minimal dari graf G berikut.

Penyelesaian

—-INISIASI: ALGORITMA PRIM—–
Step 1: Pilih salah satu titik, misalnya titik a.
Step 2: Misalkan T = \{a\} dan F = \{b, c, d, e, f, g, h, i\}. Dengan meninjau keterhubungan langsung titik pada himpunan F dengan titik pada himpunan T, diperoleh
a(-, -); b(a, 4)~\boxed{c(a, 3)}
d(a, 5)~e(-, -)~f(-, -)~g(-, -)~h(-, -)~i(-. -)
Pilih titik c(a, 3) (bobot c ke a adalah 3).
Tulis T = \{a, c\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c\} dan F = \{b, d, e, f, g, h, i\}. Gunakan prinsip yang sama.
Untuk selanjutnya, titik yang tidak terhubung langsung dengan titik-titik di T tidak ditulis.
c(a, 3); \boxed{b(a, 4)}~b(c,6)~d(a,5)~\boxed{d(c,4)}
Ada 2 pilihan. Pilih salah satu, misalkan dipilih b(a, 4) (bobot b ke a adalah 4).
Tulis T = \{a, c, b\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b\} dan F = \{d, e, f, g, h, i\}
b(a, 4); d(a,5)~\boxed{d(c,4)}
Pilih d(c, 4) (bobot d ke c adalah 4).
Tulis T = \{a, c, b, d\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d\} dan F = \{e, f, g, h, i\}
d(c, 4); ~\boxed{e(d, 2)}
Pilih e(d, 2) (bobot e ke d adalah 2).
Tulis T = \{a, c, b, d, e\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e\} dan F = \{f, g, h, i\}
e(d, 2); h(e,2)~\boxed{g(e, 1)}~f(e, 4)
Pilih g(e, 1) (bobot g ke e adalah 1).
Tulis T = \{a, c, b, d, e, g\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—
Step 2: Misalkan T = \{a, c, b, d, e, g\} dan F = \{f, h, i\}
g(e, 1); \boxed{h(e, 2)}~f(e, 4)~h(g, 4)~\boxed{i(g, 2)}
Ambil salah satu. Misal dipilih h(e, 2) (bobot h ke e adalah 2).
Tulis T = \{a, c, b, d, e, g, h\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e, g, h\} dan F = \{f,  i\}
h(e, 2); i(h,3)~\boxed{i(g, 2)}~f(e, 4)
Pilih i(g, 2) (bobot i ke g adalah 2).
Tulis T = \{a, c, b, d, e, g, h, i\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e, g, h, i\} dan F = \{f\}
i(g, 2); \boxed{f(i,3)}~f(e, 4)
Pilih f(i, 3) (bobot f ke i adalah 3).
Tulis T = \{a, c, b, d, e, g, h, i, f\}
Step 3: Semua titik berada pada himpunan T. Beri pesan: T = \{a, c, b, d, e, g, h, i, f\} adalah pohon rentang minimal dengan bobot 3 + 4 + 4 + 2 + 1 + 2 + 2 + 3 + 3 = 24
—ALGORITMA SELESAI—–

[collapse]

Ayo Beri Rating Postingan Ini
KategoriMatematika DiskritTag, , ,

2 Balasan untuk “Soal dan Pembahasan – Pohon/Tree (Graf ~ Matematika Diskrit)”

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *