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

Video ini membahas keterhubungan graf berarah, di mana graf terhubung kuat jika terdapat lintasan dari simpul A ke B dan sebaliknya. Graf terhubung lemah terjadi jika hanya terdapat satu arah antara simpul A dan B. Konsep graf dasar juga dijelaskan sebagai graf berarah tanpa orientasi. Teorema matriks ketetanggaan digunakan untuk menghitung jumlah lintasan antar simpul dengan panjang tertentu dalam graf berarah. Contoh perhitungan lintasan dari matriks ketetanggaan hingga ke A pangkat 4 juga dijelaskan.

Kalau kasusnya grafnya berarah agak beda ceritanya karena kalau graf berarah itu kan busurnya ada arah-arahnya gitu ya.

Jadi kita akan bilang dia terhubung melihat arah sama tidak melihat arah.

Jadi di sini grafnya itu akan disebut terhubung kuat kalau ada lintasan dari simpul A ke simpul B dan juga dari simpul B ke simpul A.

Belum tentu lintasannya sama karena ada arahnya ya.

Jadi kita misalnya ada simpul A kemudian simpul B ini sembarang dua simpul di dalam graf tersebut

maka kita bisa mencari satu lintasan berarah jadi lintasannya dari A menuju B kemudian nanti dari B juga kita punya lintasan ke A.

Kalau dua-duanya ini ada maka kita sebut graf berarahnya itu terhubung kuat.

Kalau dia ternyata cuma ada satu arah saja entah dari A ke B atau B ke A maka dia bisa disebut terhubung lemah.

Bahkan terhubung lemah itu sebetulnya enggak perlu melihat lintasan arahnya kemana.

Tapi kalau kita lihat dari A ke B tadi kemudian kita punya arahnya kita buang semua berarti kan grafnya jadi tidak berarah ya.

Kalau graf tak berarah itu ada lintasan yang menghubungkan A ke B di sini maka kita sebut bahwa graf tersebut juga terhubung tapi terhubungnya terhubung lemah.

Jadi ada dua terhubung lemah ada yang paling gampang adalah melihat istilahnya graf dasar.

Jadi graf dasar itu adalah graf berarah tapi arahnya dibuang semua orientasinya dibuang semua.

Kita lihat apakah grafnya yang tak berarah tadi yang jadi graf dasar itu terhubung atau tidak.

Teoremanya mengatakan jadi kaitan tentang matriks ketetanggaan dengan grafnya dan dengan lintasannya.

Jadi kalau kita punya suatu graf G dengan matriks ketetanggaannya A yang kita urut baris dan kolomnya berdasarkan simpul V1 sampai Vn

maka kita bisa menghitung berapa banyak lintasan yang punya R simpul atau panjang R dari simpul VI ke VJ.

Itu bisa dilihat dari entry ke IJ dari A pangkat R.

Jadi secara lengkap teoremanya mengatakan misalkan G adalah graf dengan matriks ketetanggaan A dengan susunan mengikuti urutan V1, V2, Vn dari simpul-simpul di graf

banyaknya lintasan berbeda dengan panjang R dari VI ke VJ dengan R merupakan bilangan bolat positif sama dengan entry ke IJ dari A pangkat R.

Jadi kalau kita melihat hanya A maka yang terlihat hanya lintasan yang panjangnya 1.

Jadi ada busur atau nggak ada busur gitu kan ya.

Kalau kita menghitung A kwadrat nanti entry-nya menyatakan berapa banyak dari A ke B lintasan dengan panjang 2.

Kalau matriks ketetanggaan dari suatu graf itu adalah seperti ini 0 1 1 0, 1 0 0 1, 1 0 0 1, dan 0 1 1 0.

Kita lihat di sini hanya ada busur atau tidak.

Jadi ada lintasan dengan panjang 1 atau tidak.

Tapi kalau kita hitung jadi A pangkat 4 maka di sini kita akan lihat entry-entry-nya menunjukkan berapa banyak lintasan dengan panjang 4 dari satu simpul ke simpul yang lain.

Jadi misalnya di sini kan simpulnya A, B, C, D gitu ya.

Nah kita lihat di sini dari A ke D itu di sini terlihat nilainya adalah 8.

Itu artinya banyak lintasan dengan panjang 4 itu ada 8.

Nanti bisa dilihat dari gambarnya kamu hitung benar nggak sih ada 8.

Jadi tapi secara teori A pangkat R itu bisa menjelaskan tentang hal tersebut.