TEORI GRAF
PEWARNAAN GRAF

Disusun oleh:

  Devia Nurhaliza
5520116036
       


JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS SURYAKANCANA
2018
BAB I
PENDAHULUAN

A.      Latar Belakang
Matematika memiliki beberapa pokok bahasan, salah satunya adalah graf. Wilson & Watkins (1990: 10) menyatakan, graf terdiri dari himpunan tak kosong dari elemen-elemen yang disebut simpul dan daftar pasangan tak berurutan dari elemen-elemen tersebut yang dinamakan rusuk. Graf biasa digunakan sebagai visualisasi obyek-obyek agar lebih mudah dimengerti. Contoh graf dalam kehidupan sehari-hari antara lain: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian  listrik, dan lain-lain.
Graf merupakan salah satu cabang ilmu Matematika yang dapat diterapkan baik dalam Ilmu Matematika maupun dalam kehidupan sehari-hari. Salah satu topik pada graf adalah pewarnaan graf. Pewarnaan graf dibagi menjadi dua macam, yaitu pewarnaan simpul dan pewarnaan rusuk. Akan tetapi, jika tidak diberikan kualifikasinya, pewarnaan graf diartikan sebagai pewarnaan simpul. Mewarnai sebuah graf berarti memberi warna pada setiap simpul dan rusuk graf sedemikian hingga simpul dan rusuk yang berkaitan dapat diwarnai dengan warna yang berbeda.
Misalkan G  adalah graf tanpa loop, banyaknya warna yang digunakan untuk mewarnai simpul graf G sedemikian sehingga simpul yang berikatan berlainan warna dinyatakan dengan k-pewarnaan. Jika G  memiliki k-pewarnaan, maka  G  dikatakan dapat diwarna dengan k warna. Pada pewarnaan  simpul,  jumlah  warna  yang  boleh dipergunakan  haruslah  seminimal  mungkin. Jumlah  warna  paling  minimum  yang  dapat diterapkan  pada Graph ini  sering  disebut  dengan angka kromatik (χ(G)). Salah satu metode yang digunakan untuk mewarnai graf adalah dengan menggunakan polinomial khromatik.
Pewarnaan graf dapat diaplikasikan pada berbagai permasalahan sehari-hari, misalnya penentuan jadwal ujian. Jadwal ujian ditentukan  sedemikian sehingga tidak ada mahasiswa yang memiliki dua mata kuliah yang diujikan pada waktu bersamaan. Contoh lainnya adalah saluran televisi ditentukan ke pemancar-pemancar, sedemikian sehingga tidak ada dua pemancar dapat beroperasi pada saluran yang sama dalam jarak tertentu.

B.       Rumusan Masalah
1.    Bagaimana penggunaan Algoritma Welsh dan Powel?
2.    Bagaimana cara menentukan banyaknya bilangan kromatik pada suatu graf?
3.    Apa perbedaan perwanan titik atau sisi suatu graph?

C.      Tujuan.
1.    Menentukan banyaknya bilangan kromatik pada suatu graf.
2.    menjelaskan pewarnaan titik suatu graph.
3.    menjelaskan pewarnaan sisi atau rusuk suatu graph.
4.    menjelaskan algoritma Welsh dan Powell dalam pewarnaan graph.


BAB II
LANDASAN TEORI

A.      Pengertian Graf
Graf adalah himpunan tak kosong yang terdiri dari himpunan simpul dan himpunan rusuk dengan himpunan simpul bukan merupakan himpunan kosong. Himpunan simpul dari G dinotasikan dengan V (G) dan himpunan rusuk dari G dinotasikan dengan E(G). Notasi graf: G(V, E) artinya graf G memiliki V simpul dan E rusuk.
Simpul-simpul pada graf dapat merupakan obyek sembarang seperti kota, nama orang, jenis buah, komponen alat elektronik dan sebagainya. Rusuk dapat menunjukkan hubungan sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain.

B.       Pewarnaan Graf
Pewarnaan graf terbagi menjadi dua macam yaitu pewarnaan simpul dan pewarnaan rusuk.
1.       Pewarnaan simpul  didefinisikan sebagai berikut :
Misalkan G adalah graf tanpa loop, k-pewarnaan untuk G menyatakan penggunaan sebanyak k-warna untuk simpul G  sedemikian hingga simpul-simpul yang berikatan mendapat warna yang berbeda. Jika G  memiliki k-pewarnaan, maka  G  dikatakan dapat diwarnai dengan  k-warna (Wilson dan Watkins, 1989: 235).
Berikut adalah contoh pewarnaan simpul pada graf  G .

Gambar 1. Pewarnaan Simpul pada Graf G


