## Muhlisatul Mahmudah

## Aplikasi Pewarnaan Graf Terhadap Penyimpanan Bahan Kimia
Muhlisatul Mahmudah, S. Pd., M. Si
Maxlisa742@gmail.com Universitas Islam Jember
Abstrak
Graf
dimana    adalah  himpunan  titik  dan    adalah  himpunan sisi.  Aplikasi  menarik  dari  suatu  graf,  salah  satunya  adalah  pewarnaan  graf  ( graph  colouring ).  Terdapat  tiga  macam  perwarnaan  yaitu  pewarnaan  titik,  sisi, dan  wilayah.  Dalam  makalah  ini  akan  dikaji  pewarnaan  titik.  Pewarnaan  titik adalah  memberi  warna  pada  titik-titiknya  dari  suatu  graf  sedemikian  sehingga tidak ada dua titik yang bertetangga mempunyai warna yang sama. Jumlah warna minimum yang dapat digunakan untuk mewarnai graf dinyatakan dengan bilangan kromatik. Saat ini banyak sekali aplikasi dari pewarnaan graf, salah satunya yaitu penyimpanan  terhadap  bahan  kimia.  Dalam  ppenyimpanan  bahan  kimia diperlukan  pengaturan  yang  baik,  hal  ini  disebabkan  adanya  pengaruh  terhadap bahan  kimia  yang  satu  dengan  yang  lainnya  jika  disimpan  bersamaan.  Fokus utama  makalah  ini  adalah  menentukan  bilangan  kromatik  pada  graf    dan  skema aplikasi dari pewarnaan graf titik
Kata Kunci : pewarnaan graf, pewarnaan titik, pewarnaan sisi dan pewarnaan wilayah.

## Abstract
Graf  G  =  (V,  E),  where  V  is  the  set  of  points  and  E  is  the  set  of  sides. Interesting  application  of  a  graph,  one  of  which  is  graph  coloring  (graph coloring).  There  are  three  kinds  of  coloring  that  are  point  coloring,  edge coloring,  and  region  coloring.  In  this  paper  will  be  studied  dye  staining.  Point coloring is to color the dots of a graph so that no two neighboring dots have the same  color.  The  minimum  number  of  colors  that  can  be  used  to  color  graph  is expressed  by  chromatic  numbers.  Currently  a  lot  of  applications  from  graph coloring,  one  of  which  is  the  storage  of  chemicals.  In  the  storage  of  chemicals required a good arrangement, this is due to the influence of chemicals with each other  if  stored  simultaneously.The  main  focus  of  this  paper  is  to  determine  the chromatic number in graph o and the application scheme of dye graph coloring.
Keywords : graph coloring, point coloring, edge coloring and region coloring

## Muhlisatul Mahmudah

## PENDAHULUAN
Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal  dan  banyak  diaplikasikan  pada  berbagai  bidang.  (Micha,  2004)  Dalam merepresentasikan  visual  dari  suatu  graf  yaitu  dengan  menyatakan  objek  dengan simpul,  noktah,  bulatan,  titik,  atau  vertex,  sedangkan  hubungan  antara  objek dinyatakan  dengan  garis  atau  edge.  (Kavitha,  2013)  dan  (Lu.  H,  2013)  Secara umum, graf adalah pasangan himpunan  (V,E) di mana V  adalah himpunan tidak kosong  dari  simpul-simpul  (vertex  atau  node),  bisa  ditulis
dan adalah  himpunan  sisi  (edges  atau  arcs)  yang  menghubungkan  sepasang simpul pada graf tersebut, dan ditulis
. (Kaiser, 2014), (Dafik, 2008), dan (Dafik, 2007)
Dalam  makalah  ini,  akan  membahas  salah  satu  aplikasi  yang  berkaitan dengan  graf  yaitu  pewarnaan  graf  (graph  coloring),  khususnya  pewarnaan  pada titik graf G sedemikian sehingga tidak ada dua titik yang bertetangga mempunyai warna yang sama, sehingga akan diperoleh jumlah minimum warna dengan notasi ϕ(G)  dan  nantinya  akan  dinyatakan  dengan  bilangan  kromatik  dengan notasi χ(Cn). (Ardiyansah, 2013), (Kavitha, 2013), dan (Sesa, 2014)
Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik dengan batas tertentu.[4][10] Pewarnaan titik (vertex coloring) adalah memberi warna berbeda pada  titik  yang  bertetangga  sehingga  tidak  ada  dua  titik  yang  bertetangga mempunyai warna yang sama. Jumlah warna minimal ϕ(G) yang dapat digunakan untuk  mewarnai  titik-titik  dalam  suatu  graph  G  disebut  bilangan  khromatik  G. salah satu aplikasi pewarnaan graf ini yaitu pengaturan penyimanan bahan kimia. Beberapa  bahan  kimia  memiliki  zat  yang  dapat  berpengaruh  jika  disimpan  atau diltakkan  dengan  bahan  kimia  lainnya.  Oleh  karena  itu,  diperlukan  pengaturan dalam penyimpanannya.

## METODE
Metode yang digunakan dalam menentukan pewarnaan titik adalah dengan menggunakan Greedy Algorithm yaitu:
1. START

