Pelabelan Ajaib Jarak Graf (Distance Magic Labelling)

Hai hai semua ^_^ Aye Admin K. Di postingan ini aye bakal ngebahas tentang salah satu jenis pelabelan dalam teori graf. Jadi, sebelum membaca postingan ini, aye sarankan untuk mempelajari terlebih dahulu dasar-dasar teori graf dan pengertian pelabelan. Baiklah, langsung aja kita cekidoot.

Oke, mungkin kalian belum tahu apa itu pelabelan graf dan mager buat mempelajarinya di buku atau di situs web lain. Sesuai namanya, pelabelan itu adalah pemberian label pada sesuatu. Nah, pada graf itu sendiri ada dua hal yang bisa kita labeli yakni titik dan sisi. Label pun bisa bermacam-macam, bisa bilangan, bisa warna, bisa nama, dan lain-lain. Namun, karena banyak titik dan sisi pada graf adalah berhingga, maka kita bisa menyempitkan pengertian pelabelan dengan hanya melabeli bilangan asli. Adapun, untuk warna, nama, kelompok dan lain-lain bisa kita wakili dengan bilangan asli. Aturan pelabelan pun tergantung selera masing-masing atau sesuai kebutuhan.

Nah, definisi formalnya seperti ini.

Definisi Pelabelan

Misalklan G = (V, E) adalah graf. Suatu fungsi f yang memetakan himpunan titik V(G) ke suatu subhimpunan dari himpunan bilangan asli ℕ disebut sebagai pelabelan titik pada graf G. Sedangkan, fungsi g yang memetakan himpunan sisi E(G) ke suatu subhimpunan dari himpunan bilangan asli ℕ disebut sebagai pelabelan sisi graf G. Adapun, apabila dikombinasikan, yakni menjadi suatu fungsi h yang memetakan dari himpunan gabungan V(G)∪E(G) ke suatu subhimpunan dari himpunan bilangan ℕ, maka fungsi h disebut sebagai pelabelan campuran.

Terdapat berbagai macam jenis pelabelan. Setiap jenis pelabelan mempunyai aturannya masing-masing. Nah, di postingan kali ini aye akan membahas aturan pelabelan yang bernama pelabelan ajaib jarak. Namun, sebelum itu, aye akan memberikan contoh pelabelan jenis lain yakni yang disebut "pewarnaan graf" atau "graph coloring".

Pewarnaan Titik

Suatu pelabelan titik disebut pewarnaan titik apabila jika terdapat 2 titik yang saling bertetangga maka kedua titik tersebut diwarnai (dilabeli) dengan warna (bilangan) yang berbeda. Sebagai contoh, kita akan mewarnai/melabeli graf berikut dengan suatu pewarnaan/pelabelan.

Untuk mewarnai graf ini, kita bisa mewaliki warna dengan bilangan-bilangan, misalnya saja 1 mewakili warna merah, 2 mewakili warna kuning, 3 mewakili warna hijau, dan 4 mewakili warna biru, sehingga menjadi pelangi-pelangi ciptaan tuhan 😆. Kita bisa dengan mudah mewarnai titik-titik di graf tersebut dengan syarat dua titik yang terhubung oleh sisi mempunyai warna yang berbeda. Ini adalah pekerjaan yang sangat mudah bahkan anak TK pun bisa melakukannya. Ayo kita coba warnai.

Pertama-tama, aye akan mewarnai titik A. Kita bisa memilih warna apa saja. Misal kita pilih warna kuning.

Okey, ini baru langkah awal. Sebenarnya kita tidak harus mulai dari A dulu, kita bisa saja mulai dari B, C, H, O, atau yang lainnya. Ini bebas. Namun, di postingan ini, aye memilih untuk konsisten mulai dari A, B, C, dst menurut urutan abjad. Berarti, selanjutnya, aye bakal ngewarnai B lalu C. Misal kita warnain B kuning dan C hijau.

Sampai saat ini belum ada masalah. Selanjutnya, kita mau ngewarnain titik D. Perhatikan bahwa titik D bertetangga dengan titik A. Karena titik A berwarna kuning maka titik D tidak boleh berwarna kuning. Kita bisa memilih warna lain, misal warna hijau.

Hal yang serupa juga terjadi pada titik E dan F. Karena E bertetangga dengan B maka E tidak boleh berwarna kuning. F juga tidak boleh berwarna hijau karena bertetanggaan dengan C dan D, tapi masih bisa warna lain. Gimana kalau kita warnain E hijau dan F kuning? Ini ide yang bagus sebab E dan F juga saling bertetangga sehingga warnanya harus berbeda.

Selanjutnya G tidak boleh hijau dan H tidak boleh kuning. Kita warnai saja G dengan kuning lagi. Mungkin kalian bosan kalau warnanya hanya hijau dan kuning mulu, kita warnai saja H dengan merah.

Lakukan terus sampai selesai. Nanti ada banyak pewarnaan yang mungkin tergantung selera kalian mau warnain gimana, contohnya saja seperti ini:

