TUGAS PRAKTIKUM
GRAPH COLORING
“IMPLEMENTASI GRAPH
COLORING DALAM PEMETAAN
DAERAH
KABUPATEN SERDANG BEDAGAI”
Oleh
Kelompok 5 :
Andri
Pebriyan Noor A1314006
Dimas
Ariyanto A1314012
Duwi
Sawitri A1314014
Eka
Aprilliani A1314015
Hartati A1314021
Khusnul
Khotimah A1314029 |
|
 |
PROGRAM
STUDI TEKNIK INFORMATIKA
POLITEKNIK
NEGERI TANAH LAUT
TAHUN
AJARAN 2014/2015
1.
Teori Graph
Secara kasar, graph adalah suatu
diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat.
Dalam kehidupan sehari-hari, graph digunakan untuk menggambarkan
berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi
objek-objek agar lebih mudah dimengerti.
Teori Graph merupakan cabang ilmu
matematika diskrit yang banyak penerapannya dalam berbagai bidang ilmu seperti engineering,
fisika, biologi, kimia, arsitektur, transportasi, teknologi komputer, ekonomi,
sosial dan bidang lainnya. Teori Graph juga dapat diaplikasikan untuk
menyelesaikan persoalan-persoalan, seperti Travelling Salesperson Problem,
Chinese Postman Problem, Shorest Path, Electrical Network
Problems, Seating Problem serta Graph Coloring.
2.
Graph Coloring
Suatu
linier graph atau sederhana G = (V,E) terdiri atas himpunan benda V = {v1, v2, . . .} disebut
vertex, dan himpunan E = {e1, e2, . . . }, yang elemen-elemennya disebut
edge sehingga setiap edge ek diidentifikasikan dengan pasangan
tak berurut vertex (vi, vj).
Gambar
contoh Sebuah Graph
Sebuah
pewarnaan graph G adalah sebuah pemetaan warna-warna ke vertises dari
G sedemikian hingga vertex adjacency atau simpul yang berdampingan
mempunyai warna yang berbeda. Graph planar G dikatakan berwarna n jika
terdapat sebuah pewarnaan dari G yang menggunakan n warna. Jumlah warna minimum
yang diperlukan untuk mewarnai G disebut bilangan chromatic dari G.
Ada
tiga macam pewarnaan graph, yaitu pewarnaan vertex, pewarnaan edge,
dan pewarnaan wilayah (region).
Pewarnaan
simpul (Vertex Coloring) suatu graph adalah pemberian warna terhadap
vertex sedemikian hingga dua vertex yang berdampingan mempunyai
warna yang berlainan. Sebuah vertex dapat diberikan sembarang warna
asalkan warna yang diberikan berbeda dengan vertex yang berdekatan
dengannya. Dikatakan G berwarna n, bila terdapat pewarnaan dengan menggunakan n
warna. Jumlah minimum warna yang dibutuhkan disebut bilangan khromatis dari G,
ditulis K(G).
3.
Kasus “Implementasi graph coloring dalam
pemetaan daerah kabupaten serdang bedagai”
Didalam Kasus Daerah Kabupaten
Serdang Bedagai yang terdiri dari 17 kecamatan dapat direpresentasikan menjadi
suatu graph dengan merepresentasikan batas-batas wilayah sebagai edge
dan perpotongan antar batas wilayah sebagai vertex.
Gambar
Graph Kabupaten Serdang Bedagai, yaitu
masing-masing
kecamatan
diwakilkan oleh satu vetrex
a. Source Code
|
#include <cstdlib>
#include <iostream>
using namespace std;
// inisialisai
const int MAX = 17;
int
a[17][17]={{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0},
{0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0},
{0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,1,1,0,1,0,0,0,1,1,0,0},
{0,0,0,0,0,0,1,0,1,0,1,1,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0},
{0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}};
int color[MAX];
int degree[MAX];
int NN[MAX];
int NNCount;
int unprocessed;
void Coloring();
void GetInput();
void Init();
int MaxDegreeVertex();
void scannedInit(int
scanned[MAX]);
void UpdateNN(int
ColorNumber);
int FindSuitableY(int
ColorNumber, int& VerticesInCommon);
int MaxDegreeInNN();
void PrintOutput();
void Coloring()
{
int x,y;
int ColorNumber = 0;
int VerticesInCommon = 0;
while (unprocessed>0)
{
x = MaxDegreeVertex();
ColorNumber ++;
color[x] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
while (NNCount>0)
{
y = FindSuitableY(ColorNumber,
VerticesInCommon);
if (VerticesInCommon == 0)
y = MaxDegreeInNN();
color[y] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
}
}
}
void GetInput()
{
// cout<<"Masukkan banyak data
: ";
// cin >> n;
//cout<<"Masukkan hubungan
graph : \n";
for (int i=0; i < 17; i++){
for (int j=0; j < 17; j++){
// cout<<"Simpul
"<<i+1<<" - "<<j+1<<" : ";
cin >> a[i][j];
}
}
}
void Init()
{
for (int i=0; i < 17; i++)
{
color[i] = 0;
degree[i] = 0;
for (int j = 0; j < 17; j++)
if (a[i][j] == 1)
degree[i] ++;
}
NNCount = 0;
unprocessed = 17;
}
int MaxDegreeVertex()
{
int max = -1;
int max_i;
for (int i =0; i < 17; i++)
if (color[i] == 0)
if (degree[i]>max)
{
max = degree[i];
max_i = i;
}
return max_i;
}
void scannedInit(int
scanned[MAX])
{
for (int i=0; i < 17; i++)
scanned[i] = 0;
}
void UpdateNN(int
ColorNumber)
{
NNCount = 0;
for (int i=0; i < 17; i++)
if (color[i] == 0)
{
NN[NNCount] = i;
NNCount ++;
}
for (int i=0; i < 17; i++)
if (color[i] == ColorNumber)
for (int j=0; j < NNCount;
j++)
while (a[i][NN[j]] == 1)
{
NN[j] = NN[NNCount - 1];
NNCount --;
}
}
int FindSuitableY(int
ColorNumber, int& VerticesInCommon)
{
int temp,tmp_y,y;
int scanned[MAX];
VerticesInCommon = 0;
for (int i=0; i < NNCount; i++)
{
tmp_y = NN[i];
temp = 0;
scannedInit(scanned);
for (int x=0; x < 17; x++)
if (color[x] == ColorNumber)
for (int k=0; k < 17; k++)
if (color[k] == 0
&& scanned[k] == 0)
if (a[x][k] == 1
&& a[tmp_y][k] == 1)
{
temp ++;
scanned[k] = 1;
}
if (temp > VerticesInCommon)
{
VerticesInCommon = temp;
y = tmp_y;
}
}
return y;
}
int MaxDegreeInNN()
{
int tmp_y;
int temp, max = 0;
for (int i=0; i < NNCount; i++)
{
temp = 0;
for (int j=0; j < 17; j++)
if (color[j] == 0 && a[NN[i]][j]
== 1)
temp ++;
if (temp>max)
{
max = temp;
tmp_y = NN[i];
}
}
if (max == 0)
return NN[0];
else
return tmp_y;
}
void PrintOutput()
{
cout<<"\n\n";
for (int i=0; i < 17; i++)
cout << "Vertex "
<< i+1
<< " warna "
<< color[i] << endl;
}
int main(int argc, char
*argv[])
{
system("color fD");
system("title Program Graph Coloring -
22 Juni 2015 - KhusnulK983.blogspot.com");
awal:
GetInput();
Init();
Coloring();
PrintOutput();
cout<<"\nIngin mengulang ?
(y/n) : ";
char p;
cin>>p;
if(p=='y') {
system("cls");
goto awal;
}
else return EXIT_SUCCESS;
}
|
b. Hasil
Penjelasan tentang fungsi-fungsi
pada source code diatas
1.
Dalam program ini diperlukan beberapa library yaitu :
#include<stdio.h>
#include <iostream>
2.
Fungsi
variabel kita juga buat untuk memberikan keterangan pada setiap fungsi yang
kita buat. Seperti:
void Coloring();
void GetInput();
void Init();
int MaxDegreeVertex();
void scannedInit(int scanned[MAX]);
void UpdateNN(int ColorNumber);
void PrintOutput();
3.
Untuk merepresentasikan Graph Kedalam array matriks
maka diinputkan terlebih dahulu sesuai dengan kasus pada makalah tersebut.
const int MAX = 17;
int
a[17][17]={{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0},
{0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0},
{0,0,0,1,0,1,0,0,1,1,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,1,1,0,1,0,0,0,1,1,0,0},
{0,0,0,0,0,0,1,0,1,0,1,1,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0},
{0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}};
4.
Karena diinputkan terlebih dahulu array matriknya, maka
yang diperlukan selanjutnya adalah perulangan dalam pewarnaan Graph tersebut
untuk mengetahu warna-warna pada setiap Vertex.
void GetInput()
{
for
(int i=0; i < 17; i++){
for (int j=0; j < 17; j++){
cin >> a[i][j];
}
}
5.
Kemudia buat fungsi untuk Pewarnaannya.
void Coloring()
{
int x,y;
int ColorNumber = 0;
int VerticesInCommon = 0;
while (unprocessed>0)
{
x = MaxDegreeVertex();
ColorNumber ++;
color[x] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
while (NNCount>0)
{
y = FindSuitableY(ColorNumber,
VerticesInCommon);
if (VerticesInCommon == 0)
y = MaxDegreeInNN();
color[y] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
}
}
}
6.
Selanjutnya
membuat fungsi untuk menentukan Pewarnaan vertek yang mana saja yang kita
warnai, vertek mana saja yang tidak boleh sama warna. Yaitu dimulai dari vertek
1 sampai vertek 17.
void Init()
{
for (int i=0; i < 17; i++)
{
color[i] = 0;
degree[i] = 0;
for (int j = 0; j < 17; j++)
if (a[i][j] == 1)
degree[i] ++;
}
NNCount = 0;
unprocessed = 17;
}
7.
Selanjutnya, fungsi Keluaran
atau output. Apa yang dikeluarkan? Yaitu vertek mana saja yang diwarnai. Warna
dimulai dari Vertek 0 sampai 17 karena terdapat 17 kasus pada makalah tersebut
void PrintOutput()
{
cout<<"\n\n";
for (int
i=0; i < 17; i++)
cout
<< "Vertex " << i+1
<< " warna " << color[i] << endl;
}
8.
Kemudian terakhir fungsi untuk
pewarnaan teks saja pada tampilan aplikasi, disini kami menggunkan FD yang
artinya menggunakan warna ungu.. Banyak format-format warnanya seperti:
F0= black, F1 = Blue,
F2= Green, FA= Light Green, FB= Light Aqua, dst sesuai keinginan kita. Namun
apabila F dtinggal atau dihapus hanya angka atau huruf abjad maka bukan tulisan
yag diwarnai melainkan tampilan atau screen yang berubah.
int main(int argc, char *argv[])
{
system("color fD");
system("title Program graph coloring – 22
Juni 2015- KhusnulK983.blogspot.com”);
awal:
GetInput();
Init();
Coloring();
PrintOutput();
cout<<"\nIngin mengulang ? (y/n) : ";
char p;
cin>>p;
if(p=='y') {
system("cls");
goto awal;
}
else return EXIT_SUCCESS;
}
0 komentar:
Posting Komentar