Gambar 1 (a), (b), dan (c) secara berturut-turut adalah 3-pewarnaan, 4-pewarnaan, dan 5-pewarnaan dari graf  G.
2.      Pewarnaan rusuk didefinisikan sebagai berikut :
Misal G adalah graf tanpa loop, k-pewarnaan rusuk untuk G  adalah pemberian  sebanyak k warna pada rusuk-rusuk G sedemikian hingga setiap dua rusuk yang bertemu dengan simpul yang sama mendapat warna berbeda. Jika G memiliki k-pewarnaan rusuk, maka rusuk graf G dikatakan dapat diwarnai dengan k warna (Wilson dan Watkins, 1989: 240).
Berikut adalah contoh pewarnaan rusuk pada graf G .
Gambar 2. Pewarnaan Rusuk pada Graf  G
Gambar 2 (a), (b), dan  (c) secara berturut-turut  adalah 4-pewarnaan rusuk, 5-pewarnaan rusuk, dan 6-pewarnaan rusuk dari graf G . Gambar 2 (d) bukan merupakan pewarnaan rusuk dari graf G , karena terdapat dua rusuk berwarna sama yang bertemu pada simpul yang sama.

3.      Bilangan kromatik didefiniskan sebagai berikut :
Indeks khromatik graph G adalah bilangan yang menyatakan minimum banyaknya warna yang diperlukan untuk mewarnai semua sisi graph G sedemikian hingga setiap dua sisi graph G yang terkait ke titik yang sama mendapatkan warna yang berbeda. Indeks khromatik diyatakan dengan c ’(G). Biasanya warna-warna yang digunakan untuk mewarnai sisi-sisi suatu graph dinyatakan dengan 1, 2, 3,…, k. c ’(G) = minimum

4.      Algoritma Welsh dan Powel
Algoritma ini memberikan cara mewarnai sebuah graph dengan memberi label titik-titiknya sesuai dengan derajatnya. Adapun langkah-lakah mewarnai sebuah graph menurut Welsh dan Powel adalah sebagai berikut :
1.        Urutkan titik – titik dari G dalam derajat menurun, d(v1) > d(v2) > d(v3) > . . . >d(Vn) (boleh memakai tabel)
2.        Gunakan warna pertama (I) untuk mewarnai titik pertama (yang mempunyai derajat tertinggi (v1)) dan titik yang tidak bertetangga dengan v1 )
3.        Gunakan warna ke dua (II) untuk mewarnai titik dengan derajat tertinggi berikutnya.
4.        Ulangi penambahan warna – warna sampai semua titik terwarnai.

BAB III
PEMBAHASAN

A.      Pewarnaan Simpul
Misalkan G adalah graf tanpa loop, k-pewarnaan untuk G menyatakan penggunaan sebanyak k-warna untuk simpul G  sedemikian hingga simpul-simpul yang berikatan mendapat warna yang berbeda. Jika G  memiliki k-pewarnaan, maka  G  dikatakan dapat diwarnai dengan  k-warna (Wilson dan Watkins, 1989: 235).
Sifat – sifat bilangan kromatik untuk pewarnaan simpul
1.        χ(G) = 1 jika dan hanya jika G adalah graf kosong.
2.        χ(G) ≥ 3 jika dan hanya jika G memiliki subgraph yang merupakan K3 atau C3
3.        χ(G) ≤ ∆(G)+1.
4.        χ(G) ≤ ∆(G), kecuali jika G adalah graf lengkap atau graf lingkaran dengan jumlah simpul ganjil.
5.        Untuk setiap graf planar, berlaku teorema 4 warna, yaitu χ(G) ≤ 4.
6.        Bila G’ adalah upagraph dari G, maka χ(G’) ≤ χ(G).
7.        Graf lengkap Kn memiliki χ(G)=n.
8.        Graf Lingkaran Cn memiliki χ(G)=2 bila n genap dan χ(G)=3 bila n ganjil.

9.        Graf Teratur berderajat n selalu memiliki χ(G) ≤ n +1 sesuai sifat no 3 di atas.
10.    Graf Bipartit selalu bisa diwarnai dengan 2 warna.

biru

