Aplikasi Pewarnaan Graf pada Tempat Penitipan Anak

Aplikasi Pewarnaan Graf pada Tempat Penitipan Anak Susanti Gojali - 135120571 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia 1 [email protected]

Abstract — Di tempat penitipan anak, pada umumnya anak-anak yang dititipkan akan dijaga oleh pengasuh dalam suatu ruangan. Namun, tidak semua anak dapat merasa nyaman dengan anak yang lain dan dapat ditempatkan dalam satu ruangan yang sama. Beberapa anak yang memiliki ketidakcocokan satu sama lain akan ditempatkan pada ruangan yang berbeda untuk meminimalisir permasalahan yang terjadi. Untuk mendapatkan jumlah ruangan minimal yang diperlukan dalam satu waktu, dapat digunakan teknik pewarnaan graf. Teknik pewarnaan graf yang digunakan adalah pewarnaan simpul. Simpul akan merepresentasikan anak dan sisi akan merepresentasikan anak-anak yang memiliki ketidakcocokan satu sama lain. Kata Kunci — Pewarnaan Graf, Aplikasi, Penitipan Anak, Ruangan.

II. DASAR TEORI A.Graf Graf G dinyatakan sebagai pasangan himpunan (V,E). V: himpunan tidak kosong dari simpul-simpul (vertices atau node) E: himpunan sisi (edges) yang menghubungkan simpul-simpul Definisi graf tersebut menyatakan bahwa graf boleh tidak memiliki sisi namun harus terdiri minimal satu simpul. Graf yang hanya memiliki satu simpul disebut graf trivial. Contoh Graf G1 (V,E) V: {1,2,3,4,5} E: {(1,1),(1,2),(1,4),(2,3),(2,3),(2,5),(4,5)} e1 1

I. PENDAHULUAN Di era globalisasi ini, semua orang dituntut untuk bekerja. Terkadang karena tuntutan pekerjaan, anak-anak menjadi kurang terurus jika dibiarkan sendiri di rumah. Pada umumnya, setiap keluarga akan memperkerjakan pengasuh untuk mengurus anak-anaknya. Namun, ada alternatif lain yang dapat dipilih yaitu membawanya ke tempat penitipan anak untuk sementara waktu selagi mereka bekerja. Di tempat penitipan anak inilah, berkumpul anak-anak yang berasal dari berbagai keluarga. Anak-anak ini bisa merasa nyaman dan dekat satu sama lain. Namun, mereka juga bisa saling bertengkar satu sama lain. Pertengkaran dapat terjadi karena sama-sama merebutkan mainan yang sama ataupun saling menganggu satu sama lain. Pada dasarnya di tempat penitipan anak, anak-anak ini akan ditempatkan pada satu ruangan yang sama. Namun, jika banyak terjadi ketidakcocokan diantara mereka, anakanak tersebut akan ditempatkan pada ruangan yang berbeda. Jika semakin banyak ruangan yang dipakai maka biaya pengeluaran akan semakin besar. Oleh karena itu, jumlah minimal ruangan yang diperlukan untuk menempatkan anak-anak tersebut perlu diketahui. Permasalahan mencari ruangan minimum yang dipakai dapat diatasi dengan teknik pewarnaan graf yaitu pewarnaan simpul.

2 e2

e4 e5

e3 4

3

e6 e7

5

Gambar 1. Graf G1 Pada contoh graf di atas, sisi e4 dan e5 dinamakan sisi ganda karena sisi ini menghubungkan simpul yang sama yaitu, simpul 2 dan 3. Sedangkan sisi e1 dinamakan sisi gelang karena berawal dan berakhir pada simpul yang sama, yaitu simpul 1. Graf dapat dibedakan berdasarkan ada tidaknya sisi ganda dan sisi gelang, yaitu graf sederhana dan graf taksederhana. 1.Graf Sederhana (simple graph) Graf sederhana adalah graf yang tidak memiliki sisi ganda maupun sisi gelang. 2.Graf tak-Sederhana (unsimple-graph) Graf tak-sederhana adalah graf yang memiliki sisi ganda ataupun sisi gelang. Graf tak-sederhana terbagi atas graf ganda dan graf semu. Graf ganda adalah graf yang mengandung sisi ganda sedangkan graf semu adalah graf yang mengandung sisi gelang.

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2012/2013

