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

Video ini membahas keterhubungan graf tidak berarah, di mana lintasan menghubungkan dua simpul dalam graf. Konsep Six Degree Separation dan Erdos Number digunakan untuk mengukur seberapa dekat hubungan antara individu dalam kolaborasi. Erdos Number menggambarkan jarak hubungan dengan matematikawan terkenal, Erdos, melalui kolaborasi penulisan paper. Konsep serupa juga digunakan dalam Bacon Number untuk mengukur seberapa dekat hubungan dalam film. Graf dikatakan terhubung jika setiap pasang simpul memiliki lintasan yang menghubungkan keduanya, jika tidak, graf tersebut disebut tak terhubung. Penjelasan ini memberikan gambaran tentang keterhubungan dalam graf tidak berarah dengan contoh visual graf terhubung dan tak terhubung.

Sekarang kalau kita melihat lintasan lagi dengan panjang N dari simpul U ke simpul V di G,

tadi kan sudah dijelaskan bahwa dia adalah barisan busur E1 sampai EN,

di mana si E1 itu berasosiasi dengan X0 X1, E2 berasosiasi dengan X1 X2,

dan EN berasosiasi dengan Xn-1 Xn di mana si X0 itu adalah simpul U dan Xn itu simpul V.

Kalau kita lihat di sini contoh yang kedua itu lintasan dari graf perkenalan,

jadi itu menunjukkan siapa kenal dengan siapa.

Lintasan itu akan menghubungkan dua orang antara si A dengan si B misalnya,

itu kalau ada lintasan yang menghubungkan kedua orang ini

dengan dua orang bertetangga dalam rantai jika mereka mengenali satu dengan yang lain.

Jadi misalnya kalau kita lihat si A dan si B itu ada lintasan salah satunya itu menggunakan lintasan yang ini,

artinya di sini dari A ke B itu bisa terhubung meskipun tidak langsung,

kalau kena langsung kan artinya cuma ada satu busur yang menghubungkan keduanya,

tapi dia bisa mencapai atau memberikan informasi ke B.

Konsep ini mungkin agak kurang mengikuti zaman karena sekarang komunikasi kan melalui mesos

dan mesos itu tidak melihat dalam bentuk perkenalan yang seperti ini,

tapi kan bisa di blasting kalau kita mau memberikan informasi dari A ke B gitu misalnya,

jadi bisa lewat grup WhatsApp, bisa lewat Facebook, bisa lihat LINE atau apapun Instagram dan seterusnya

yang bisa dibaca dengan orang yang kita tidak kenal langsung.

Nah salah satu film itu judulnya Six Degree Separation itu dibuat berdasarkan ide ini,

jadi dulu ada suatu percobaan orang mengirimkan surat,

waktu itu masih zaman surat, jadi dari si A ke si B yang dia tidak kenal,

ini tapi di Amerika ya, jadi si A ini bertugas untuk mengirimkan suratnya pada seseorang yang dia kenal,

yang dia pikir bisa ada komunikasi yang menuju ke si B,

dan ternyata dari beberapa orang yang sudah dicoba,

itu ada enam kali si surat itu dikirim agar mencapai si orang yang dituju,

makanya di situ pakai namanya Six Degree Separation.

Nah kalau di kalangan matematika diskret gitu,

ada matematikawan yang sangat terkenal yang disebut sebagai Erdos,

kalau kita melihat graf kolaborasi, graf kolaborasi itu menentukan apakah si A itu pernah membuat artikel bersama dengan si B,

kalau iya berarti ada busur yang menghubungkan mereka berdua,

nah kaitan dengan Pak Erdos itu disebut sebagai Erdos Number,

Erdos Number ini adalah menjelaskan berapa jauh hubungan kita dengan Pak Erdos terkait dalam pembuatan paper,

jadi misalnya dari A ke B itu kita lihat ada kolaborasi berarti dia ada busur,

Pak Erdos sendiri punya Erdos Number 0 karena dia yang mulai,

kemudian orang yang pernah bikin paper bersama Pak Erdos itu punya Erdos Number 1,

dan yang berikutnya lagi kalau orang pernah bikin paper dari orang-orang yang tadi,

jadi sekarang kita lihat misalnya saya sendiri,

saya punya paper bersama supervisor saya namanya Bu Mirka Miller itu di tahun 2008,

Bu Mirka Miller itu punya paper bersama dengan Pak Alexander Rosa di tahun 2002,

Pak Alexander Rosa punya paper dengan Pak Erdos,

jadi Pak Alexander Rosa itu punya Erdos Number 1,

jadi itu gaya-gayaan di dunia kombinatorik,

seberapa dekat sih kita dengan Pak Erdos.

jadi di zaman dulu ini ada artis terkenal namanya Kevin Bacon,

tapi seberapa jauh dia pernah bikin film bersama,

kemudian orang-orang yang pernah main film bareng Bacon ini,

jadi kamu bisa ganti dengan bintang film yang terkenal sekarang,

itu yang pernah main dengan beliau itu 2.367 orang,

kemudian orang yang pernah main film bersama si 2.367 itu,

ada 242.000 lebih yang punya Bacon Number 2,

untuk melihat bagaimana lintasan itu bisa kita gunakan.

Jadi kembali kepada keterhubungan dalam graf,

kalau kita bisa mendapatkan lintasan antara setiap pasang simpul,

harus ada lintasan yang menghubungkan dua graf tersebut,

kalau kita bisa mendapatkan dua simpul yang tidak bisa dibuat lintasannya,

maka graf tersebut disebut sebagai graf terhubung,

kalau enggak punya lintasan berarti dia grafnya tak terhubung.

tadi saya sudah mengatakan bahwa kalau digambar itu gampang lihatnya,

karena kalau kita ambil sembarang pasang simpul di sini,

kita pasti bisa mendapatkan suatu lintasan,

kita tidak bisa mendapatkan lintasan yang menghubungkan dia,

jadi melihat lintasan itu adalah secara teorinya,

kalau digambar kita bisa lihat dari gambarnya langsung.

kalau antara dua simpul selalu terdapat lintasan yang menghubungkan kedua simpul tersebut,