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

Video ini membahas tentang konsep komplement dari graf, di mana simpul-simpulnya sama dengan graf aslinya namun hubungan antar simpul berbeda. Selain itu, juga dijelaskan tentang graf n-cube yang merupakan graf hypercube berdimensi n, di mana simpulnya merepresentasikan string biner panjang n. Hubungan antar simpul dalam graf n-cube terjadi jika kedua string hanya berbeda di satu posisi bit. Contoh penerapan konsep ini disajikan untuk n=2 dan n=3.

Ini ada jenis graf yang mungkin tidak tepat sebagai jenis graf ya,

tapi suatu graf yang kita bisa dapat dari graf yang sudah ada,

yang kita sebut sebagai komplement dari graf.

Jadi komplement dari graf G itu notasinya adalah biasanya G pakai tanda baris di atasnya,

itu himpunan simpulnya sama dengan G, jadi VG juga,

tapi kalau 2 simpul itu bertetangga di komplement,

maka di komplementnya nanti tidak akan jadi 2 simpul yang bertetangga.

Jadi misalnya kita punya G dengan 6 simpul seperti ini,

saya kasih nama dulu V1, V2, V3, V4, V5, dan V6,

maka G komplementnya ini juga akan punya simpul V1, V2, V3, V4, V5, dan V6.

jadi kalau di G itu kita punya busur V1, V2,

maka nanti di komplementnya itu antara V1, V2 itu tidak ada busurnya di sini,

Kalau kita lihat dari V1 ke V5 di grafnya itu,

di sini kan tidak ada busur, artinya dia tidak bertetangga.

Di komplementnya itu nanti akan kita berikan busur,

jadi komplement itu terkait sama busurnya.

Dan graf yang sering muncul kalau di komputasi itu adalah graf n-cube,

jadi graf hypercube berdimensi n atau disebut notasinya itu key n,

itu graf yang simpulnya itu merepresentasikan 2 pangkat n string yang panjangnya n,

jadi 2 simpul itu bertetangga jika dan hanya jika,

kedua string dari simpul tersebut hanya berbeda di satu posisi bit saja.

maka stringnya itu kan kita punya 0 0 0 1 1 0 dan 1 1 yang panjangnya 2.

Ini direpresentasikan sebagai titik-titik jadi simpul-simpul,

masing-masing merepresentasikan di sini ada 0 0 0 1 kemudian 1 0 dan 1 1.

2 simpul ini akan mempunyai busur yang menghubungkan mereka atau bertetangga,

kalau stringnya itu hanya berbeda satu posisi,

berarti kita punya busur yang menghubungkan mereka.

kita lihat di situ 0 1 dengan 1 0 itu tidak punya busur karena dia berbeda di dua posisi,

jadi kita bisa menambahkan busur karena mereka bertetangga,

0 0 sama 1 1 tidak ada karena bedanya di dua posisi,

begitu juga 0 0 dengan 1 0 juga bertetangga karena bedanya ada di posisi satu.

Kalau dibentuk dalam lingkaran jadinya adalah seperti gambar yang key 2.

berarti kita punya 0 0 0 0 0 1 dan seterusnya ada 8,

berarti graf nya bentuknya adalah seperti ini.