Pewarnaan Simpul pada Hipergraf dengan Pendekatan Matriks
Keywords:
Hipergraf, Hyperedge, Pewarnaan simpul, Teori grafAbstract
As the science develops, the concept of hypergraphs is introduced, which is a generalization of graphs. Graphs are composed of pairs of vertices set and edges set, while hypergraphs are composed of pairs of vertices set and hyperedges set. Hyperedges connect 2 or more vertices in the hypergraph. Vertex coloring on hypergraphs can be used to solve various mapping problems. In this study, vertex coloring on hypergraphs is carried out using the vertex coloring algorithm on hypergraphs with a matrix approach. In order to make the vertex coloring on hypergraph efficient, a computer application program is formed in this research. This program is prepared by translating the algorithm into Python high-level language. The program is executed by giving input of hyperedge set, vertex set, and also many colors to be used. The result of this program is a visualization of all vertex coloring schemes on the hypergraph.
Keywords: Graph theory, Hyperedge, Hypergraph, Vertex coloring.
ABSTRAK
Seiring berkembangnya ilmu pengetahuan, diperkenalkan konsep hipergraf yang merupakan generalisasi graf. Graf tersusun dari pasangan himpunan simpul dan himpunan sisi, sedangkan hipergraf tersusun dari pasangan himpunan simpul dan himpunan hyperedge, dimana hyperedge menghubungkan 2 atau lebih simpul pada hipergraf. Pewarnaan simpul pada hipergraf dapat digunakan untuk menyelesaikan berbagai masalah penugasan. Pada penelitian ini dilakukan pewarnaan simpul pada hipergraf dengan menggunakan algoritma pewarnaan simpul pada hipergraf dengan pendekatan matriks. Agar pewarnaan simpul pada hipergraf efisien, pada penelitian ini dibentuk program aplikasi komputer. Program ini disusun dengan menterjemahkan algoritma tersebut ke dalam bahasa tingkat tinggi Python. Program dijalankan dengan memberikan input himpunan hyperedge, himpunan simpul, dan juga banyak warna yang akan digunakan. Hasil dari program ini adalah visualisasi semua skema pewarnaan simpul pada hipergraf.
References
Bahmanian, M. A., & Šajna, M. (2015). Hypergraphs: connection and separation. Theory and Applications of Graphs.
Berge, C. (1973). Balanced hypergraphs and some applications to graph theory. In A survey of combinatorial theory (pp. 15-23). North-Holland.
Bretto, A. (2013). Hypergraph theory. An introduction. Mathematical Engineering. Cham: Springer, 1, 209-216.
Cheng, D. Z., & Zhang, L. J. (2003). On semi-tensor product of matrices and its applications. Acta Mathematicae Applicatae Sinica, 19(2), 219-228.
Cheng, D. Z., & Zhang, L. J. (2003). On semi-tensor product of matrices and its applications. Acta Mathematicae Applicatae Sinica, 19(2), 219-228.
Fernández, F. M. (2016). The Kronecker product and some of its physical applications. European Journal of Physics, 37(6), 065403(1-11).
Lovász, L. (1972). Normal hypergraphs and the perfect graph conjecture. discrete Mathematics, 2(3), 253-267.
Meng, M., & Feng, J. E. (2014). A matrix approach to hypergraph stable set and coloring problems with its application to storing problem. Journal of Applied Mathematics, 2014(1), 783784 (1-9).
Pickard, J., Chen, C., Stansbury, C., Surana, A., Bloch, A. M., & Rajapakse, I. (2024). Kronecker product of tensors and hypergraphs: structure and dynamics. SIAM Journal on Matrix Analysis and Applications, 45(3), 1621-1642.
Putri, F., F., Triyani & Wardani, A. (2020). Konsep dasar hipergraf dan sifat-sifatnya. Jurnal Ilmiah Matematika dan Pendidikan Matematika (JMP). 12(2), 49-62.
Toft, B. (1974). Color-critical graphs and hypergraphs. Journal of Combinatorial Theory, Series B, 16(2), 145-161.
Wanless, I. M., & Wood, D. R. (2022). A general framework for hypergraph coloring. SIAM Journal on Discrete Mathematics, 36(3), 1663-1677.
