## Muhlisatul Mahmudah
Meminimalkan Pengembangan Danau Pada Titik Pertemuan Sungai Untuk Mengurangi Banjir Di Jakarta M enggunakan Aplikasi Dominating Set Muhlisatul Mahmudah, S. Pd., M, Si

## Maxlisa742@gmail.com
Universitas Islam Jember

## Abstrak
Salah  satu  teori  yang  dikembangkan  dalam  teori  graf  adalah  dominating  set. Dominating  set  merupakan  suatu  konsep  penentuan  titik  seminimal  mungkin  pada  graf dengan  ketentuan  titik  sebagai  dominating  set  menjangkau  titik  yang  ada  di  sekitarnya. Kardinalitas  terkecil  dari  dominating  set  disebut  domination  number  yang  dinotasikan dengan  (G)..  Diberikan  graf  G  dengan V  titik  dan  E  sisi,  misalkan  D  merupakan  subset dari V. Jika setiap titik dari V-D saling adjacent sedikitnya dengan satu titik dari D, maka D dikatakan dominating set dalam graf G. Saat ini banyak sekali aplikasi dari domintaing set,  salah  satunya  yaitu Meminimalkan  Pembangunan  Danau  Pada  Titik  Pertemuan Sungai Untuk Mengurangi Banjir Di Jakarta . Didalam penelitian ini akan dibangun danau dititik  pertemuan  sungai  untuk  mengurangi  banjir  yang  ada  di  Jakarta. Banjir  adalah bencana alam  yang saat ini sering  melanda wilayah di  Indonesia. Khususnya di Jakarta. Jakarta  adalah  salah  satu  daerah  beresiko  banjir  di  Indonesia  dan  selalu  banjir  ketika musim  hujan  tiba.  Begitu  banyak  cara  untuk  menguranginya,  tetapi  itu  tidak  berhasil. Salah  satu  penyebab  banjir  di  Jakarta  yaitu  meluapnya  air  sungai.  Ketika  musim  hujan tiba.  beberapa  sungai  yang  memiliki  arus  besar,  aliran  air  akan  bertabrakan  di  titik pertemuan. Ketika sungai mengalir, air akan meluap cukup besar kedaratan. Oleh karena itu,  Penting  untuk  pengembangan  danau  di  titik  pertemuan  sungai  akan  tetapi pi diperlukan seminimal mungkin untuk pembuatan danau tersebut dan tentunya juga harus efisien.  Dalam  penelitian  difokuskan  aplikasi  dominating  set  terhadap  pembangunan danau disetiap titik pertemuan sungai yang ada dijekarta . Kata Kunci : dominating set, sungai, danau

## Abstract
One of the theories developed in graph theory is the dominating set. Dominating set is a  concept  of  determining  the  minimum  point  on  the  graph  with  the  provision  of  a  point  as dominating set to reach the point that is around it. The smallest cardinality of the dominating set is called the domination number denoted by (G). Given graph G with point V and E side, let D be a subset of V. If each point of VD is adjacent at least one point from D, then D is said dominating set in  graph  G.  Currently  a  lot  of  applications  from  dominating  set,  one  of  which  is  Minimizing  the Construction of Lakes at River Meeting Points to Reduce Floods in Jakarta. In this study a river meeting will be rebuilt to select floods in Jakarta. Flooding is a natural disaster which is currently often in Indonesia. Especially in Jakarta. Jakarta is one of the risk areas for flooding in Indonesia and  floods  that  always  occur suddenly  There  are  so  many ways  to  reduce  them, but  that  doesn't work. One of the causes of flooding in Jakarta is the overflow of river air. When a patient appears suddenly several rivers that have large currents, air flow will collide at the meeting point. When the river flows, the air will overflow large enough. Therefore, it is important to develop a lake at the river meeting point but it is necessary to make the lake as minimal as possible and also to be efficient.  The  research  application  dominates  the  set  of  lake  developments  in  each  river  meeting point in the city.
Keywords : dominating set, river, flood

## Muhlisatul Mahmudah

