Pewarnaan Titik Antiajaib Lokal Pada Graf Sapu dan Keterkaitannya dengan Keterampilan Berpikir Tingkat Tinggi

Abstract

Teori graf diperkenalkan oleh Leonhard Euler, matematikawan asal Swiss pada tahun 1736. Idenya muncul sebagai upaya dalam menyelasaikan masalah jembatan Konisberg menggunakan teori graf. Salah satu topik yang menjadi kajian menarik dalam teori graf adalah Local Antimagic Vertex Coloring (LAVC) yaitu pewarnaan titik antiajaib lokal. Topik ini mengaitkan konsep pewarnaan dengan pelabelan yaitu pelabelan antiajaib yang dikembangkan menjadi pelabelan antiajaib lokal. Sebuah graf G = (V,E) dengan banyaknya titik order atau |V| = p dan banyaknya sisi size atau |E| = q mempunyai titik-titik yang tidak terisolasi. Pemetaan bijektif f : E → {1,2,3,....,|E|} dikaatakan pelabelan antiajaib lokal jika untuk setiap dua titik yang bertetangga yaitu u dan v, uv ∈E dengan w(u) 6= w(v) dimana w(u) = Pe∈E(u) f(uv) dan E(u) adalah bagian dari sisi yang bersisihan dengan u. Bobot (warna) titik yang dihasilkan disebut bilangan kromatik antiajaib lokal χla(G) yaitu banyaknya warna minimum dari semuapewarnaangrafGdenganpelabelanantiajaiblokaldarigraf G. Selanjutnya LAVC ini dikembangkan menjadi LATVC yaitu Local Antimagic Total Vertex Coloring. Sebuah graf G = (V,E) dengan banyaknya titik order atau |V| = p dan banyaknya sisi size atau |E|= q mempunyai titik-titik yang tidak terisolasi. Pemetaan bijektif f : V∪E →{1,2,...,p+q}dikaatakan pelabelan total antiajaib lokal jika untuk setiap dua titik yang bertetangga yaitu u dan v, uv ∈E dengan w(u) 6= w(v) dimana w(u) =Pe∈E(u) f(uv) + f(v). dan E(u) adalah bagian dari sisi yang bersisihan dengan u. Bobot (warna) titik yang dihasilkan disebut bilangan kromatik total antiajaib lokal χlat(G) yaitu banyaknya warna minimum dari semua pewarnaan graf G dengan pelabelan total antiajaib lokal dari graf G. Pada penelitian ini menggunakan graf sapu yaitu graf sapu tunggal (Broom Graph) Bn,d dan graf sapu ganda (Double Broom Graph) DBn,d. Graf sapu tunggal Broom Graph Bn,d adalah sebuah graf dengan n titik, yang memuat graf lintasan P dengan d titik dan (n−d) titik anting-anting atau bandul yang semuanya bertetangga dengan salah satu titik ujung dari graf lintasan P, pada penelitian ini dibatasi untuk d≥3 dan n−d≥2. Graf sapu ganda (Double Broom Graph) DBn,d adalah sebuah graf dengan n titik yang memuat graf lintasan P dengan d titik dan n−d 2 titik anting-anting atau bandul yang semuanya bertetangga dengan salah satu titik ujung dari graf lintasan P, pada penelitian ini dibatasi untuk n ≥ 7,d ≥ 3,n−d ≥ 4 dan 2|n−d dan d yang digunakan d ganjil dan banyaknya bandul n−d 2 juga ganjil. Tujuan dari penelitian ini adalah menentukan bilangan kromatik antiajaib lokal, menentukan bilangan kromatik total antiajaib lokal, menganalisis keterkaitan antara LAVC dengan LATVC,dan keterkaitannya dalam menumbuhkan keterampilan berpikir tingkat tinggi berdasarkan Taksonomi Bloom yang telah direvisi. Penelitian ini menggunakan jenis penelitian eksploratif dan metode yang digunakan yakni metode deduktif aksiomatik dan pendeteksian pola. Hal tersebut diterapkan pada konsep pewarnaan titik antiajaib lokal pada graf sapu yaitu Bn,d dan DBn,d. Hasil penelitian ini berupa teorema, lemma dan konjektur baru serta keterkaitannya dalam menumbuhkan keterampilan berpikir tingkat tinggi. 1) hasil tentang pewarnaan titik dengan pelabelan sisi antiajaib lokal (LAVC) pada graf sapu sebagai berikut: Teorema 1. Untuk d ≥ 3 dan n−d ≥ 2, bilangan kromatik antiajaib lokal pada graf sapu Bn,d adalah χlan−d + 2. Konjektur 1. Untuk d ≥ 3,d ganjil dan n−d 2 ganjil, bilangan kromatik antiajaib lokal pada graf sapu ganda DBn,d adalah χla(DBn,d) = n−d + 1. 2) hasil tentang pewarnaan titik dengan pelabelan total antiajaib lokal (LATVC) pada graf sapu sebagai berikut: Lemma 1. Untuk Bn,d adalah graf sapu memiliki batas bawah bilangan kromatik total antiajaib lokal untuk graf Bn,d adalah (χlat = 3;n < 7+2d−√48d−23 2 atau n > 7+2d+√48d−23 2 2≤χlat ≤3; 7+2d−√48d−23 2 ≤n≤ 7+2d+√48d−23 2 Teorema 2. Untuk Bn,d adalah graf sapu (Broom Graph) dengan d ≥ 3 dan n−d ≥ 2 maka didapatkan bilangan kromatik total antiajaib lokal graf sapu χlat(Bn,d) = 3. Lemma 2. Untuk DBn,d adalah graf sapu ganda memiliki batas bawah bilangan kromatik total antiajaib lokal untuk graf Bn,d adalah (χlat = 3;n < d+19−√48d+289 2 atau n > d+19+√48d+289 2 2≤χlat ≤3; d+19−√48d+289 2 ≤n≤ d+19+√48d+289 2 Teorema 3. Untuk DBn,d adalah graf sapu ganda (Double Broom Graph) dengan n≥7,d≥3,n−d≥4 dan 2|n−d maka didapatkan bilangan kromatik total antiajaib lokal graf sapu χlat(DBn,d) = 3. Keterkaitan antara pelabelan sisi antiajaib lokal dengan pelabelan total antiajaib lokal dalam pewarnaan titik yaitu dengan membandingkan bilangan kromatik yang dihasikan dari pewarnaan titik dengan pelabelan sisi antiajaib lokal (LAVC) yaitu χla(G) dengan bilangan kromatik dari pewarnaan titik dengan pelabelan total antiajaib lokal (LATVC) χlat(G). Berdasarkan bilangan kromatik yang dihasilkan bahwa bilangan kromatik antiajaib lokal χla(G) lebih besar dibandingkan bilangan kromatik total antiajaib lokal χlat(G) . Hal ini dapat terjadi karena pada LAVC bobot titik di bandul hanya dipengaruhi oleh pelabelan sisi yang mengakibatkan warna/ bobot titik berbeda (padahal boleh sama karena titik pada bandul tidak bertetangga) sedangkan pada LATVC komponen pelabelannya terdiri dari sisi dan titik sehingga memungkinkan bobot titiknya sama. Keterkaitan menumbuhkan keterampilan berpikir tingkat tinggi dalam proses menemukan bilangan kromatik antiajaib lokal yaitu diawali dari tahap mengingat jenis graf yang akan digunakan, mengingat terminologi graf dan mendefinisikan pewarnaan titik antiajaib lokal; memahami pewarnaan titik antiajaib lokal dengan memberikan contoh dan menentukan kardinalitasnya; menerapkan konsep dan teorema pewarnaan titik antiajaib lokal pada graf sapu; menganalisis pola pewarnaan titik antiajaib lokal yang tepat pada graf sapu, mengevaluasi batas bawah bilangan kromatik antiajaib lokal, fungsi sisi dan bobot titik dari pewarnaan titik antiajaib lokal dan menciptakan teorema baru dalam pewarnaan titik antiajaib lokal.