Materi, Soal, dan Pembahasan – Pohon dalam Teori Graf

Graf pohon

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 induk, anak, saudara kandung, keturunan, leluhur, dan sebagainya.

Artikel tentang Graf

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. Selain itu, pohon harus berupa graf hingga (finite graph), artinya simpulnya ada sebanyak berhingga. 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. Lebih lanjut, pohon pasti merupakan graf sederhana karena jika tidak, sisi rangkap atau gelang akan membuat graf itu memiliki siklus sehingga bertentangan dengan definisi pohon.

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.

Teorema: Bilangan Kromatik Pohon

Dua warna sudah cukup untuk mewarnai simpul setiap pohon sehingga tidak ada dua simpul yang bertetangga mempunyai warna yang sama. Dengan kata lain, pohon mempunyai bilangan kromatik 2.

Bukti

Sebagai contoh, berikut ini merupakan pohon dengan 7 simpul dan pewarnaan simpulnya dengan hanya menggunakan dua warna, yaitu merah dan biru.


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.

Misalkan G=(V,E) merupakan graf tak-berarah terhubung yang bukan pohon, artinya G memuat siklus, setidaknya satu. G dapat diubah menjadi pohon T=(VT,ET) dengan cara memutuskan siklus-siklus yang ada. Secara teknis, tinjau suatu siklus di T, kemudian hapus satu sisi dari siklus tersebut sehingga siklusnya sekarang berkurang satu. Lakukan proses serupa sampai tidak ditemukan siklus lagi di G. Berdasarkan definisi pohon, sekarang G=T merupakan pohon, atau lebih spesifik, pohon merentang.

Definisi: Pohon Merentang

Suatu pohon T=(VT,ET) dikatakan pohon merentang (spanning tree) dari suatu graf G=(VG,EG) jika T merupakan pohon dengan VT=VG dan ETEG.

Dengan kata lain, jika subgraf merentang (spanning subgraph) dari suatu graf terhubung merupakan pohon, maka subgraf merentang tersebut dinamai pohon merentang. Sebagai contoh, diberikan graf G dan beberapa pohon merentangnya.
Beberapa teorema penting terkait pohon diberikan sebagai berikut.

Teorema: Banyak Simpul dan Sisi pada Pohon

Pohon dengan n simpul memiliki n1 sisi.

Bukti

Teorema: Ketaksamaan Kardinalitas Himpunan Simpul dan Sisi 

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

Bukti

Teorema: Daun pada Pohon Taktrivial

Pohon taktrivial memiliki paling sedikit dua daun.

Bukti

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. Salah satu sumber berbahasa Indonesia yang digunakan adalah buku “Matematika Diskrit” karya Rinaldi Munir. Untuk sumber berbahasa Inggris, salah satu 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.

No.Bahasa IndonesiaBahasa Inggris1.Graf TerhubungConnected Graph1.PohonTree2.Pohon BebasFree Tree3.Pohon BerakarRooted Tree2.HutanForest3.DaunLeaf4.AnakChildren5.IndukParent6.Saudara KandungSibling7.LeluhurAncestor8.KeturunanDescendant8.Simpul DalamInternal Vertex9.SubpohonSubtree10.Pohon m-erm-ary Tree11.Pohon BinerBinary Tree12.Pohon Berakar TerurutOrdered Rooted Tree13.Anak KiriLeft Child14.Anak KananRight Child15.Subpohon KiriLeft Subtree16.Subpohon KananRight Subtree17.TingkatLevel18.KetinggianHeight19.SeimbangBalanced

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

Dari lima model graf berikut, manakah graf yang tergolong pohon?

Pembahasan

Soal Nomor 2

Misalkan pohon T dan U masing-masing memiliki 5.000 simpul dan 5.001 simpul. Jika T dan U merupakan graf yang saling lepas, gabungan dari keduanya akan membentuk hutan yang memuat sisi sebanyak
A. 5.000                     D. 10.001
B. 5.001                     E. 10.003
C. 9.999

Pembahasan

Soal Nomor 3

Suatu pohon mempunyai 2n simpul berderajat 1, 3n simpul berderajat 2, dan n simpul berderajat 3. Banyak simpul dan sisi dari pohon tersebut berturut-turut adalah
A. 13 dan 12
B. 12 dan 11
C. 10 dan 9
D. 8 dan 7
E. 6 dan 5

Pembahasan

Soal Nomor 4

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

Pembahasan

Bagian Uraian

Soal Nomor 1

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

Pembahasan

Soal Nomor 2

Misalkan m dan n merupakan bilangan bulat positif. Graf bipartit lengkap Km,n manakah yang merupakan pohon?

Pembahasan

Soal Nomor 3

Buktikan bahwa setiap sisi dari pohon merupakan jembatan.

Pembahasan

Soal Nomor 4

Buktikan bahwa jika P={v0,v1,v2,,vn} merupakan lintasan terpanjang dari pohon T, maka deg(v0)=deg(vn)=1.

Pembahasan

Soal Nomor 5

Suatu graf merupakan pohon jika dan hanya jika setiap pasangan simpul berbeda di graf tersebut terhubung oleh tepat satu lintasan.

Pembahasan