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

Video ini membahas tentang konsep Cut Vertex, Cut Edge, Vertex Connectivity, dan Keterhubungan Busur dalam Teori Graf. Cut Vertex adalah simpul yang jika dihilangkan akan membuat graf menjadi tak terhubung, sedangkan Cut Edge adalah busur yang jika dihilangkan akan memisahkan graf menjadi dua bagian tak terhubung. Graf dapat memiliki cut vertex, cut edge, atau keduanya, atau bahkan tidak sama sekali. Graf lengkap seperti K5 memiliki keterhubungan yang erat, di mana harus menghilangkan n-1 simpul untuk membuatnya tak terhubung. Konsep Vertex Connectivity (kappa G) dan Busur Connectivity (lambda G) saling terkait, di mana lambda G selalu lebih besar atau sama dengan kappa G, dan lambda G lebih kecil atau sama dengan derajat minimum dari simpul-simpulnya.

Kalau grafnya itu tidak terhubung, maka kita bisa lihat misalnya pada contoh ini

ada beberapa graf yang terpisah yang kita sebut sebagai komponen terhubung.

Jadi komponen terhubung dari suatu graf itu adalah subgraf terhubung dari G

yang tidak termuat pada subgraf yang lain.

Jadi di sini komponen terhubung adalah subgraf terhubung yang maksimal.

Kalau dia dalam suatu graf itu mempunyai lebih dari satu komponen terhubung

dan gabungannya itu adalah graf G, maka graf G itu akan disebut sebagai graf tak terhubung.

Jadi di sini graf H punya tiga komponen terhubung yaitu H1, H2, dan H3.

Di dalam melihat suatu graf itu ada simpul atau busur yang memegang peranan penting

terutama terkait dengan misalnya hubungan komunikasi dari satu tempat ke tempat yang lain.

Kalau ada satu simpul atau satu busur yang mengalami suatu kerusakan,

Simpulnya itu kita sebut sebagai cut vertex dan busurnya tadi disebut cut edge.

tentunya kalau menghilangkan satu simpul itu busur-busur yang hadir di sekitarnya itu juga ikut hilang,

sehingga graf tersebut menjadi tak terhubung.

Simpul ini yang kita sebut sebagai cut vertex.

Kalau busur yang hilang maka membuat dia jadi tidak terhubung itu kita sebut sebagai cut edge

atau seringkali kita sebut sebagai bridge atau jembatan.

Jadi itu kalau misalnya ada dua daerah jembatannya rusak artinya kan dari dua daerah itu jadi tidak terhubung.

Kita lihat contohnya misalnya pada graf ini, untuk graf yang pertama kita lihat

kalau kita lihat simpul D kemudian mau kita hilangkan,

maka yang terisolasi atau yang hilang itu cuma D,

tapi yang lain masih aman, masih bisa berhubungan satu dengan yang lain.

maka begitu ini hilang graf tersebut akan terbagi menjadi dua yang tak terhubung,

ada dua komponen yang tak terhubung sehingga itu kita sebut sebagai cut vertex.

Ternyata tidak karena kita punya juga simpul E di sini, ini juga cut vertex.

Simpul B juga cut vertex, simpul-simpul yang lain itu aman.

Jadi kalau ada masalah itu tidak mengakibatkan komunikasi menjadi tak terhubung.

Kalau di gambar yang pertama ini, cut edge itu adalah busur yang kalau dia hilang mengakibatkan dia jadi tak terhubung,

kalau CE itu bermasalah maka dia akan terpisah menjadi dua yang tidak terhubung.

jadi kalau AB ini ada masalah maka si A menjadi terisolasi.

Kita lihat juga untuk contoh yang lain, misalnya contoh yang paling jelas itu adalah G2.

G2 itu punya satu simpul yang menjadi cut vertex yaitu si C,

karena kalau C itu bermasalah maka ada dua bagian yang menjadi tak terhubung.

jadi di sini kita lihat di dalam gambarnya itu tidak ada yang serupa jembatan,

jadi dia tidak punya cut edge dalam hal ini.

Berikutnya lagi kalau kita lihat yang G3, G4 dan G5 itu tidak punya cut vertex,

jadi simpul manapun yang diambil masih aman, masih bisa terhubung.

karena busur yang manapun bermasalah si komunikasi masih bisa lewat jalur yang lain.

Jadi yang ketiga graf ini aman, tidak punya cut vertex, tidak punya cut edge.

Kalau kita misalnya sudah lihat di contoh-contoh yang tadi,