e1 2 1

e2

3

e3 e1

e3 2

9.

e4

e4

memiliki lintasan dari v1 ke v2. Graf berbobot Graf berbobot adalah graf yang sisinya memiliki nilai (bobot).

1 e2 3

e5

4

(a) (b) Gambar 2. (a) Graf Semu, (b) Graf Ganda Graf juga bisa dibedakan berdasarkan orientasi arah pada sisi, yaitu graf tak-berarah dan graf berarah. 1. Graf tak-berarah (undirected graph) Graf ini tidak memiliki arah pada sisinya sehingga urutan pasangan simpul pada sisi tidak perlu diperhatikan, yaitu (v1,v2) = (v2,v1). 2. Graf berarah (directed graph) Grag berarah adalah graf yang pada setiap sisinya memiliki arah. Pada graf berarah, sisi (v1,v2) ≠ (v2,v1).

B. Pewarnaan Graf (Graph Colouring) Pewarnaan graf dibagi atas tiga, yaitu: 1. Pewarnaan Simpul Pewarnaan simpul/titik adalah memberi warna pada simpul-simpul pada graf sehingga dua simpul yang bertetanggaan memiliki warna yang berbeda. 2

1

3

4

5

6

Gambar 4. Pewarnaan simpul pada graf 2.

Pewarnaan Sisi Pewarnaan sisi pada graf yaitu memberi warna semua sisi graf sehingga semua sisi yang bertetanggaan memiliki warna yang berbeda.

(a) (b) Gambar 3. (a) Graf tak-berarah, (b) Graf berarah Ada beberapa terminologi graf, yaitu: 1. Bertetangaan (Adjacent) Dua buah simpul dikatakan bertetanggaan jika simpul tersebut dihubungkan dengan sebuah sisi. 2. Bersisian (Incidency) Suatu sisi e1 dikatakan bersisian dengan simpul v1 dan v2 jika sisi tersebut menghubungkan v1 dan v2, yaitu e1=(v1, v2). 3. Simpul Terpencil (Isolated Vertex) Simpul terpencil adalah simpul yang tidak memiliki sisi yang bersisian dengan simpul tersebut. 4. Graf Kosong (Null Graph) Graf kosong adalah graf yang hanya terdiri dari simpul dan himpunan sisinya kosong. 5. Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. 6. Lintasan (Path) Lintasan dari simpul awal v0 ke simpul tujuan vn merupakan barisan selang-seling antara simpul dan sisi yang dilewatinya berbentuk v1, e1, v2, e2 .. vn. 7. Siklus atau Sirkuit Suatu lintasan dinamakan sirkuit atau siklus jika berawal dan berakhir pada simpul yang sama. 8. Terhubung Graf tak berarah G dikatakan terhubung jika setiap pasang simpul v1 dan v2 dalam himpunan V

Gambar 5. Pewarnaan sisi pada graf 3.

Pewarnaan Daerah/Wilayah Pewarnaan wilayah yaitu mewarnai daerah sehingga tidak ada daerah yang berdekatan memiliki warna yang sama.

Gambar 6. Pewarnaan wilayah Dalam pewarnaan graf, kita tidak hanya mewarnai titik, sisi atau wilayah yang bertetanggaan dengan warna yang berbeda saja. Namun, kita menginginkan jumlah warna minimal yang bisa digunakan untuk mewarnai graf tersebut. Jumlah warna minimum yang digunakan untuk

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2012/2013

