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

Video ini membahas tentang keterhubungan dalam suatu graf, di mana graf terhubung didefinisikan melalui lintasan yang merupakan barisan busur-busur yang menghubungkan dua simbol tertentu. Lintasan tersebut dapat berupa sirkuit jika kembali ke simpul asal, dengan panjang minimal 1. Graf terhubung dapat direpresentasikan sebagai barisan simpul yang dilalui lintasan dari simpul awal ke simpul akhir. Konsep lintasan dan sirkuit ini penting dalam memahami keterhubungan pada teori graf.

Kali ini kita bahas tentang keterhubungan dalam suatu graf.

Jadi kalau graf itu kita gambar, maka kita akan dengan cepat bisa melihat apakah grafnya itu terhubung atau tidak.

Kecuali kalau grafnya itu punya simbol yang terlalu banyak ya.

Tapi kalau kita merepresentasikan graf itu dalam bentuk matriks, atau dalam bentuk adjacency list,

atau bentuk-bentuk yang lain, itu agak sulit melihatnya.

Jadi, kapan suatu graf itu disebut sebagai graf yang terhubung?

Untuk mendefinisikan graf terhubung, kita menggunakan satu bentuk dari graf yang kita sebut sebagai lintasan.

Lintasan itu bisa dikatakan merupakan barisan busur-busur yang melalui suatu simbol tertentu,

misalkan U, kemudian dia melalui beberapa simbol, dalam perjalanannya menuju ke simbol yang lain,

atau simbol yang dituju kita sebut misalnya V.

Jadi kalau kita punya N bilangan bulat positif dan G itu suatu graf yang tidak berarah dalam hal ini,

maka lintasan dengan panjang N dari simbol U ke simbol V di G itu merupakan barisan busur-busur,

misalnya kita sebut E1-EN dari G, sehingga akan terdapat barisan simpul yang kita mulai dari X0 sama dengan U,

kemudian X1, X2, X3, sampai XN, di mana XN sama dengan V,

sehingga busur EI itu menyatakan busur yang menghubungkan simpul XI-1 ke XI.

Jadi kalau di graf sederhana supaya tidak terlalu banyak rotasi yang kita gunakan,

kita akan meneruskan lintasan sebagai barisan simpul saja dari X0, X1, sampai XN.

Kalau kebetulan lintasan itu yang dimulai dengan U sama dengan X0 tadi dan V sama dengan XN,

ternyata U-nya sama dengan V, jadi dia kembali lagi ke simpul asal,

maka lintasan tadi kita sebut sebagai sirkuit dan panjangnya pasti lebih besar dari 0,

karena paling kecil itu adalah loop, loop itu panjangnya 1.

Lintasan yang melalui simpul-simpul X0, X1, dan XN-1 itu disebut menjalani busur-busur E1-EN,

jadi dari X0 dia akan melalui E1 kemudian sampai ke X1,

habis itu kita lanjut lagi dari X0 kita punya E1 menuju X1 kemudian lanjut lagi ke X2,

itu akan melalui busur E2 dan seterusnya sampai kita ketemu dengan XN.