itu ada graf yang punya cut vertex, ada yang punya cut edge, ada yang punya dua-duanya,

dan juga banyak yang tidak punya cut vertex sama sekali.

Kalau yang tidak punya cut vertex itu kita sebut sebagai non-separable graph,

jadi dia tidak bisa dipisahkan hanya dengan menghilangkan satu simpul atau satu busur saja.

Tapi seringkali kita bisa melihat bukan cuma satu simpul,

tapi bisa membuat suatu graf itu menjadi tak terhubung dengan mengambil beberapa simpul.

Jadi kita kembali lihat contoh yang sebelumnya,

jadi misalnya kita lihat contoh yang G3, kita tidak punya cut vertex di sini,

tapi kalau kita mengambil dua simpul, misalnya di sini saya ambil yang C dan F,

Begitu juga pasangan-pasangan yang lain, ada beberapa yang bisa kita lihat di situ.

Jadi yang menjadi cut di sini atau yang menjadikan dia tak terhubung

itu bukan hanya satu simpul, tapi himpunan.

Jadi himpunan vertex dengan beberapa simpul,

kalau di dalam contoh kita tadi dua, ada juga yang tiga dan seterusnya.

Kalau kita punya himpunan yang bisa membuat graf itu tak terhubung,

kita bisa menghitung vertex connectivity-nya, jadi keterhubungan simpulnya.

Di sini notasinya adalah kappa G, itu adalah banyak minimum simpul dari vertex cut-nya.

Jadi kalau misalnya contoh yang tadi dua saja kita sudah cukup untuk membuat dia menjadi tak terhubung,

kalau kita ambil tiga ya sudah pasti hasilnya akan lebih jelas.

Tapi yang kita butuhkan adalah berapa banyak simpul yang minimal,

yang kalau dia bermasalah mengakibatkan si grafnya itu komunikasinya menjadi tidak jalan atau menjadi tidak terhubung.

Kalau kita lihat graf yang spesial yaitu graf lengkap, misalnya saya ambil di sini contohnya adalah K5.

K5 itu berarti dia punya lima simpul dan setiap pasang simpulnya itu terhubung.

Kita kalau mau menghilangkan simpul menjadi tidak terhubung, itu harus menghilangkan sebanyak n-1.

Dalam hal ini ada empat simpul yang kita mesti buang untuk dia menjadi tak terhubung.

Jadi di sini dibuang sehingga dia menjadi terisolasi, ada satu simpul yang terisolasi.

Jadi complete graf atau graf lengkap ini sangat erat dalam artian keterhubungannya.

Jadi berapapun yang bermasalah dia tetap bisa terhubung, kecuali kalau n-1 tadi.

Jadi kappa dari KN itu adalah n-1, jadi banyaknya simpul yang harus dihilangkan.

Keterkaitan dengan busur juga sama, kalau tadi ada jembatan berarti satu busur saja bermasalah dia akan menjadi tak terhubung.

Tapi kita juga bisa melihat ada berapa busur minimal sih yang membuat dia menjadi tak terhubung.

Notasinya itu keterhubungan busur adalah lambda G.

Kalau lambda G itu 0, itu artinya dia minima busur yang menjadi edge cut itu tidak ada.

Kalau dia simpulnya tunggal berarti dia tidak ada busur yang bisa dihilangkan, itu lambda G sama dengan 0.

Kalau dia punya n simpul maka si lambda G itu adalah dari 0 sampai n-1.

Jadi bisa 0 tadi kalau dia merupakan simpul terisolasi atau bisa kita cari sampai jumlahnya adalah n-1.

Antara tadi si kappa sama si lambda itu ternyata ada hubungannya.

Jadi kalau misalnya grafnya lengkap, tadi untuk kappanya kita harus menghilangkan n-1 simpul tadi dari contoh yang kalima.

Sehingga disini secara umum berlaku bahwa kappa itu selalu lebih kecil sama dengan lambda G

dan lambda G itu lebih kecil atau sama dengan minimum degree dari V.

Jadi kalau kita punya V disini, kemudian disini ada tetangga-tetangganya, tetangganya itu U1, U2, U3, U4 misalnya.

Maka untuk membuat dia menjadi tak terhubung, kita paling tidak harus menghilangkan semua busur yang ini.

Dan kalau ini adalah degree minimum atau banyak busur yang terhubung pada suatu simpul,

berarti si lambda G itu paling banyak adalah menghilangkan semuanya ini.

Tapi bisa saja dia tidak harus menghilangkan semua sebanyak minimum degree-nya, tapi bisa lebih sedikit lagi.