Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Roda

Muhammad Abdy(1*), Rahmat Syam(2), T. Tina(3),

(1) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(2) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(3) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(*) Corresponding Author




DOI: https://doi.org/10.35580/jmathcos.v4i2.24443

Abstract


Penelitian ini bertujuan mengkonstruksi graf dual dari graf roda (Wn*) dan menentukan bilangan kromatik graf dual dari graf roda (Wn*). Penelitian ini dimulai dari menggambarkan beberapa graf roda  dari  ke , kemudian membangun graf dual dari graf roda  dengan memanfaatkan graf-graf dari  ke , kemudian memberikan warna pada titik-titik dari graf dualnya dengan menentukan bilangan kromatiknya. Diperoleh hasil bahwa Graf roda  merupakan graf self-dual karena isomorfik dengan graf dualnya yaitu . Pewarnaan titik diperoleh dengan menentukan bilangan kromatik graf dual dari graf roda, menentukan pola dari bilangan kromatik, dan memberikan warna. Berdasarkan hasil penelitian, diperoleh bilangan kromatik pewarnaan titik pada graf dual dari graf roda yakni

 

Kata Kunci: Pewarnaan Titik, Bilangan Kromatik, Graf Dual dan Graf Roda.

This research aims to construct a dual graph from a wheel graph (Wn*) and determine the dual graph chromatic number of the wheel graph (Wn*). This research starts from describing some wheel graph   from  to , then construct a dual graph from a wheel graph   from  to , then gives color to the vertices of the dual graph by determining the chromatic number. The result showed that the wheel graph  is a self-dual graph because it is isomorphic with its dual graph, namely . The vertex coloring is obtained by determining the chromatic number of the dual graph of the wheel graph, determining the pattern of the chromatic number and giving the color. Based on the research results, the chromatic number of vertex coloring on dual graph of a wheel graph is:   

 

Keywords: Vertex Coloring, Chromatic Number, Dual Graph and Wheel Graph.


Full Text:

PDF

References


Abdussakir. (2009). Teori Graf. Malang: UIN Malang Press.

Assadillah, M. H. (2009). Dari Graf Roda (W_n) dan Graf Gear (G_n) (Skripsi). Universitas Islam Negeri, Malang.

Dewi, F. K. S. (2010). Pembangun Perangkat Lunak Pembangkit Jadwal Kuliah dan Ujian dengan Metode Pewarnaan Graf. Jurnal Buana Informatika, 1(1), 57-68.

Hasanah, U. (2012). Modifikasi Algoritma Welch-Powell untuk Pewarnaan Graf (Vertex Colouring) pada Penjadwalan Kuliah Jurusan Matematika Fakultas Sains Dan Teknologi UIN Suska Riau (Skripsi). Universitas Islam Negeri Sultan Syarif Kasim Riau, Pekan Baru.

Mahardika, F., & Marcos, H. (2017). Penerapan Algoritma Graf Welch Powel pada Penjadwalan Mata Kuliah dan Jadwal Asisten Study Kasus Forum Asisten Stmik Amikom Purwokerto. Jurnal Simetris, 8 (2). 825-832.

Muhib. (2013). Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Piramida (Prn*) (Skripsi). Universitas Islma Negeri Maulana Malik Ibrahim, Malang.

Puspasari, D. S., & Dafik. (2014). Pewarnaan Titik pada Graf Khusus: Operasi dan Aplikasinya. Prosiding Seminar Nasional Matematika, 1(1), 50-58.

Setiawan, I. 2012. Pewarnaan Graf dan Aplikasinya (Skripsi). Universitas Negeri Makassar, Makassar.

Supriyandi & Eka, M. (2018). Penerapan Teknik Pewarnaan Graph pada Penjadwalan Ujian dengan Algoritma Welch-Powell. Jurnal Ilmu Komputer dan Informatika, 3(1), 58-63.

Welyyanti, D. (2018). Beberapa Syarat Cukup untuk Bilangan Kromatik Lokasi Hingga pada Graf Tak Terhubung. Jurnal Eksakta, 19(1), 76-82.


Article Metrics

Abstract view : 226 times | PDF view : 30 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 JMathCos (Journal of Mathematics, Computations, and Statistics)

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Indexed by:

 

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.