## Aplikasi Pewarnaan Graf pada Penempatan Kamar Mahasiswa (Studi Kasus: Asrama Institut Teknologi Sumatera)
Sri EfrinitaIrwan e-mail: sri.efrinita@ma.itera.ac.id
Program StudiMatematika InstitutTeknologi Sumatera

## 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.
Keywords : graph, adjacency matrix, Welsh-Powell algorithm

## 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.
Kata Kunci: graf, matriks ketetanggaan, algoritma Welsh-Powell

## PENDAHULUAN
Institut Teknologi Sumatera merupakan  salah  satu  perguruan  tinggi yang  menyediakan  asrama  sebagai  salah satu fasilitas bagi mahasiswanya,
khususnya  mahasiswa  tahun  pertama. Dalam pengelolaannya, Institut Teknologi Sumatera berupaya
menerapkan  kebijakan  yang  bertujuan untuk  melatih  jiwa  sosial  di  kalangan mahasiswa.  Salah  satu  upaya  untuk mencapai  hal  tersebut  adalah  dengan menjaga  keberagaman  mahasiswa  yang menempati  setiap  kamar  di  asrama. Namun demikian, pengolahan data
ratusan mahasiswa calon penghuni asrama  untuk  memenuhi  kriteria  yang dimaksudkan  dalam  kebijakan  tersebut bukanlah hal yang mudah untuk dilakukan secara manual.
Sementara itu, dalam cabang ilmu matematika,  permasalahan  semacam  ini biasanya  dapat  diselesaikan  dengan mengaplikasikan  teori  yang  disebut sebagai pewarnaan graf ( graph colouring ). Pewarnaan graf terbagi menjadi  beberapa  bagian,  diantaranya pewarnaan  titik  ( vertex  colouring )  dan pewarnaan sisi ( edge colouring ).
Berbagai  aplikasi  pewarnaan  graf  telah dikemukakan  diantaranya  dalam  Bincy and  Presitha  (2017),  Tosuni  (2015), Gupta  dan  Sikhwal  (2014),  dan  Marx (2004).
Dalam  Irwan  dan  Muliawati (2019),  telah  dikaji  bagaimana  teori tentang pewarnaan graf, khususnya
pewarnaan  titik,  dapat  digunakan  untuk menentukan penempatan kamar
mahasiswa  di  asrama.  Sampel  data  yang digunakan adalah data mahasiswa Institut Teknologi  Sumatera.  Hal  ini  bertujuan untuk  memudahkan  pengolahan  data mahasiswa  calon  penghuni  asrama  untuk memenuhi  kriteria  yang  dimaksudkan dalam kebijakan-kebijakan yang diberlakukan di lingkungan Institut
Teknologi Sumatera. Pada artikel
tersebut,  pengaturan  penempatan  kamar mahasiswa  dilakukan  agar  tidak  ada mahasiswa  yang  berasal  dari  program studi  ataupun  daerah  asal  yang  sama dalam  satu  kamar.  Namun  demikian, hasil  yang  diperoleh  tidak  mendukung efektivitas  penggunaan  kamar  asrama. Hal  ini  disebabkan  mayoritas  calon mahasiswa  penghuni  asrama  berasal  dari propinsi Lampung.
Pada  artikel  ini,  golongan  UKT
mahasiswa  dijadikan  indikator  pengganti daerah asal dalam
pengaturan penempatan kamar mahasiswa. Selain itu, proses  pewarnaan  graf  pada  artikel  ini akan  memanfaatkan  teori  aljabar  terkait untuk  mempermudah  proses  pengolahan data. Dalam Diestel (2005)
dikemukakan  bahwa  graf  ( graph )  adalah suatu  pasangan  himpunan 𝐺 = (𝑉, 𝐸) sehingga 𝐸 ⊆ [𝑉] 2 ,  akibatnya  unsur- unsur  di 𝐸 merupakan  subhimpunan- subhimpunan  dari 𝑉 yang  terdiri  dua unsur di 𝑉 . Unsur-unsur di 𝑉 adalah titik- titik  ( vertices )  dari  graf 𝐺 ,  sedangkan unsur-unsur  di 𝐸 adalah  sisi-sisi  ( edges ) dari graf tersebut.
Himpunan  titik-titik  dari  graf 𝐺 dinotasikan  sebagai 𝑉(𝐺) ,  sedangkan
himpunan sisi-sisi dari graf 𝐺 dinotasikan sebagai 𝐸(𝐺) .  Berikut  dikemukakan salah satu contoh graf.
Gambar 1. Graf 𝐻
Dari  gambar  tersebut  diketahui bahwa 𝑉(𝐻) = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 , 𝑣 5 , 𝑣 6 } dan 𝐸(𝐻) = {𝑒 1 , 𝑒 2 , 𝑒 3 , 𝑒 4 , 𝑒 5 } dengan 𝑒 1 = {𝑣 1 , 𝑣 6 }, 𝑒 2 = {𝑣 2 , 𝑣 3 }, 𝑒 3 = {𝑣 2 , 𝑣 4 }, 𝑒 4 = {𝑣 2 , 𝑣 6 }¸𝑒 5 = {𝑣 3 , 𝑣 4 }, 𝑒 6 = {𝑣 3 , 𝑣 6 }, 𝑒 7 = {𝑣 4 , 𝑣 6 } .
Beberapa istilah berikut merupakan istilah dasar tentang graf yang diperlukan dalam pembahasan
selanjutnya.
1. Dua  titik 𝑥 dan 𝑦 dari  graf 𝐺 dikatakan  bertetangga  ( adjacent ) jika {𝑥, 𝑦} adalah  suatu  sisi  dari graf 𝐺 ,  yaitu  jika  titik 𝑥 dan 𝑦 dihubungkan  oleh  suatu  sisi  dari graf 𝐺 .
2. Suatu  sisi 𝑒 dikatakan  bersisian
( incident )  dengan  titik 𝑣 1 dan 𝑣 2 jika 𝑒 = {𝑣 1 , 𝑣 2 } , yaitu 𝑒 menghubungkan titik 𝑣 1 dan 𝑣 2 . 3. Suatu  titik 𝑣 pada  graf 𝐺 dikatakan memiliki derajat ( degree ) 𝑛 jika  terdapat 𝑛 buah sisi  yang  bersisian  dengan 𝑣 . Derajat  dari  titik 𝑣 dinotasikan dengan 𝑑(𝑣) .
Pada graf, dikenal istilah pewarnaan graf ( graph colouring ).
Pewarnaan graf dibedakan menjadi beberapa  jenis,  diantaranya  pewarnaan titik  ( vertex  colouring )  dan  pewarnaan sisi  ( edge  colouring ).  Pada  artikel  ini,
𝑣 2 𝑣 3 𝑣 1 𝑣 4
𝑣 6 𝑣 5
pewarnaan  graf  yang  dimaksud  adalah pewarnaan titik.
Secara  formal,  suatu  pewarnaan titik  dari  suatu  graf 𝐺 = (𝑉, 𝐸) adalah suatu  pemetaan 𝑐 ∶ 𝑉 → 𝑆 sehingga 𝑐(𝑣 1 ) ≠  𝑐(𝑣 2 ) jika 𝑣 1 bersisian  dengan 𝑣 2 .  Dalam  hal  ini, 𝑆 merupakan himpunan  yang  terdiri  dari  warna-warna yang tersedia untuk titik-titik pada graf 𝐺 . Informasi  penting  yang  diperlukan  dari himpunan 𝑆 adalah  tentang  ukuran himpunan  itu  sendiri.  Oleh  karena  itu, suatu  pewarnaan  titik 𝑐 ∶ 𝑉 → 𝑆 dapat dibatasi  menjadi 𝑐 ∶ 𝑉 → {1, 2, 3, … , 𝑘} untuk  menyatakan  bahwa  graf 𝐺 dapat diwarnai dengan 𝑘 warna berbeda.
Bilangan  bulat  positif  terkecil 𝑘 yang memenuhi aturan pewarnaan titik di atas  disebut  sebagai  bilangan  kromatik ( chromatic  number )  dari  graf 𝐺 dan dinotasikan  sebagai 𝜒(𝐺) .  Bilangan kromatik  yang  dimaksud  terkait  dengan pewarnaan  titik  pada  graf 𝐺 .  Untuk selanjutnya,  istilah  pewarnaan  dalam penelitian ini dikhususkan untuk pewarnaan titik pada graf.
Berikut  dikemukakan  salah  satu contoh pewarnaan graf.
Gambar 2. Graf 𝐻 dengan pewarnaan 𝑐 ∶ 𝑉 → {1, 2, 3, 4}
Dari  gambar  tersebut,  terlihat bahwa  graf 𝐻 yang  memiliki  enam  titik dapat  diwarnai  dengan  empat  warna sehingga  setiap  dua  titik  yang  bersisian memiliki warna yang berbeda.
Proses  pewarnaan  graf  pada artikel  ini  akan  memanfaatkan  teori aljabar  terkait  untuk  mempermudah
proses  pengolahan  data,  yaitu  teori tentang  matriks  ketetanggaan  dari  suatu graf.  Teori  tersebut  dijelaskan  dalam Biggs (1993) sebagai berikut.
Misalkan 𝐺 suatu  graf  dengan 𝑛 buah  titik.  Matriks  ketetanggaan  dari 𝐺 , yang  dinotasikan  dengan 𝐴 = 𝐴(𝐺) , adalah  suatu  matriks  berukuran 𝑛 × 𝑛 dengan entri
𝑎 𝑖𝑗 = { 1, 0, jika 𝑣 𝑖 dan 𝑣 𝑗 bertetangga; lainnya.
Dengan  demikian,  jelas  bahwa 𝐴 adalah  suatu  matriks  simetrik.  Sebagai contoh, matriks ketetanggaan dari graf 𝐻 pada Gambar 1 adalah
𝐴(𝐻) =
[ 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0] .
Matriks ketetanggaan dapat mempermudah  proses  pewarnaan  graf, khususnya  untuk  graf  yang  memiliki banyak  titik.  Jumlah  dari  entri-entri  pada baris  (kolom)  ke- 𝑖 menyatakan  derajat dari titik 𝑣 𝑖 .
Salah  satu  algoritma  yang  dapat digunakan  dalam  proses  pewarnaan  graf adalah  algoritma  Welsh-Powell  yang dinyatakan sebagai berikut:
1. Tentukan  derajat  dari  masing- masing titik pada graf.
2. Urutkan titik-titik pada graf berdasarkan derajatnya (dari derajat terbesar ke derajat terkecil).
3. Gunakan  warna  pertama  untuk mewarnai  titik  dengan  derajat tertinggi.
4. Warnai  setiap  titik  yang  tidak bertetangga  dengan  titik  tersebut dengan menggunakan warna yang sama.
5. Ulangi  proses  pemberian  warna (dengan  warna  berbeda)  terhadap
4 3 2 2 1 1
titik-titik yang belum diberi warna sampai semua titik diwarnai.

## HASIL DAN PEMBAHASAN
Pada  penelitian  terdahulu,  Irwan dan Muliawati (2019) membahas aplikasi pewarnaan  graf  pada  penentuan  kamar mahasiswa  di  asrama  Institut  Teknologi Sumatera.  Pengaturan  tersebut  dilakukan untuk mengatur agar tidak ada mahasiswa yang berasal dari program studi atau pun daerah asal yang sama dalam satu kamar. Namun demikian, indikator tersebut tidak mendukung efektivitas penggunaan kamar. Hal ini disebabkan oleh kenyataan bahwa  lebih  dari  50%  mahasiswa  calon penghuni  asrama  berasal  dari  daerah Lampung.
Berdasarkan fakta di atas, diperlukan  indikator  pengganti  dalam penentuan  kamar  mahasiswa  di  asrama Institut Teknologi Sumatera. Pada artikel ini,  indikator  daerah  asal  diganti  dengan indikator  golongan  UKT.  Selain  untuk meningkatkan  efektivitas  penggunaan kamar  di  asrama  Institut  Teknologi Sumatera, pemilihan indikator ini sebagai upaya  dalam  mendukung  kebijakan institusi  untuk  memupuk  rasa  saling menghargai  dan  tolong-menolong  di kalangan mahasiswa melalui keberagaman status ekonomi. Sampel data dari calon mahasiswa
penghuni  asarama  Institut  Teknologi Sumatera diberikan sebagai berikut.
Tabel  1.  Sampel  data  dari  calon mahasiswa penghuni asrama.
No Nama Mahasiswa Program Studi Gol. UKT 1 Mahasiswa 1 Teknik Informatika 2 2 Mahasiswa 2 Teknik Geofisika 4 3 Mahasiswa 3 Teknik Lingkungan 1 4 Mahasiswa 4 Teknik Elektro 3 5 Mahasiswa 5 Teknik Lingkungan 0 6 Mahasiswa 6 Teknik Geomatika 5 7 Mahasiswa 7 Fisika 1 8 Mahasiswa 8 Matematika 3 9 Mahasiswa 9 Teknik Geofisika 0 10 Mahasiswa 10 Teknik Sipil 1 11 Mahasiswa 11 Teknik Geomatika 2 12 Mahasiswa 12 Teknik Geofisika 3 13 Mahasiswa 13 Teknik Geomatika 4 14 Mahasiswa 14 Teknik Geologi 0 15 Mahasiswa 15 Teknik Geologi 3 Representasi data di atas ke dalam bentuk  graf  dijelaskan  sebagai  berikut. Setiap  mahasiswa  mewakili  satu  titik pada  graf  sehingga  diperoleh  suatu  graf 𝐺 yang  terdiri  dari  15  titik  misalkan
𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 15 } . Titik 𝑣 𝑖 dikatakan bertetangga dengan titik 𝑣 𝑗 jika mahasiswa 𝑖 dan  mahasiswa 𝑗 berasal dari  program  studi  atau  golongan  UKT yang  sama.  Berdasarkan  data  tersebut, diperoleh  matriks  ketetanggaan  sebagai berikut.
𝐴(𝐺) =
[ 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0]
Telah  dijelaskan  bahwa  jumlah dari  entri-entri  pada  baris  (kolom)  ke- 𝑖 menyatakan  derajat  dari  titik 𝑣 𝑖 .  Dengan demikian, diperoleh derajat dari titik-titik pada graf 𝐺 sebagai berikut.
Tabel  2.  Derajat  dari  setiap  titik  pada graf.
Titik Derajat
𝑣 1 1 𝑣 2 3 𝑣 3 3 𝑣 4 3 𝑣 5 3 𝑣 6 2 𝑣 7 2 𝑣 8 3 𝑣 9 4 𝑣 10 2 𝑣 11 3 𝑣 12 5 𝑣 13 3 𝑣 14 3 𝑣 15 4
Selanjutnya,  algoritma  Welsh- Powell  digunakan  untuk  memastikan bahwa tidak ada mahasiswa yang berasal dari  program  studi  atau  pun  golongan UKT  yang  sama  dalam  satu  kamar. Penerapan  algoritma  tersebut  diawali dengan  mengurutkan  titik-titik  pada  graf 𝐺 berdasarkan  derajatnya  (dari  derajat terbesar  ke  derajat  terkecil).  Diperoleh hasil sebagai berikut.
Tabel 3. Urutan titik dari derajat tertinggi dan pewarnaan titik.
No Titik Derajat Warna 1 𝑣 12 5 1 2 𝑣 15 4 2 3 𝑣 9 4 2 4 𝑣 14 3 1 5 𝑣 13 3 1 6 𝑣 11 3 2 7 𝑣 8 3 3 8 𝑣 5 3 3 9 𝑣 4 3 4 10 𝑣 3 3 1 11 𝑣 2 3 3 12 𝑣 10 2 2
13 𝑣 7 2 3 14 𝑣 6 2 3
15 𝑣 1 1 1
Berdasarkan Tabel 3 di atas, dapat disimpulkan  bahwa  bilangan  kromatik dari graf 𝐺 adalah 4.

