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

Video ini membahas konsep pohon dalam matematika diskrit dengan menjelaskan tentang graf terhubung. Graf lintasan, komponen graf, dan konsep terhubungnya graf dibahas untuk memahami apakah suatu graf merupakan pohon atau tidak. Dengan memperhatikan lintasan yang menghubungkan setiap pasang simpul dalam graf, kita dapat menentukan keterhubungan suatu graf. Melalui contoh kasus yang disajikan, penentuan keterhubungan graf dapat dilakukan dengan mudah atau sulit tergantung kompleksitas graf tersebut.

Oke, kali ini kita akan bicarakan jenis graf yang spesial ya, yang kita sebut sebagai pohon.

Tapi sebelum kita cerita tentang pohon, kita ulangi apa yang kita sebut sebagai graf lintasan.

Jadi graf lintasan itu adalah suatu graf, misalnya disini contohnya lintasan dengan 5 simpul, V1, V2, V3, V4, dan V5.

Dan busurnya itu hanya menghubungkan V1 ke V2, V2 ke V3, V3 ke V4, dan V4 ke V5.

Nah, kemudian yang berikutnya yang mungkin perlu kita ingat lagi, disini ada 2 graf, G1 dan G2.

Kita lihat kalau digambar bahwa G1 itu kan terhubung ya, sedangkan G2 itu terdiri dari 2 graf yang terpisah.

Biasanya bagian-bagian yang terpisah ini kita sebut komponen, jadi disini kita punya 2 komponen.

Nah, kalau digambar dan kebetulan banyaknya simpul itu sedikit, itu dengan mudah kita akan bilang,

oh ini graf G1 terhubung, graf G2 tak terhubung.

Tapi kalau misalnya grafnya itu sudah terlalu kompleks, misalnya tentang jaringan internet,

itu kan sudah banyak sekali simpul-simpulnya, sehingga agak sulit melihat apakah dia terhubung atau tidak.

Begitu juga kalau kita representasikan dalam bentuk matriks atau daftar ketetanggaan.

Nah, untuk menentukan apakah suatu graf itu terhubung, kita bisa pakai konsep bahwa

setiap pasang dari graf, setiap pasang simpul dari graf tersebut itu terhubung oleh lintasan.

Jadi, dalam akhir ini lintasannya itu subgrafnya.

Jadi, kalau misalnya di graf G1 itu saya punya U1, U2, U3, U4, U5,

U1 itu bertetangga dengan U2, U3, U4, dan U5, jadi tidak masalah.

Sekarang dari U2 ke U5 itu bisa terhubung tidak?

Tidak, itu bisa misalnya kita pakai lintasan U2, U1, sampai U5.

Jadi, setiap kita ambil sembarang dua simpul itu pasti ada lintasan yang menghubungkan.

Nah, kalau yang G2 itu tidak bisa kita lakukan hal yang sama,

karena misalnya kalau yang graf komponen pertama itu ini saya kasih nama U1, U2, U3 simpulnya,

kemudian yang berikutnya V1, V2, V3, V4, V5, V6,

yang bagian U itu bisa kita cari lintasannya, yang bagian V itu bisa kita cari lintasannya,

tapi kita tidak bisa mencari lintasan misalnya dari U3 ke V4.

Jadi, di sini karena tidak bisa ada lintasan maka kita katakan grafnya tidak terhubung.

Review Graf Terhubung

DEKSRIPSI

PENGAJAR

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

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

DEKSRIPSI

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

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