Merah
11.  Graf yang berupa pohon selalu dapat diwarnai dengan 2 warna.
Algoritma Welsh dan Powel
Kita dapat menggunakan Algoritma Welch-Powell untuk mewarnai suatu Graf, dengan banyak warna minimal sebagi berikut :
1.      Urutkan semua simpul berdasarkan derajatnya, dari derajar besar ke derajat kecil.
2.      Ambil warna pertama (misalnya merah), warnai simpul pertama yang sudah kita urutkan berdasarkan derajatnya tadi. Kemudian warnai simpul berikutnya yang tidak berdampingan dengan simpul pertama tadi dengan warna yang masih sama (merah).
3.     Kemudian kita lanjutkan dengan warna kedua, dan seterusnya, sampai semua simpul telah diberi warna.
Contoh : mewarnai simpul Graf menggunakan algoritma Welch-Powell
1.      Urutkan simpul berdasarkan derajatnya dari besar ke kecil : Simpul berderajat terbesar adalah E, yaitu 5 (mempunyai 5 ruas) kemudian simpul C berderajat 4, B,D,F masing-masing berderajat 3 dan A,H,G masing-masing berderajat 2. Jadi Urutannya adalah : E,C,B,D,F,A,H,G
2.      Ambil warna pertama, misalnya Merah. Beri warna Merah simpul E (karena E adalah simpul urutan pertama).Kemudian cari simpul yang tidak berdampingan dengan simpul E, beri warna yang sama (merah)
Kita berikan warna yang sama pada simpul A dan G dengan warna simpul E yaitu merah karena Simpul A dan G tdk berdampingan dengan simpul E
3.      Sehingga didapat urutan simpul yang belum diberi warna sbb : C,B,D,F,H
4.      Ambil warna kedua, misalnya Biru, warnai simpul C ( karena simpul C sekarang ada diurutan pertama). Kemudian cari simpul yang tidak berdampingan dengan simpul C, beri warna yang sama (Biru).
Kita berikan warna yang sama pada simpul D dan H dengan warna simpul C yaitu biru karena Simpul D dan H tidak berdampingan dengan simpul C
5.      Sehingga didapat urutan simpul yang belum diberi warna sbb : B,F
6.      Ambil warna ketiga, misalnya Hijau, warnai simpul B dan F.
7.      Pewarnaan telah selesai, Graf merupakan Graf berwarna 3. Jadi K(G) = 3

B.       Pewarnaan Rusuk
Pewarnaan garis atau rusuk pada suatu graph adalah penentuan warna rusuk-rusuk suatu graph sehingga setiap rusuk yang berdekatan mendapatkan warna yang berbeda. Ukuran keberwarnaan suatu graph didefinisikan sama dengan ukuran keberwarnaan titik, yaitu mengacu kepada banyaknya warna yang memungkinkan sehingga setiap rusuk yang berdekatan mendapat warna yang berbeda. Jumlah warna minimal yang dapat digunakan untuk mewarnai rusukrusuk dalam suatu graph G disebut bilangan khromatik G.
Sifat – sifat bilangan kromatik untuk pewarnaan simpul
1.        ∆(G ) ≤ χ(G) ≤ ∆(G)+1.
Derajat maksimum titik dari graph G1 , G2 , dan G3 adalah 3 Bilangan khromatiknya adalah 3.
2.        χ (Kn ) = n, jika n ganjil dan n > 1
3.        χ (Kn ) = n-1, jika n genap
4.        χ(G)  = ∆(G)


BAB IV
PENUTUP

A.      KESIMPULAN
Beberapa kesimpulan yang dapat ditarik dari penulisan makalah ini adalah:
1.         Masalah pewarnaan graf merupakan masalah yang banyak digunakan untuk memodelkan masalah di berbagai bidang.
2.         Beberapa jenis graf yang memiliki keteraturan dapat ditentukan bilangan kromatiknya secara langsung dengan menggunakan sifat – sifatnya.
3.         Terdapat beberapa algoritma yang dapat digunakan untuk menyelesaikan masalah pewarnaan graf. Salah Satunya Algoritma Welsh dan Powel untuk mewarnai suatu Graf, dengan banyak warna minimal .



DAFTAR PUSTAKA

Munir, Rinaldi, Diktat Kuliah IF 2153, Matematika Diskrit, Edisi Keempat, Program Studi Teknik Informatika, STEI, ITB, 2006.

Budiman, Hengki, Penerapan Graph Colouring Untuk Merencanakan Jadwal, Program Studi Teknik Informatika, STEI, ITB, 2010.

Devadas, Srini dan Eric Lehman. 2005. Graph Teory II. Diakses dari http://files.myopera.com/m4th03/files/vertex_coloring_graph.pdf  

Maaruf, Faridah. ----. Pengenalan Teori Graf. Diakses dari http://books.google.co.id/books?id=teQ1aMau9i8C&pg=PA113&lpg=PA113&dq=cara+menentukan+polinomial+kromatik&source=bl&ots=p9KCYF0gog&sig=yhqKLURDCZAsqHttx8zDlfdQ5zY&hl=id&sa=X&ei=fTqgUKvklcqVmQW4yYHQCA&ved=0CBoQ6AEwAA#v=onepage&q&f=false

Priatna, Nanang. ----. Pewarnaan Graf. Diakses dari http://file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/196303311988031-NANANG_PRIATNA/Pewarnaan_Graph.pdf




Tolong beri dukungan dengan cara Komen dan Bagikan Postingan ini, Agar Minvi selalu semangat update informasi yang lain 😄 

Terimakasih semoga bermanfaat.