## KESIMPULAN
Berdasarkan  penjelasan  di  atas, dapat  disimpulkan  bahwa  hasil  yang diperoleh pada artikel ini jelas lebih baik jika  dibandingkan  dengan  hasil  yang dikemukakan dalam Irwan dan Muliawati (2019).  Dalam  artikel  tersebut  diperoleh bahwa bahwa bilangan kromatik dari graf 𝐺 adalah  8.  Dengan  asumsi  bahwa kapasitas  maksimal  adalah  4  orang  per kamar,  dibutuhkan  9  kamar  untuk menempatkan  15  mahasiswa  tersebut sehingga  tidak  ada  mahasiswa  yang berasal  dari  program  studi  atau  pun daerah  asal  yang  sama  dalam  satu kamar.Sedangkan  dalam  artikel  ini, diperoleh  bahwa  bilangan  kromatik  dari graf 𝐺 adalah  4.  Dengan  asumsi  yang sama bahwa kapasitas maksimal adalah 4 orang  per  kamar,  hanya  dibutuhkan  6 kamar untuk menempatkan 15 mahasiswa tersebut  sehingga  tidak  ada  mahasiswa yang berasal dari program studi atau pun golongan  UKT  yang  sama  dalam  satu kamar.

## Ucapan Terima Kasih
Penelitian  ini  didanai  oleh  Hibah Mandiri  Institut  Teknologi  Sumatera  No. 134bl/IT9.C1/PP/2018.

## DAFTAR PUSTAKA
Biggs,  N.  (1996). Algebraic  Graph Theory  2 nd 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 3 rd 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.