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 bukan pohon karena memuat siklus, salah satunya seperti yang ditandai dengan simpul dan sisi berwarna merah. Graf merupakan pohon. Dapat dilihat bahwa tidak memuat siklus. Perhatikan bahwa kita dapat menjadikan graf 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
Bukti
Misalkan merupakan sembarang pohon. Pertama, beri warna pertama pada sembarang simpul Kemudian, beri warna kedua pada simpul-simpul yang bertetangga dengannya. Selanjutnya, beri warna pertama pada simpul-simpul yang bertetangga dengan simpul yang diberi warna kedua tadi. Lakukan proses ini sampai semua simpul diwarnai. Dengan demikian, 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
[collapse]
Sebagai contoh, berikut ini merupakan pohon dengan 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 dan keduanya merupakan hutan karena sama-sama tidak memuat siklus. Namun, merupakan pohon, sedangkan bukan pohon karena grafnya tidak terhubung. Dapat dilihat bahwa merupakan graf takterhubung dengan komponen.
Misalkan merupakan graf tak-berarah terhubung yang bukan pohon, artinya memuat siklus, setidaknya satu. dapat diubah menjadi pohon dengan cara memutuskan siklus-siklus yang ada. Secara teknis, tinjau suatu siklus di kemudian hapus satu sisi dari siklus tersebut sehingga siklusnya sekarang berkurang satu. Lakukan proses serupa sampai tidak ditemukan siklus lagi di Berdasarkan definisi pohon, sekarang merupakan pohon, atau lebih spesifik, pohon merentang.
Definisi: Pohon Merentang
Suatu pohon dikatakan pohon merentang (spanning tree) dari suatu graf jika merupakan pohon dengan dan
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 dan beberapa pohon merentangnya.
Beberapa teorema penting terkait pohon diberikan sebagai berikut.
Teorema: Banyak Simpul dan Sisi pada Pohon
Pohon dengan simpul memiliki sisi.
Bukti
Teorema tersebut akan dibuktikan dengan menggunakan induksi matematika.
Misalkan merupakan bilangan asli. Misalkan juga menyatakan proposisi bahwa pohon dengan simpul memiliki sisi.
Langkah Basis:
Untuk benar karena pohon dengan simpul membentuk graf trivial yang jelas tidak memiliki sisi sisinya sebanyak
Langkah Induktif:
Ambil sembarang bilangan asli Asumsikan benar, yaitu proposisi bahwa pohon dengan simpul memiliki sisi. Akan dibuktikan bahwa benar, yaitu proposisi bahwa pohon dengan simpul memiliki sisi.
Misalkan pohon memiliki simpul. Karena pohon merupakan graf hingga, daun dari pasti ada, sebutlah Misalkan merupakan induk dari Dengan menghilangkan simpul dan sisi dari diperoleh pohon baru yang hanya karena graf yang dihasilkan masih terhubung dan tidak memuat siklus. Jelas bahwa memiliki simpul . Menurut hipotesis induksi, memiliki sisi. Akibatnya, memiliki sisi karena banyak sisi satu lebihnya dari yaitu ditambah dengan sisi yang menghubungkan dan tadi. Jadi, benar.
Menurut prinsip induksi matematika, benar untuk setiap bilangan asli Dengan kata lain, pohon dengan simpul memiliki sisi.
[collapse]
Teorema: Ketaksamaan Kardinalitas Himpunan Simpul dan Sisi
Jika merupakan graf sederhana dan terhubung, maka dengan dan berturut-turut menyatakan kardinalitas dari himpunan simpul dan himpunan sisi
Bukti
Misalkan merupakan graf sederhana dan terhubung. Jika tidak memuat siklus, adalah pohon. Dengan menggunakan teorema terkait banyak simpul dan sisi pada pohon, diperoleh sehingga proposisi terbukti benar.
Sekarang misalkan memuat siklus, katakanlah Pilih dan konstruksi graf yaitu graf yang tidak memuat sisi Asumsikan tidak memuat siklus lagi, artinya merupakan pohon. Karena merupakan sisi pembentuk siklus, penghapusan sisi membuat masih tetap terhubung. Jelas bahwa Akibatnya, diperoleh
Jadi, Lebih lanjut, jika masih memuat siklus, lakukan proses yang serupa dengan menghilangkan sisi pembentuk siklusnya.
Dari sini, terbukti bahwa Kesamaan tercapai ketika merupakan pohon.
[collapse]
Teorema: Daun pada Pohon Taktrivial
Pohon taktrivial memiliki paling sedikit dua daun.
Bukti
Misalkan merupakan pohon taktrivial dengan simpul. Dengan menggunakan metode kontradiksi, andaikan memiliki kurang dari dua daun. Jelas bahwa pasti memiliki satu daun karena jika tidak, siklus akan muncul sehingga bertentangan dengan definisi pohon. Misalkan daun tersebut dinamai
Tinjau lintasan terpanjang di dengan simpul awal dan simpul akhir yaitu Karena hanya memiliki satu daun simpul memiliki tetangga selain katakanlah Akibatnya, lintasan dapat diperpanjang lagi menjadi Hal ini kontradiktif dengan fakta bahwa kita sebelumnya sudah membuat lintasan terpanjang. Jadi, pengandaian salah. Disimpulkan bahwa pohon memiliki paling sedikit dua daun.
[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. 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.
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
Graf pada opsi A dan B merupakan graf sederhana, tetapi keduanya bukan pohon karena memuat siklus (salah satunya yang berupa bangun segitiga). Graf pada opsi C merupakan pohon karena tidak memuat siklus dan juga terhubung. Graf pada opsi D bukan graf sederhana karena memuat gelang sehingga bukan tergolong pohon. Graf pada opsi E juga bukan graf sederhana karena memuat sisi rangkap. Lebih lanjut, graf tersebut takterhubung sehingga jelas bukan tergolong pohon.
(Jawaban C)
[collapse]
Soal Nomor 2
Misalkan pohon dan masing-masing memiliki simpul dan simpul. Jika dan merupakan graf yang saling lepas, gabungan dari keduanya akan membentuk hutan yang memuat sisi sebanyak
A. D.
B. E.
C.
Pembahasan
Banyak sisi yang dimiliki suatu pohon sama dengan satu kurangnya dari banyak simpul. Karena memiliki simpul, sisinya ada sebanyak Begitu juga dengan yang memiliki simpul sehingga sisinya ada sebanyak Karena dan saling lepas (tidak ada simpul maupun sisi yang sama), banyak sisi semuanya ada Jadi, ada sisi pada hutan yang terbentuk dari gabungan dua pohon tersebut.
(Jawaban C)
[collapse]
Soal Nomor 3
Suatu pohon mempunyai simpul berderajat simpul berderajat dan simpul berderajat Banyak simpul dan sisi dari pohon tersebut berturut-turut adalah
A. dan
B. dan
C. dan
D. dan
E. dan
Pembahasan
Misalkan pohon tersebut dinotasikan Menurut lema jabat tangan, jumlah derajat semua simpul dari setiap graf adalah kali banyak sisi yang dimiliki graf tersebut. Dengan demikian,
Karena banyak sisi yang dimiliki pohon sama dengan satu kurangnya dari banyak simpul, diperoleh
Substitusikan persamaan pada menghasilkan
Jadi, banyak simpulnya adalah sedangkan banyak sisinya adalah
(Jawaban B)
[collapse]
Soal Nomor 4
Misalkan pohon memiliki sisi. Satu sisi dari dihilangkan sehingga terbentuk dua pohon yang saling lepas, katakanlah dan Jika dan memuat banyak simpul yang sama, maka banyak sisi dari adalah
A. C. E.
B. D.
Pembahasan
Misalkan pohon memiliki sisi. Ini berarti banyak simpul yang dimuat di adalah Karena satu sisi dihilangkan, diperoleh pohon yang saling lepas, yaitu dan Agar banyak simpulnya sama, dan masing-masing harus memuat simpul. Akibatnya, memiliki sisi.
(Jawaban A)
[collapse]
Bagian Uraian
Soal Nomor 1
Misalkan merupakan pohon dengan sisi. Pembuangan suatu sisi tertentu dari menghasilkan dua pohon dan Jika banyak simpul pada sama dengan banyak sisi pada tentukan banyak simpul dan banyak sisi pada dan
Pembahasan
Misalkan pohon memiliki sisi. Satu sisi dari dibuang sehingga diperoleh dan Karena banyak sisi pada pohon sama dengan satu kurangnya dari banyak simpul, dapat kita misalkan memiliki simpul dan sisi, sedangkan memiliki simpul dan sisi. Banyak sisi secara keseluruhan adalah sehingga diperoleh persamaan atau
Karena diketahui banyak simpul pada sama dengan banyak sisi pada didapat Dari sini, diperoleh sehingga haruslah Akibatnya,
Jadi, memiliki simpul dan sisi, sedangkan memiliki simpul dan sisi.
[collapse]
Soal Nomor 2
Misalkan dan merupakan bilangan bulat positif. Graf bipartit lengkap manakah yang merupakan pohon?
Pembahasan
Misalkan dan merupakan bilangan asli. Graf bipartit lengkap memiliki banyak simpul dan banyak sisi Agar graf tersebut dapat digolongkan sebagai pohon, banyak sisi harus satu kurangnya dari banyak simpul. Dari sini, diperoleh
Dari persamaan terakhir, diperoleh atau Dengan kata lain, graf bipartit lengkap merupakan pohon jika atau salah satunya bernilai Secara umum, merupakan pohon untuk setiap bilangan bulat positif
[collapse]
Soal Nomor 3
Buktikan bahwa setiap sisi dari pohon merupakan jembatan.
Pembahasan
Misalkan merupakan pohon. Dengan menggunakan metode kontradiksi, andaikan terdapat sisi , katakanlah yang bukan jembatan. Akibatnya, penghapusan sisi tersebut membuat tetap terhubung. Dengan kata lain, jika merupakan graf dengan sisi yang dihilangkan, maka terhubung. Dengan demikian, terdapat suatu lintasan yang menghubungkan simpul dan di Lintasan tersebut bersama-sama dengan membentuk siklus di Hal ini kontradiktif dengan definisi pohon sebagai graf yang tidak memiliki siklus. Jadi, pengandaian salah. Disimpulkan bahwa setiap sisi dari pohon merupakan jembatan.
[collapse]
Soal Nomor 4
Buktikan bahwa jika merupakan lintasan terpanjang dari pohon maka
Pembahasan
Misalkan merupakan lintasan terpanjang dari pohon Dengan menggunakan metode kontradiksi, andaikan atau Jelas bahwa dan bukan simpul terpencil sehingga atau
Sekarang andaikan Akibatnya, terdapat simpul selain sehingga bertetangga dengan Dengan kata lain, terdapat sisi yang bukan sisi pembentuk lintasan Ini artinya ada lintasan lain di pohon yang lebih panjang dari yaitu Namun, hal ini kontradiktif dengan fakta bahwa merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dengan cara yang serupa, andaikan Akibatnya, terdapat simpul selain sehingga bertetangga dengan Dengan kata lain, terdapat sisi yang bukan sisi pembentuk lintasan Ini artinya ada lintasan lain di pohon yang lebih panjang dari yaitu Namun, hal ini kontradiktif dengan fakta bahwa merupakan lintasan terpanjang. Jadi, pengandaian salah.
Dari sini, disimpulkan bahwa
[collapse]
Soal Nomor 5
Suatu graf merupakan pohon jika dan hanya jika setiap pasangan simpul berbeda di graf tersebut terhubung oleh tepat satu lintasan.
Pembahasan
Kita akan membuktikan proposisi di atas dari dua arah karena proposisi tersebut berupa biimplikasi.
Arah kiri:
Misalkan merupakan pohon. Akan dibuktikan bahwa setiap pasangan simpul berbeda di terhubung oleh tepat satu lintasan.
Karena terhubung berdasarkan definisi pohon, setiap pasangan simpul berbeda di terhubung oleh setidaknya satu lintasan. Berikutnya, akan dibuktikan bahwa lintasan tersebut tunggal. Dengan menggunakan metode kontradiksi, andaikan terdapat pasangan simpul berbeda di , katakanlah dan yang terhubung oleh dua lintasan dan Misalkan merupakan simpul pertama di yang tidak termuat di dan dengan merupakan simpul berikutnya yang termuat di dan Akibatnya, lintasan merupakan siklus yang terbentuk karena eksistensi lintasan dan Hal ini kontradiktif dengan permisalan bahwa merupakan pohon karena pohon seharusnya tidak memuat siklus. Jadi, pengandaian salah. Terbukti bahwa setiap pasangan simpul berbeda di terhubung oleh tepat satu lintasan.
Arah kanan:
Misalkan merupakan graf yang setiap pasangan simpul berbedanya terhubung oleh tepat satu lintasan. Akan ditunjukkan bahwa merupakan pohon. Karena setiap pasangan simpul berbeda di terhubung oleh suatu lintasan, menurut definisi, terhubung. Berikutnya, perlu ditunjukkan bahwa asiklik (tidak memuat siklus).
Dengan menggunakan metode kontradiksi, andaikan memuat siklus Pilih simpul dengan sehingga Akibatnya, memuat dua lintasan dari ke , yaitu lintasan dan lintasan Hal ini kontradiktif dengan permisalan bahwa merupakan graf yang setiap pasangan simpul berbedanya terhubung oleh tepat satu lintasan. Jadi, pengandaian salah. Disimpulkan bahwa tidak memuat siklus. Karena terhubung dan tidak memuat siklus, berdasarkan definisi, merupakan pohon.
[collapse]