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

Video ini membahas contoh pohon dan bukan pohon dalam graf. Pohon adalah graf tanpa subgraf berbentuk lingkaran atau sirkuit, seperti contoh pada graf G1 dan G2. Namun, jika terdapat subgraf dengan lingkaran atau sirkuit, seperti pada graf G3, maka itu bukan pohon. Selain itu, dalam contoh terakhir, terdapat hutan yang terdiri dari tiga pohon yang tidak terhubung satu sama lain. Komponen-komponen dalam hutan ini adalah A, F dan C, E, B, D.

Kalau kita lihat contoh dari graf yang sembarang, disini kita punya empat graf, kita lihat.

Untuk yang pertama, kalau kita ambil sepasang simpul, kita selalu bisa mendapatkan lintasan yang menghubungkan kedua simpul tersebut.

Misalnya disini saya ambil B ke E, kita bisa lihat ini dari B ke C, C ke F, dan F ke E.

Ini pohon tidak? Ya pohon, karena tidak ada subgraf berbentuk sirkuit atau lingkaran.

Begitu juga untuk G2, G2 itu juga tidak membentuk sirkuit atau lingkaran, dan dia juga terhubung.

Yang G3, kita bisa mendapatkan subgraf yang berbentuk lingkaran atau sirkuit di dalamnya.

Jadi kalau kita lihat disini, kita punya A, D, E, kemudian B, A.

Ini walaupun gambarnya tidak seperti lingkaran, tapi ini adalah lingkaran, sehingga ini bukan merupakan pohon.

Yang contoh terakhir, kita lihat disini, ini sebetulnya walaupun gambarnya kelihatan jadi satu, ini terdiri dari dua pohon.

Jadi ini tidak terhubung, kita punya pohon pertama adalah A, F, dan pohon keduanya itu adalah C, E, B, dan D.

Jadi ini merupakan contoh yang kita sebut sebagai hutan.

Ini adalah contoh hutan juga, jadi kita punya tiga pohon disini, kita lihat disini tidak ada lingkarannya,

berarti pohon disini tidak ada lingkarannya, ini pohon, tidak ada lingkarannya, ini pohon.

Jadi ini adalah hutan yang terdiri dari tiga komponen, karena bagian yang terhubung itu masing-masing kita sebut komponen.

Ini komponen pertama, ini komponen kedua, ini komponen ketiga.