## PENDAHULUAN
Teori  graf  merupakan  cabang  ilmu  matematika  diskrit  yang  banyak penerapannya  dalam  berbagai  bidang  ilmu  seperti  engineering,  ﬁsika,  biologi, kimia,  arsitektur,  transportasi,  teknologi  komputer,  ekonomi,  sosial  dan  bidang lainnya.  Teori  graf  juga  dapat  diaplikasikan  untuk  menyelesaikan  persoalan  - persoalan,  seperti  Travelling  Salesperson  Problem,  Chinese  Postman  Problem, Shortest  Path,  Electrical  Network  Problems,  Graph  Coloring,  dan  lain-lain  [9]. Dominating  number  dinotasikan  γ(G)  adalah  kardinalitas  minimum  dari  sebuah dominating  set  yang  merupakan  pengembangan  dari  penelitian-penelitian sebelumnya. Nilai dari dominating number selalu γ(G) ⊆ V (G). Mengenai batas atas  dari  dominating  number  adalah  banyaknya  titik  pada  graf.  Ketika  paling sedikit  satu  titik  yang  dibutuhkan  untuk  himpunan  dominasi  di  graf,  maka  1  ≤ γ(G) ≤ n untuk setiap graf yang berordo n. Diketahui graf G = (V,E). Misalkan D merupakan subset dari V  . Jika setiap titik dari V  – D  saling adjacent  sedikitnya dengan satu titik dari D, maka D dikatakan himpunan dominasi dalam graf G [6].
Himpunan  dominasi  minimal  adalah  himpunan  dominasi  yang  tidak  ada titik yang dapat dihilangkan tanpa mengubah dominasinya. Himpunan kebebasan independent  set  dari  graf  G  adalah  suatu  himpunan  titik  -  titik  dengan  tidak  ada dua titik dalam himpunan yang saling berdekatan (adjacent). Bilangan kebebasan independent  number  merupakan  kardinalitas  terbesar  dari  himpunan  kebebasan dan  dinotasikan  dengan  β(G).  Himpunan  kebebasan  maksimal  adalah  himpunan kebebasan  yang  tidak  ada  titik  lainnya  dapat  ditambahkan  kedalamnya  tanpa mengubah kebebasannya [4].

## METODE
Metode yang digunakan dalam menentukan dominating set yaitu:
1. Menentukan objek penelitian berupa pembanguan titik temu sungai yang ada di Jakarta
2. Mempersentasikan sungai-sungaiyang ada di Jakarta kedalam konstruksi graf.
3. Menentukan dominating set terhadap wilayah-wilayah tersebut.
4. Menetukan  bilang  kromatik  atau  bilangan  minimum  yang  digunakan  atau dihasilkan dalam dominating set.

## Muhlisatul Mahmudah

## HASIL DAN PEMBAHASAN
Banjir  adalah  bencana  alam  yang  saat  ini  sering  melanda  wilayah  di Indonesia. Khususnya di Jakarta. Jakarta adalah salah satu daerah beresiko banjir di Indonesia dan selalu banjir ketika musim hujan tiba. Begitu banyak cara untuk menguranginya,  tetapi  itu  tidak  berhasil.  Wilayah  Jakarta  dikelilingi  oleh beberapa sungai yang selalu meluap ketika musim hujan tiba.
Jika  beberapa  sungai  yang  memiliki  arus  besar,  aliran  air  akan bertabrakan  di  titik  pertemuan.  Ketika  sungai  mengalir,  air  akan  meluap  cukup besar  kedaratan.  Oleh  arena  itu,  perlu  dibangunnya  danau  dititik  pertemuan sungai.  Secara umum, danau didefinisikan sebagai  bangunan seri  yang berfungsi untuk mengisi air dari sungai atau hujan. Jadi ketika aliran air bertabrakan di titik pertemuan  sungai,  danau  akan  mengisi  air  dari  sungai.  Hal  itu  bisa  mengurangi lupan  air  ke  darat.  Dengan  menggunakan  metode  dominating  set  kita  dapat mengatur pembangunan  danau, jadi tidak perlu  membangun danau di  setiap titik pertemuan  sungai.  Hal  itu  karena  jumlah  danau  yang  besar  tidak  akan    efisien. Berikut merupakan peta kota Jakarta.
Gambar 1. Peta wilayah Jakarta
Gambar 1 merupakan peta wilayah jakarta yang dialiri sungai. Dari peta tersebut sangat  tidak  efisien  jika  disetiap  pertuman  sungai  dibangun  danau.  Oleh  karena itu,  diperlukan  pembangunan  danau  seminimal  mungkin  untu  setiap  titik pertemuan sungai tersebut.
Selanjutnya  jika  diperesentasikan  kedalam  kontruksi  graf,  maka  akan menjadi  seperti  gambar  2.  Dimana  setiap  titik  temu  sungai  dinotasikan  dengan