## Muhlisatul Mahmudah
2. Pilih  titik  tertentu  (lebih  baik  pilih  titik  awal  sesuai  dengan  notasi  dari  titik sebuah graf)
3. Warnai  titik  tertentu  tersebut  dengan  warna  1  dan  dilanjutkan  ke  titik-titik lainnya  sedemikian  hingga  tidak  ada  dua  titik  yang  bertetangga  memiliki warna yang sama.
4. Warnai  sisa  titik-titik  lainnya  dengan  warna  2  sedemikian  hingga  tidak  ada dua titik yang bertetangga memiliki warna yang sama.
5. Lanjutkan dengan teknik yang sama dengan warna lebih besar satu tingkat di atasnya sampai semua titik terwarnai dan warnanya adalah mencapai γ dimana γ  adalah  warna  terbesar  yang  minimal.  Maka  γ  sebagai  bilangan  kromatik pewarnaan titik.
6. STOP

## HASIL DAN PEMBAHASAN
Berikut  data  zat  kimia  yang  akan  disimpan  di  suatu  ruangan  akan  tetapi tidak  boleh  atau  tidak  bisa  disimpan  bersama  atau  berdekatan  dengan  zat  kimia lainnya (reaktifitas bahan-bahan kimia):
1. Bahan  asam  anorganik  akan  bereaksi  dengan  asam  organik,  bahan  kaustik, asam amino, serta alkohol, gliter dan gliter eter.
2. Bahan asam organik akan bereaksi dengan asam anorganik dan amino.
3. Bahan  kaustik  akan  bereaksi  dengan  asam  anorganik,  amino  serta  alkohol, gliter dan gliter eter.
4. Bahan  amino  akan  bereaksi  dengan  asam  anorganik,  asam  organik,  bahan kaustik, serta senyawa halogen.
5. Bahan bersenyawa halogen hanya bereaksi dengan amino.
6. Alkohol,  glikol  dan  glikol  eter  bereaksi  dengan  asam  anorganik  dan  asam organik.
Jika  dibuat  dalam  bentuk  tabel  akan  menjadi  sebagai  berikut,  angka  (0) jika  zat  kimia  tersebut  memilki  reaktifitas  dan  angka  (1)    jika  zat  kimia  tersebut tidak memilki reaktifitas.

## Muhlisatul Mahmudah

## Tabel 1. Matriks Reaktifitas Bahan Kimia
Keterangan:
A = Asam Anorganik B = Asam Organik C = Kaustik D = Amino
E = Senyawa Halogen
F = Alkohol
*Alkohol sama sifatnya dengan glikol dan glikol eter, sehingga dapat disatukan dalam satu baris atau kolom
Tabel 2. Senarai Reaktifitas Bahan Kimia
Berikut pemodelan dalam bentuk graf yaitu:
Gambar 1. Pemodelan Dalam Bentuk Graf

## Muhlisatul Mahmudah
Gambar 2. Vertex Coloring
Tabel 3. Hasil Pewarnaan Titik
Dari  pewarnaan  titik  yang  telah  dilakukan  maka  didapat  seperti  tabel  3 yaitu  asam  amino  dapat  disimpan  dengan  senyawa  halogen,  asam  organik disimpan dengan kaustik, amini dengan alkohol, glikol, dan glikol eter.

## KESIMPULAN
Berdasarkan  hasil  penelitian  dan  pembahasan  maka  kesimpulan  yang dapat  diambul  dari  penelitian  ini  antara  lain:  (1)  Teori  pewarnaan  simpul  graf dapat  digunakan  untuk  menyelesaikan  berbagai  macam  permasalahan,  salah satunya  adalah  permasalahan  pengaturan  penyimpanan  bahan  kimia.  (2)  Dengan menggunakan teori pewarnaan graf, kita dapat membuat konfigurasi penyimpanan bahan  kimia  dengan  lebih  cepat  dan  efisien.  Selain  itu,  juga  dapat  menemukan jumlah  kompartmen  minimum  yang  dibutuhkan  untuk  menyimpan  beberapa bahan.  Hal  ini  tentunya  lebih  menguntungkan  agar  tempat  penyimpanan  bahan kimia menjadi lebih efisien karena kompartmennya yang tidak terlalu banyak.

## Muhlisatul Mahmudah

## DAFTAR PUSTAKA
Ardiyansah. R, Bilangan Kromatik Graf Hasil Amalgamasi Dua Buah Graf, ITS. vol 2(1), 2013
Daﬁk, Structural Properties and Labeling of Graphs, University of Ballarat,2007.
Joseph  A.  Gallian,  A  Dynamic  Survey  of  Graph  Labeling,  University  of Minnesota, 1997.
Kaiser.  T,  Strong  Parity  Vertex  Coloring  of  Plane  Graphs,  University  of Primorska. vol 16(1). 143158, 2014.
Kavitha  dan  Govindarajan,  A  Study  on  Achromatic  Coloring  Graphs  and  its Applications, Dravidian University. ISSN: 2319-7064. 105-108, 2013.
Lu.  H,  Vertex-Coloring  Edge-Weighting  of  Bipartite  Graphs  with  Two  Edge Weights, Xian Jiaotong University, 2013.
Martin Baca, Stanislaf Jendrol, MirkaMiller, and Joseph Ryan, On Irregular Total Labelings, Discrete Mathematics, 307:13781388, 2007.
Micha  l  Karonski,  Tomasz  Luczak,  and  Andrew  Thomason,  Edge  Weights  and Vertex  Colours,  Journal  of  Combinatorial  Theory,  Series  B,  91:151157, 2004.
Sesa. J, Penentuan Bilangan Kromatik Fraksional pada Operasi Amalgamasi Graf Lintasan dan Graf Siklus, Universitas Hasanudin. 2014