Pewarnaan Graf Menggunakan Bahasa C - Matematika Diskrit

Graph Coloring

Pewarnaan graf adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu.
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.

#include <stdio.h>

#define MAX_NUM_VERTICES 20 // jumlah vertex maksimum
#define MAX_NUM_EDGES 2 * MAX_NUM_VERTICES // jumlah edge maksimum

int numVertices; // jumlah vertex tersimpan
int numEdges; // jumlah edge tersimpan
int chromNumber = 0; // bilangan kromatik

int edges[MAX_NUM_EDGES][2];
int color[MAX_NUM_VERTICES];

int VerticesConnected(int, int);
int CountHomogenEdges();
void ArrangeColor();

int main()
{
int i;
printf("Jumlah Vertex: ");
scanf_s("%d", &numVertices);
printf("Jumlah Edge  : ");
scanf_s("%d", &numEdges);

printf("\n> Vertex\n");
for (i = 0; i < numVertices; i++)
{
// semua vertex diberikan warna inisial: 0
printf("  + vertex[%d]\n", i);
color[i] = 0;
}

printf("\n> Edge\n");
for (i = 0; i < numEdges; i++)
{
printf("  + edge[%d]: vertex ", i);
scanf_s("%d %d", &edges[i][0], &edges[i][1]);
}

printf("\n> Mewarnai Vertex\n");

ArrangeColor();

for (i = 0; i < numVertices; i++)
printf("  + vertex[%d]\tcolor: %d\n", i, color[i]);
printf("  Chromatic Number: %d\n\n", chromNumber);

system("pause");

return 0;
}

// fungsi: VerticesConnected
//   Memeriksa apakah dua vertex terhubung.
//   Pemeriksaan dilakukan dengan menelusuri seluruh edge.
// parameter:
//   - v1: index vertex 1
//   - v2: index vertex 2
// kembalian: int
//   0: FALSE, bila 2 vertex tidak terhubung
//   1: TRUE, bila 2 vertex terhubung

int VerticesConnected(int v1, int v2)
{
int i;
for (i = 0; i < numEdges; i++)
if ((edges[i][0] == v1 && edges[i][1] == v2) || (edges[i][0] == v2 && edges[i][1] == v1))
return 1;

return 0;
}

// fungsi: CountHomogenEdges()
//   Menghitung ada berapa banyak edge yang memiliki 2 vertex dengan varna sama,
//   dengan cara menelusuri dan memeriksa seluruh edge.
// parameter: void
// kembalian: int jumlah

int CountHomogenEdges()
{
int i;
int c = 0;
for (i = 0; i < numEdges; i++)
if (VerticesConnected(edges[i][0], edges[i][1]) && color[edges[i][0]] == color[edges[i][1]])
c++;

return c;
}

// fungsi: ArrangeColor()
//   yaitu dengan langkah:
//   1. Mewarnai seluruh vertex dengan chromatic number = 1, artinya pada langkah ini
//      seluruh vertex memiliki warna yang sama.
//   2. Menaikkan chromatic number, sehingga ada kemungkinan 2 warna yang bisa digunakan.
//      cek seluruh vertex, bila ditemukan dalam 1 edge ditemukan vertex dengan warna sama
//      ganti salah satu vertex dengan warna yang baru.
//   3. Lakukan langkah no: 2 sampai seluruh vertex yang terhubung dalam edge tidak memiliki
//      warna sama.
// parameter: void
// kembalian: void

void ArrangeColor()
{
int i, j;

// langkah 1:
// isikan semua vertex dengan warna yang sama
chromNumber++;
for (i = 0; i < numVertices; i++)
color[i] = chromNumber;

// langkah berikutnya:
// jika edge dengan 2 vertex-nya memilik warna sama jumlahnya > 0
// lakukan perulangan untuk pewarnaan baru.
while (CountHomogenEdges() > 0)
{
chromNumber++;
for (i = 0; i < numVertices - 1; i++)
for (j = i + 1; j < numVertices; j++)
if (VerticesConnected(i, j) && color[i] == color[j])
color[j] = chromNumber;
}
}

TEKNIK INFORMATIKA UNIVERSITAS UDAYANA

Tweet

Postingan terkait:

— Sabtu, 02 Juni 2018 — 1 Comment — Algoritma dan Pemrograman Dasar, Matematika Diskrit