Pelabelan 𝐿(2,1) pada Graf Lollipop 𝐿𝑚,𝑛

Abstract

Teori graf merupakan cabang ilmu matematika yang telah mengalami banyak perkembangan. Terdapat banyak topik yang dipelajari dalam teori graf, salah satunya adalah pelabelan graf. Secara umum, pelabelan graf membahas tentang pemberian label berupa bilangan bulat pada titik-titik graf, sisi-sisi graf, atau keduanya. Dalam perkembangannya, pelabelan graf ditambah dengan beberapa aturan yang berkaitan dengan jarak. Pelabelan graf dari pengembangan ini biasa disebut pelabelan 𝐿(ℎ,𝑘). Kemudian, beberapa peneliti melanjutkan pengembangannya yaitu pelabelan 𝐿(2,1) dimana setiap dua titik berjarak satu harus memiliki mutlak selisih label minimal dua dan setiap dua titik berjarak dua harus memiliki mutlak selisih label minimal satu. Dalam penelitian ini, penulis membahas pelabelan 𝐿(2,1) pada graf lollipop 𝐿𝑚,𝑛 dengan 𝑚≥3 dan 𝑛 bilangan bulat positif. Tujuan penelitian ini adalah menentukan nilai minimal span (mutlak selisih label terbesar dan terkecil) dari pelabelan 𝐿(2,1) pada graf lollipop 𝐿𝑚,𝑛 yang disimbolkan dengan 𝜆2,1(𝐿𝑚,𝑛), dan membangun program simulasi yang dapat digunakan untuk pelabelan hingga nilai 𝑚 dan 𝑛 yang sangat besar. Terdapat beberapa langkah utama yang dilakukan dlam penelitian ini yaitu pelabelan graf, membentuk fungsi dan teorema, serta membangun program dan dilanjutkan simulasi. Dalam membentuk teorema, langkah pertama yang dilakukan adalah melakukan penotasian titik pada graf. Kemudian dilanjutkan dengan pemberian label dan pendeteksian pola. Selanjutnya adalah membentuk fungsi pelabelan dan menyusun teorema berdasarkan pola yang diperoleh. Langkah terakhir adalah membuktikan teorema. Apabila teorema sudah terbukti, maka langkah selesai. Namun, jika teorema belum terbukti, maka mengulang kembali langkah pelabelan. Program simulasi yang dibangun dalam penelitian ini, dibuat dalam bentuk Graphical User Interface (GUI) sehingga mudah dioperasikan. ix Graf lollipop yang disimbolkan dengan 𝐿𝑚,𝑛 merupakan graf yang dibentuk dari penggabungan dua graf yaitu graf komplit (𝐾𝑚) dan graf lintasan (𝑃𝑛) dengan sebuah sisi penghubung (bridge). Graf lollipop diberi penotasian himpunan titik dan sisi sebagai berikut, 𝑉={𝑢𝑖 | 1≤𝑖≤𝑚}∪{𝑣𝑗 | 1≤𝑗≤𝑛} dan 𝐸={𝑢𝑖𝑢𝑘 | 1≤𝑖≤𝑚−1,𝑖+1≤𝑘≤𝑚}∪{𝑢1𝑣1}∪{𝑣𝑗𝑣𝑗+1 | 1≤𝑗≤𝑛−1}. Dari hasil pelabelan 𝐿(2,1) diketahui bahwa untuk sebarang graf lollipop (𝐿𝑚,𝑛) dengan 𝑚≥3 dan 𝑛 bilangan bulat positif, minimal span pada pelabelan 𝐿(2,1)=2𝑚−2. Fungsi pelabelan yang digunakan untuk memperoleh nilai span tersebut adalah 𝑓(𝑢𝑖)={2𝑚−2𝑖 | 1≤𝑖≤𝑚} dan 𝑓(𝑣𝑗)={1 | 𝑗=1}∪{3 | 𝑗=2}∪{2𝑎 | 3≤𝑗≤𝑛 dengan 𝑎 adalah sisa ketika 𝑗−3 dibagi 𝑚}. Berdasarkan hasil simulasi dari program yang didasarkan pada fungsi pelabelan, dapat diketahui bahwa mutlak selisih dari setiap dua titik berjarak satu adalah minimal dua dan mutlak selisih dari setiap dua titik berjarak dua adalah minimal satu. Selain itu, nilai span atau mutlak selisih dari label terbesar dan label terkecil pada hasil pelabelan merupakan nilai terkecil yang mungkin digunakan dalam pelabelan 𝐿(2,1) yaitu 𝜆2,1(𝐿𝑚,𝑛)=2𝑚−2. Nilai minimal span graf lollipop sama dengan nilai minimal span graf komplit