## Muhlisatul Mahmudah
vertex  dan  dan  aliran  sungai    dinotasikan  dengan  edge.  Untuk  semua  titik  temu sungai diberi vertex dari 1 hingga 26.
Gambar 2. Reprensentasi graf
Dari  gambar  2,  dapat  ditentukan  dominating  set  dengan  dasar  bahwa semua  daerah  yang  dialiri  sungai  dapat  terhubung  secara  maksimal,  akan  tetapi diperlukan  seminimal  mungkin  untu  pembangunan  danau  di  titik  temu  sungai. Dengan  menggunakan  konsep  dari  dominating  set  maka  didapat  bilangan kromatik  atau  penempatan  terkecil  yang  dapat  digunakan  untuk  pembangunan danau di titik pertemuan sungai yang ada di daerah jakarta seperti gambar 3.
Gambar 3. Dominating set terhadap titik temu sungai jakarta Dari gambar 3, didapat bahwa bilangan kromatik dari dominating set graf tersebut yaitu  8  dimana  tertera  seperti  gambar  tersebut.  Berikut  titik  temu  sungai    yang mendominasi  daerah  aliran  sungai  jakarta  sehingga  penempatan  pembangunan danau efisien.

## Muhlisatul Mahmudah
Gambar 4. Daerah-daerah yang terdominasi
Sesuai  dengan  repprsentasi  graf  pada  peta  kota  jakarta,  maka  titik  temu sungai nomor 1 mendominasi titik temu sungai nomor 2 dan 26, titik temu sungai nomor 5 mendominasi titik temu sungai nomor 4,6 dan 7, titik temu sungai nomor 7  mendominasi  titik  temu  sungai  nomor  5,8  dan  9,  titik  temu  sungai  nomor  10 mendominasi  titik  temu  sungai  nomor  3,11  dan  12,  titik  temu  sungai  nomor  17 mendominasi titik temu sungai nomor 13, 14, 15 dan 18, titik temu sungai nomor 18 mendominasi  titik temu sungai  nomor 16,17  dan 23, titik temu sungai  nomor 21  mendominasi  titik  temu  sungai  nomor  20,22,24  dan  25,  titik  temu  sungai nomor  22  mendominasi  titik  temu  sungai  nomor  19,21  dan  23.  Jadi  dengan menggunakan dominating set semua titik temu sungai yang ada di wilayah Jakarta dapat terjangkau secara maksimal.

## KESIMPULAN DAN SARAN
1. Teori dominating set dapat digunakan berbagai macam aplikasi salah satunya yaitu pembuatan danau di titik temu sungai yang ada di Jakarta.
2. Dengan menggunakan teori  dominating set,  kita  dapat  membuat  danau  yang ditempatkan  di  beberapa  titik  temu  sungai    yang  ada  jakarta  dengan  lebih cepat dan efisien. Selain itu, kita juga dapat menemukan jumlah kompartmen minimum  yang  dibutuhkan  untuk  pembuatan  danau  di  sejumlah  titik  temu

## Muhlisatul Mahmudah
sungai.  Hal  ini  tentunya  lebih  menguntungkan  agar  pembangunan  danau menjadi lebih efisien karena kompartmennya yang tidak terlalu banyak.

## DAFTAR RUJUKAN
[1] Agustin I.H. dan Dafik (2014). On the domination number of some families of special  graphs. prosiding  seminar  matematika  dan  pendidikan  matematika unversitas jember. 1(1).
[2]  Alfarisi.R.,  Dafik.  dan  Fatahillah.analisa  himpunan  dominasi  pada  graf-graf khusus. prosiding seminar matematika dan pendidikan matematika unversitas jember.1(1).
[3]  Daﬁk,  Structural  Properties  and  Labeling  of  Graphs,  University  of Ballarat,2007.
[4] Harrary. F. (2007).Graph Theory.Addison:Wesley.
[5]  Hayness,T.W.,Hedetniemi,S.T.,  and  Slater,P.J,.(1998). Fundamentals  of domination in Graph. New York:Marcel Dekker.
[6]  Hayness,T.W.,  and  Henning,M.A,.(2002).Total  Domination  good  vertices  in graphs. Australasian Journal of combinatoric , page 305-315.
[7]  Joseph  A.  Gallian,  A  Dynamic  Survey  of  Graph  Labeling,  University  of Minnesota, 1997.
[8]  Kavitha  dan  Govindarajan,  A  Study  on  Achromatic  Coloring  Graphs  and  its Applications, Dravidian University. ISSN: 2319-7064. 105-108, 2013.
[9]  Lu.  H,  Vertex-Coloring  Edge-Weighting  of  Bipartite  Graphs  with  Two  Edge Weights, Xian Jiaotong University, 2013.
[10]  Micha  l  Karonski,  Tomasz  Luczak,  and  Andrew  Thomason,  Edge  Weights and Vertex Colours, Journal of Combinatorial Theory, Series B, 91:151157, 2004.
[11] https://www.petajakarta.net/tempat-sungai-di-jakarta/ (akses  11  november 2017)