Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini menjelaskan tentang pohon dalam Matematika Diskrit, di mana pohon merupakan graf yang memiliki N simpul dengan N-1 busur. Pohon adalah satu-satunya graf yang memiliki sifat tersebut. Jika beberapa pohon digabungkan menjadi hutan, jumlah simpul dan busurnya akan berbeda. Sebagai contoh, hutan dengan 11 simpul dan 2 komponen akan memiliki 9 busur. Selain itu, jika setiap simpul memiliki M anak dan terdapat I simpul internal, maka jumlah simpul keseluruhan adalah M-I+1.

Nah, pohon ini selain tadi sifatnya adalah setiap dua simpul itu bisa dihubungkan dengan rintasan yang tunggal,

dia juga merupakan penamanya graf yang bersifat khusus.

Jadi kalau dia punya N simpul, maka banyaknya busur adalah N-1.

Jadi ini adalah satu-satunya graf yang mempunyai sifat seperti itu, jadi pohon itu, kalau yang lain itu tidak punya.

Jadi kalau kita punya hutan, nah hutan itu kan terdiri dari beberapa pohon,

misalnya ini pohon yang pertama, ini pohon yang kedua, ini T2.

Di T1, di sini ada 5 simpul, berarti nanti busurnya kan cuma 4.

Sedangkan untuk yang T2, kita punya 6 simpul dan 5 busur.

Kalau kita melihatnya itu sebagai hutan, maka ini menjadi satu graf yang kita sebut sebagai hutan,

tapi kita lihat di sini banyaknya simpul jadi 11 sekarang, dan banyaknya busur itu 9.

Jadi tidak memenuhi sifat sebagai pohon tadi, kalau pohon kan N simpul, busurnya adalah sebanyak N-1.

Kalau hutan, kita punya N simpul, dalam hal ini contohnya N-11,

maka banyaknya busur adalah N dikurang, bukan 1, tapi banyaknya komponen.

Karena di sini komponennya ada 2, T1 dan T2, berarti di sini ada N-2, 11 kurang 2 itu jatuhnya 9.

Jadi setiap hutan dengan N simpul dan K komponen, dia akan mempunyai N-K busur.

Kalau M-Ri, yang anaknya itu tidak cuma 2 tapi banyak, dan N-M-Ri itu penuh,

dalam arti setiap simpul itu punya anaknya sebanyak M.

Kalau kita punya I simpul internal, dia akan punya semuanya itu adalah M-I plus 1.

Itu dengan mudah nanti bisa kita lihat melalui contoh, buktinya juga sebetulnya tidak terlalu sulit.