Pewarnaan Simpul pada Hipergraf dengan Pendekatan Matriks

Abstract

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.