atau yang ini:

dan masih banyak lagi. Bahkan, kalau dimulai lagi dari awal, kita bisa membuat cara pewarnaan lain yang benar-benar berbeda.

Kalau kita perhatikan, kita bisa mewarnai titik-titik di graf tersebut dengan hanya menggunakan 4 warna saja. Sebenarnya kita bisa menggunakan berapapun warna yang kita inginkan dan semuanya sah/valid selama tidak ada titik yang saling bertetangga mempunyai warna yang sama. Bahkan, kita bisa menggunakan 17 warna untuk membuat semua titik pada graf di atas punya warna berbeda-beda. Namun, tentu saja akan lebih menarik kalau kita mencari banyak warna minimal yang dibutuhkan. Pada graf di atas, butuh lebih dari 1 warna, sebab ya kalau hanya 1 warna jelas gak bisa. Apakah 2 warna saja cukup? Perhatikan bahwa terdapat 3 titik yang membentuk graf lengkap yakni K, L, dan N. Ketiga titik tersebut bertetangga satu sama lain sehingga warnanya harus berbeda. Jadi, setidaknya kita butuh 3 warna atau lebih. Apakah cukup hanya dengan 3 warna? Well, silakan dicari tau sendiri sebagai PR yah, hehe.

Sebenarnya ada juga yang namanya pewarnaan sisi tapi aye gak bakal bahas di postingan ini karena bakalan tambah panjang. Setidaknya kalian bisa tahu contoh salah satu jenis pelabelan yang lain selain yang bakal aye bahas disini. Oh yah, mungkin kalian heran kok pakai warna yah bukan pakai bilangan? Well, disini warna bisa diwakili dengan bilangan, dengan kata lain pewarnaan disini artinya kita memberi label angka/bilangan sehingga titik yang saling bertetangga tidak mempunyai label bilangan yang sama. Jadi, semua warna di atas bisa kalian ganti dengan bilangan selama setiap warna yang berbeda diwakili oleh bilangan yang berbeda.

Pelabelan ajaib jarak

Oke, kalian sudah mengenal salah satu jenis pelabelan yakni pewarnaan titik. Pewarnaan titik mengharuskan kita memberikan label bilangan pada titik-titik sehingga setiap 2 titik yang bertetangga tidak mempunyai bilangan atau warna yang sama. Sebenarnya ada banyak sekali jenis aturan pelabelan selain pewarnaan bahkan kita bisa membuat sendiri aturan pelabelan yang menarik. Nah, disini kita akan membahas tentang aturan pelabelan yang benar-benar berbeda dan tidak bisa diilustrasikan dengan warna sebab kita butuh melihat bilangannya. Pelabelan ini bernama pelabelan ajaib jarak atau distance magic labelling.

Misalkan $G=(V,E)$ adalah graf dengan orde $n$ . Suatu fungsi bijektif $f:V\rightarrow \left \{ 1,2,3,...,n \right \}$ disebut suatu pelabelan ajaib jarak dari $G$ apabila terdapat suatu bilangan bulat positif $k$ sehingga $\sum_{u \in N(v)}^{} f(u) = k$ untuk setiap $v \in V$ , dengan $N(v)$ adalah ketetanggaan buka dari $v$ . Konstanta $k$ disebut konstanta ajaib dari pelabelan $f$ . Setiap graf yang memiliki suatu pelabelan ajaib jarak disebut graf ajaib jarak.

Catatan:

Orde dari suatu graf adalah banyaknya titik pada graf tersebut. Jadi, orde dari graf $G=(V,E)$ adalah $|V|=n \in \mathbb{N}$ .
Ketetanggaan buka dari suatu titik pada suatu graf adalah himpunan semua titik yang bertetangga dengannya. Jadi, ketetanggaan buka dari titik $v$ pada graf $G=(V,E)$ adalah $N(v)=\left \{ u \in V: uv \in E \right \}$ . Ada juga yang namanya ketetanggaan tutup dari suatu titik yang sama seperti ketetanggan buka yakni memuat semua titik tetanggannya. Akan tetapi, yang berbeda adalah ketetanggaan tutup juga memuat titik tersebut. Jadi, ketetanggaan tutup dari suatu titik ${\color{Purple} v}$ pada graf ${\color{Purple} G=(V,E)}$ adalah ${\color{Purple} N(v)\cup \left \{ v \right \}=\left \{ u \in V: uv \in E \right \} \cup \left \{ v \right \}}$ . Di definisi yang di atas, kita menggunakan ketetanggaan buka bukan ketetanggaan tutup.

Oke, itulah definisi dari pelabelan ajaib jarak. Tampak jelas bahwa pelabelan ajaib jarak adalah pelabelan titik sebab domainnya adalah himpunan titik. Perhatikan pula bahwa pelabelan ajaib jarak memetakan ke himpunan bilangan asli dari 1 sampai $n$ dengan $n$ adalah orde dari graf secara bijektif. Ini berarti bahwa setiap titik dilabeli dengan bilangan yang berbeda dan semua bilangan harus terlabeli pada suatu titik.

