Aplikasi Pewarnaan Graf pada Penempatan Kamar Mahasiswa (Studi Kasus: Asrama Institut Teknologi Sumatera)

Authors

  • Sri Efrinita Irwan Institut Teknologi Sumatera

DOI:

https://doi.org/10.31851/sainmatika.v17i1.3137

Keywords:

graph, adjacency matrix, Welsh-Powell algorithm

Abstract

This article discusses the application of graph colouring to the placement of students room. The sample data used is the data of prospective students resident ofInstitut Teknologi Sumatera. The graph colouring process in this article utilizes the Welsh-Powell algorithm and related algebraic theories to facilitate the data processing. The process is carried out to find out the minimum number of rooms needed to place a number of students so that there are no students come from the same study program or UKT group in one room.

 

ABSTRAK

 

Artikel ini membahas aplikasi pewarnaan graf pada penempatan kamar mahasiswa. Sampel data yang digunakan adalah data calon mahasiswa penghuni asrama Institut Teknologi Sumatera. Proses pewarnaan graf pada artikel ini memanfaatkan algoritma Welsh-Powell dan teori aljabar terkait untuk mempermudah proses pengolahan data. Proses tersebut dilakukan untuk mengetahui jumlah minimum kamar yang dibutuhkan untuk menempatkan sejumlah mahasiswa sehingga tidak ada mahasiswa yang berasal dari program studi atau pun golongan UKT yang sama dalam satu kamar.

 

References

Biggs, N. (1996). Algebraic Graph Theory 2nd edition. New York: Cambridge University.

Bincy, A. K. dan Pressitha, B. J. (2017). Graph coloring and its real time applications an overview. International Journal of Mathematics and its applications. Vol. 5. 845-849.

Diestel, R.(2005).Graph theory 3rd edition. New York: Springer-Verlag Heidelberg.

Gupta, P. and Sikhwal, O. (2014). A study of vertex-edge coloring techniques with application. International Journal of Core Engineering & Management. Vol. 1. 27-32.

Irwan, S. E. and Muliawati, T.(2019).A graph theory approach to the dormitory room placement problem.Journal of Science and Applicative Technology: ICOSITER Special Edition. Vol. 2 No. 1. 111-118.

Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica Ser. El. Eng. Vol. 48 No. 1. 11-16.

Tosuni, B. (2015). Graph theory in computer science – an overview. International Journal of Academic Research and Reflection. Vol. 3 No. 4. 55-62.

Downloads

Additional Files

Published

2020-04-20

Issue

Vol. 17 No. 1 (2020): Sainmatika : Jurnal Ilmiah Matematika dan Ilmu Pengetahuan Alam

Section

Articles

License

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a  Creative Commons Attribution 4.0 International License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Creative Commons License