mewarnai graf disebut dengan bilangan kromatik graf G yang disimbolkan dengan χ(G). Bilangan kromatik pada contoh graf di gambar 3 adalah 2. Pada graf-graf tertentu, bilangan kromatik suatu graf dapat langsung ditentukan, seperti: 1. Graf kosong Nn memiliki (G) = 1, 2. Graf lengkap Kn memiliki (G) = n, 3. Graf bipartit Km,n mempunyai (G) = 2, 4. Graf lingkaran dengan n ganjil memiliki (G) = 3, 5. Graf lingkaran dengan n genap maka (G) = 2. Pewarnaan titik pada graf dapat menggunakan algoritma Welch–Powell. Algoritma Welch-Powell dijabarkan dalam beberapa langkah berikut. 1. Urutkan simpul—simpul berdasarkan jumlah derajatnya menurun. Dalam kasus tertentu, jumlah derajat bisa sama. 2. Beri warna pada simpul dengan derajat yang terbesar. 3. Beri warna yang sama dengan langkah kedua terhadap simpul lain yang tidak bertetanggaan dengan simpul sebelumnya. 4. Ulangi langkah kedua dan ketiga dengan menggunakan warna yang berbeda sampai semua simpul telah habis diwarnai.

3. C P 4. D P 5. E P 6. F P 7. G P 8. H L 9. I L 10. J L 11. K L 12. L L 13. M L 14. N L 15. O L Tabel 1. List anak-anak di tempat satu waktu tertentu

Permasalahan yang telah disebutkan di atas dapat diselesaikan dengan teknik pewarnaan graf. Teknik pewarnaan yang dipakai adalah pewarnaan simpul. Untuk menentukan jumlah ruangan minimal maka kita mencari bilangan kromatik dari graf yang merepresentasikan hubungan anak-anak tersebut. Langkah pertama yang dilakukan adalah merepresentasikan anak-anak tersebut dengan simpul.

III. PENERAPAN PEWARNAAN GRAF PADA PEMBAGIAN RUANGAN DI TEMPAT PENITIPAN ANAK Pada suatu tempat penitipan anak X, Pemilik penitipan anak menetapkan aturan-aturan untuk penempatan anakanak. Aturan ini diterapkan untuk mengurangi pertengkaran atau perkelahian yang mungkin terjadi di antara anak-anak tersebut. Dalam kasus terterntu, anak kembar ditempatkan dalam ruangan yang berbeda karena bisa saling merebutkan mainan yang sama. Begitupun anak laki-laki yang selisih usianya satu tahun. Anak perempuan yang selisih usianya lebih dari tiga tahun juga ditempatkan pada ruangan yang berbeda. Adanya aturan–aturan tersebut, maka dimungkinkan ruangan yang dipakai akan cukup banyak. Jika memakai banyak ruangan maka biaya pengeluaran dalam satu hari akan lebih besar. Dengan kapasitas ruangan maksimal menampung enam orang anak, pemilik penitipan anak ini ingin mengetahui jumlah minimum ruangan yang diperlukan untuk menempatkan anak-anak tersebut. Dengan semakin minimum ruangan yang dipakai, maka biaya pengeluaran pun akan semakin minimum. Dibawah ini merupakan contoh list anak yang dititipkan ke penitipan anak pada satu waktu tertentu. Keterangan tambahan bahwa A dan B serta F dan N adalah anak kembar. No 1. 2.

Nama A B

Jenis Kelamin P P

6 7 8 10 11 6 6 7 8 9 9 10 10 penitipan anak dalam

A

B

G

H L N

D

C

F

E I

M

J N

K J K O K

Gambar 7. Simpul-simpul yang merepresentasikan anak Langkah kedua adalah membuat list anak-anak yang tidak dapat ditempatkan dalam satu ruangan yang sama. Dari list yang dibuat, lalu dibentuk grafnya. Anak-anak yang tidak dapat ditempatkan dalam satu ruangan yang sama dibuat sisi yang menghubungkan simpul yang merepresentasikan anak tersebut.

Usia (Tahun) 6 6

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2012/2013

No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

Anak A B C D F G H I J K L M

Tidak seruangan dengan B,F, G A,F,G F,G G A,B,C,N A,B,C,D J J H,I,K J,L,M K,M,N,O K,N,O

