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

Video ini membahas tentang Teorema 1 Pohon yang menjelaskan syarat pohon dalam Matematika Diskrit. Pohon merupakan graf yang memungkinkan lintasan tunggal antara dua simpul tanpa membentuk sirkuit. Teorema ini menyatakan bahwa sebuah graf adalah pohon jika dan hanya jika setiap dua simpul di dalamnya memiliki lintasan tunggal. Dengan demikian, graf pohon tidak memuat subgraf yang membentuk lingkaran.

Nah sekarang, karena kita lihat tadi ada kaitannya antara sepasang simpul yang bisa dihubungkan tadi,

si pohon itu, jadi graf yang berbentuk pohon itu kita selalu bisa mendapatkan lintasan

antara dua simpul pada graf tersebut dan lintasan tersebut itu tunggal.

Jadi kalau kita punya contohnya ini saya punya pohon di sini,

maka kita bisa lihat dari misalnya di sini U1, ini U2, U3, U4, U5, U6, U7 dan U8,

maka kalau kita mau lihat dari U1 ke U6, lintasannya melalui U4 ke U6 dan cuma ada satu,

tidak ada lintasan yang lain, jadi dia tunggal dan kalau lintasannya itu selalu kita dapatkan tunggal,

pasti itu berbentuk pohon, jadi di sini teoremanya itu jika dan hanya jika.

Teoremanya ini bisa kita buktikan karena buktinya tidak terlalu rumit, bisa kita jelaskan sekarang.

Jadi bagian yang pertama adalah kita asumsikan si grafnya itu adalah pohon,

kemudian mau kita buktikan akan ada lintasan tunggal, jadi sekarang asumsikan T nya adalah pohon,

maka karena dia pohon dan bukan hutan, T nya terhubung dan tidak memuat sirkuitkan.

Sekarang kita ambil dua simpul sembarang misalnya X dan Y,

karena T nya terhubung pasti ada lintasan sederhana di sini antara X dan Y,

lintasan ini harus tunggal karena kalau kita punya dua lintasan,

kalau kita punya dua lintasan seperti ini maka kita akan bisa memuat sirkuitkan,

sehingga hal ini tidak mungkin terjadi pada pohon,

jadi lintasan antara dua simpul sembarang T itu harus tunggal.

kita asumsikan selalu ada lintasan tunggal antara sembarang dua simpul X dan Y,

jadi T terhubung karena ya itu tadi T atau graf itu terhubung

kalau syaratnya adalah setiap dua simpul itu kita punya lintasan,

tidak perlu tunggal tapi pokoknya ada lintasannya,

jadi karena kita selalu punya lintasan antara dua simpul maka dia terhubung.

Nah T itu tidak mungkin memuat sirkuit sederhana,

karena kalau dia memuat sirkuit sederhana yang juga memuat X dan Y,

misalnya kayak contoh yang tadi ada lintasan dari kiri, ada lintasan dari kanan,

akibatnya dia akan membentuk lingkaran atau sirkuit,

jadi kalau kita punya lintasan tunggal antara dua simpul sembarang,

karena pasti si graf ini tidak memuat subgraf yang berbentuk lingkaran