Pengertian
Graf
Dalam matematika dan ilmu komputer, sebuah graf adalah
objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah
himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan
oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang
memenuhi syarat, di mana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf
digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau
simpul) yang digabungkan dengan kurva (garis atau sisi).
Pewarnaan Graf
Dalam sebuah
teori graf, metode pewarnaan graf merupakan
sebuah kasus khusus untuk pelabelansebuah
graf. Pewarnaan graf merupakan penambahanwarna
pada elemen sebuah graf itu sendiri.
Pewarnaan Simpul
Dalam menggunakan spesifikasi
yang lain, pewarnaansebuah graf sering disebut dengan pewarnaan dari simpul
graf itu sendiri. Pewarnaan simpul pada graf adalah memberi warna pada
simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul
bertetanggayang memiliki warna yang sama
Pewarnaan Sisi
Pewarnaan sebuah sisi graf,
pewarnaan sisi-sisinyasecara tepat berarti cara pemberian warna pada
garissedemikian rupa sehingga setiap garis yang bertumpuan pada titik yang
sama diberi warna yang berbeda. Pewarnaan sisi dengan warna-warna
(sebutsaja dengan variabel k) dinamakan sebagai pewarnaansisi k.
Pewarnaan Wilayah
Pewarnaan wilayah adalah pemberian warna padasetiap wilayah pada
graf sehingga tidak ada wilayah bersebelahan yang memiliki warna yang
sama.Pewarnaan wilayah ini diterapkan pada pewarnaan peta. Pada pewarnaan
peta, diberikan warna yang berbeda pada setiap propinsi yang saling bersebelahan. Dalam
mengerjakan pewarnaanwilayah, kita dapat menggunakap prinsip pewarnaansimpul
pada graf. Misalnya adalah masalah pewarnaan peta. Tiapwilayah pada peta
dinyatakan sebagai simpul graf.Sedangkan sisi menyatakan bahwa terdapat
duawilayah yang berbatasan langsung (disebut juga bertetangga).
Ada tiga macam
pewarnaan graf :
Pertama, pewarnaan titik (vertex coloring) yaitu memeberikan warna berbeda pada setiap titik yang bertetangga sehingga tidak ada dua titik yang bertengga dengan warna yang sama.
Kedua, pewarnna sisi (edge coloring), yaitu memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga memepunya warna yang sama.
Ketiga, pewarnaan bidang, yaitu memberikan warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama.
Contoh Pewaraan Graf
:
Gambar 1. Contoh graf
Pada gambar diatas, sisi e3 = (1,3) dan sisi e4 = (1,3) dinamakan
sisi-ganda (multiple edges atau parallel edges) karena kedua sisi tersebut
menghubungkan dua simpul yang sama, yaitu simpul 1 dan simpul 3. Sedangkan sisi
e8 = (3,3) dinamakan sisi gelang atau kalang (loop) karena ia berawal dan
berakhir pada simpul yang sama. Berdasarkan ada tidaknya gelang atau sisi ganda
pada suatu graf, maka graf dapat digolongkan menjadi dua jenis, yaitu graf
sederhana dan graf tak-sederhana.
Graf sederhana adalah graf yang tidak mengandung gelang maupun
sisi-ganda.
Gambar 2. Contoh graf sederhana
Sedangkan graf tak-sederhana adalah graf yang mengandung sisi ganda
atau gelang. Ada dua jenis graf-tak-sederhana, yaitu graf ganda (multigraph)
dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda.
Graf semu adalah graf yang mengandung gelang termasuk jika mempunyai sisi ganda
pada graf tersebut. Graf pada Gambar 1 merupakan salah satu contoh graf semu.
Gambar di bawah ini adalah graf ganda.
Gambar 3. Contoh graf ganda
Berikut ini beberapa terminologi dasar yang menyangkut tentang graf :
1. Bertetangga
Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila
keduanya terhubung langsung dengan sebuah sisi pada graf G.
2. Bersisian
Untuk sembarang sisi e = (vj,vk), sisi e dikatakan bersisian dengan
simpul vj dan simpul vk.
3. Simpul Terpencil
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian
dengannya. Atau, dapat juga simpul terpencil adalah simpul yang tidak satupun
bertetangga dengan simpul-simpul lainnya.
4. Graf Kosong
Graf kosong adalah graf yang himpunan sisinya merupakan himpunan
kosong. Dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul.
5. Derajat
Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang
bersisian dengan simpul tersebut.
6. Lintasan
Lintasan yang panjangnya n dan simpul awal v0 ke simpul tujuan vn di
dalam graf G ialah barisan selang-seling simpul-simpul dan sisi-sisi yang
berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn sedemikian sehingga i1 =
(v0,v1), e2 = (v1,v2), … , en = (vn-1,vn), adalah sisi – sisi dari graf G. 7.
Siklus atau Sirkuit
Lintasan yang berawal dan berakhir pada simpul yang sama disebut siklus
atau sirkuit. 8. Terhubung
Graf tak berarah G disebut graf terhubung jika untuk setiap pasang
simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v.
Referensi :
https://rahadikusuma.blogspot.co.id/2013/12/matematika-diskrit-pewarnaan-graf_30.html
Comments
Post a Comment