Misalkan graf $G=(V,E)$ dilabeli dengan pelabelan ajaib jarak $f$ . Lalu kita ambil sebarang titik berbeda $v_1$ dan $v_2$ di $V$ . Kita peroleh secara berturut-turut ketetanggaan buka dari $v_1$ dan $v_2$ adalah $N(v_1)$ dan $N(v_2)$ . Berdasarkan definisi, maka haruslah $\sum_{u\in N(v_1)}^{} f(u) = \sum_{u\in N(v_2)}^{} f(u) = k$ untuk suatu bilangan asli $k$ , ini artinya jumlahan dari setiap label tetangga(-tetangga) dari $v_1$ harus sama dengan jumlahan dari setiap label tetangga(-tetangga) dari $v_2$ . Mengingat ini berlaku untuk setiap titik, maka pelabelan ajaib jarak mempunyai maksud bahwa jumlahan dari label-label tetangga dari setiap titik itu konstan/tetap dan sama dengan suatu bilangan asli $k$ .

Perhatikan bahwa terdapat definisi dari "graf ajaib jarak" yakni graf yang dapat dilabeli dengan pelabelan ajaib jarak. Ini seolah-oleh menyiratkan bahwa bisa jadi suatu graf tidak dapat dilabeli dengan aturan pelabelan ajaib jarak ini dan faktanya memang iya, ada graf demikian. Contoh sederhananya adalah graf $K_2\cong P_2$ yakni graf yang terdiri dari 2 titik dan 1 sisi. Apabila dilabeli maka pasti salah satu titik dilabeli dengan bilangan 1 dan titik lain dilabeli dengan bilangan 2. Misalkan titik-titiknya adalah $v_1$ dan $v_2$ . Jika kita labeli $v_1$ dengan 1 maka kita harus labeli $v_2$ dengan 2. Namun perhatikan bahwaa anggota dari ketetanggaan buka $N(v_1)$ hanyalah $v_2$ , sedangkan anggota dari $N(v_2)$ hanyalah $v_1$ . Jika dijumlahkan semua label anggota di $N(v_1)$ hasilnya adalah 2 sebab anggotanya hanya $v_2$ . Sedangkan, jumlah semua label anggota di $N(v_2)$ adalah 1. Itu artinya pelabelan ini tidak memenuhi definisi pelabelan ajaib jarak. Dengan demikian, graf $K_2\cong P_2$ bukan graf ajaib jarak.

Okey, kita sudah tunjukkan bahwa $K_2\cong P_2$ bukan graf ajaib jarak. Yang menjadi pertanyaan selanjutnya, apakah memang ada yang namanya graf ajaib jarak? Apakah ada graf yang dapat dilabeli dengan pelabelan ajaib jarak? Jawabannya adalah ada. Contohnya adalah graf siklus $C_4$ yang pelabelannya bisa kalian lihat di gambar berikut.

Disini ada 4 buah titik yakni titik merah, biru, kuning, dan hijau. Keempat titik ini dilabeli dengan bilangan asli dari 1 sampai 4 sehingga memenuhi pelabelan ajaib jarak dengan konstanta ajaib $k=5$ . Perhatikan ketetanggaan buka setiap titik, misal titik merah punya ketetanggaan buka {biru, hijau} yang mempunyai jumlahan label setiap titiknya adalah 4 + 1 = 5. Begitupun ketetanggaan buka dari hijau yakni {merah, kuning} mempunyai jumlahan label 2 + 3 = 5. Hal yang sama juga berlaku untuk ketetanggan buka titik biru dan kuning. Dengan demikian $C_4$ adalah graf ajaib jarak karena dapat dilabeli dengan pelabelan ajaib jarak.

Contoh graf lain yang dilabeli dengan pelabelan ajaib jarak adalah graf tripartit $K_{3,3,3}$ yang bisa kalian lihat pada gambar berikut.

Graf ini mempunyai konstanta ajaib $k=30$ . Contohnya saja coba perhatikan ketetanggaan buka dari titik yang dilabeli 9, jumlahan labelnya adalah 7 + 6 + 2 + 3 + 4 + 8 = 30.

Dengan demikian, graf $K_{3,3,3}$ ini juga merupakan graf ajaib jarak.

Nah, seperti itulah pelabelan ajaib jarak pada graf dimana tidak semua graf bisa dilabeli demikian. Mungkin kalian tahu graf lain yang bisa dilabeli atau tidak bisa dilabeli? Coba kasih di komentar yah. Oh yah, selain pelabelan ini, masih ada banyak pelabelan graf yang lain bisa kalian cari di buku-buu, internet, bahkan bisa kalian buat sendiri. Baik, cukup sekian postingan aye yang lumayan panjang ini. Sampai jumpa di postingan selanjutnya. Bye~