13. N F,L,M, 14. O L,M Tabel 2. List anak-anak yang tidak bisa seruangan A ditempatkan di ruangan yang berbeda dengan dengan B, F, dan G. Oleh karena itu, pada simpul A dibuat sisi dengan B, F, dan G. Setiap simpul anak yang tidak seruangan dengan anak yang lain dihubungkan dengan sisi sampai semua simpul selesai. Dalam graf pada gambar 7, simpul E merupakan simpul terpencil. Ini berarti simpul E tidak terhubung dengan simpul manapun. Ini menandakan E terbebas dari sisi manapun. Langkah ketiga adalah memberi warna pada graf tersebut. Dengan menggunakan algoritma Welch–Powell, pemberian warna graf tersebut dibagi atas beberapa tahap. Tahap pertama, simpul-simpul tersebut diurutkan menurun berdasarkan jumlah derajatnya. Lalu, memilih satu warna bebas yaitu biru untuk mewarnai simpul dengan derajat terbesar yaitu F. Selanjutnya, mewarnai simpul lain yang tidak bertetanggaan dengan F dengan warna biru yaitu simpul G. Simpul-simpul lain yang tidak bertetanggaan dengan simpul-simpul yang berwarna biru, yaitu L, M, J, dan E juga diwarnai biru. C E G

F

B

A

D

N L O

H J

K

M

I Gambar 8. Pemberian warna biru pada graf Selanjutnya,mengulangi algoritma Welch–Powell dengan memilih warna kuning untuk mewarnai simpul belum berwarna yang memiliki derajat terbesar, yaitu simpul A. Simpul-simpul lain yang dibertetanggaan dengan A diberi warna kuning. Simpul-simpul tersebut adalah N,K,C,O, dan D. Simpul H dan I tidak bisa diberi warna kuning karena satu warna hanya bisa dipakai untuk enam buah simpul. Ini disebabkan dalam satu ruangan hanya berisi maksimal enam orang anak.

C E G

F

B

A

D

N L O

H J

K

M

I Gambar 9. Pemberian warna kuning pada graf Setelah pewarnaan simpul dengan warna kuning selesai, masih ada simpul-simpul yang belum diwarnai. Langkahlangkah diulangi lagi dengan mengambil warna hijau untuk mewarnai simpul B. Simpul-simpul lain yang bisa diwarnai hijau adalah simpul H dan I. Pewarnaan graf telah selesai karena semua simpul telah diberi warna. Hasil akhir dari pewarnaan berdasarkan algoritma Welch– Powell ditunjukkan dengan tabel dan graf di bawah ini. No. Simpul Derajat Warna 1. F 4 Biru 2. G 4 Biru 3. A 3 Kuning 4. B 3 Hijau 5. N 3 Kuning 6. L 3 Biru 7. M 3 Biru 8. K 3 Kuning 9. J 3 Biru 10. C 2 Kuning 11. O 2 Kuning 12. D 1 Kuning 13. H 1 Hijau 14. I 1 Hijau 15. E 0 Biru Tabel 3. Hasil pewarnaan pada simpul dengan alogritma Welch–Powell.

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2012/2013

PERNYATAAN C E G

F

B

Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 16 Desember 2013

A

D

N L O

H

Susanti Gojali - 13512057 J

K

M

I Gambar 10. Pewarnaan Simpul pada graf Setelah memberi warna pada graf, dapat diketahui bahwa bilangan kromatik graf tersebut adalah (G) = 3. Ini menunjukkan bahwa jumlah ruangan minimal yang dibutuhkan sebanyak tiga ruangan, dengan masing-masing tiap ruangan berisi anak-anak sebagai berikut. No Ruangan Anak-anak 1. I E,F,G,J,L,M 2. II A,C,D,K,N,O 3. III B,H,I Tabel 4. Penempatan ruangan untuk anak-anak

V. KESIMPULAN Teori graf memiliki banyak penerapan dalam berbagai bidang, salah satunya permasalahan yang ditemui di tempat penitipan anak. Permasalahan dalam tempat penitipan anak ini adalah mencari jumlah ruangan minimum. Untuk mencari jumlah ruangan minimum dapat digunakan teknik pewarnaan graf yaitu pewarnaan simpul. Dalam salah satu kasus yang telah disebutkan, jumlah minimum ruangan yang dibutuhkan adalah 3.

REFERENCES [1] [2]

Munir, Rinaldi, Diktat Kuliah IF2120, Matematika Diskrit, Edisi Keempat, Program Studi Teknik Informatika, STEI, ITB, 2006 Kenneth H, Rosen, Discrete Mathematic and Application to Computer Science 7th edition , Mc Graw-Hill 2007.

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2012/2013