|
Here is a real life problem. How can we paint the countries in a map that no same color should be neighbor with as little colors as possible? This method can be used to decide how many different colors will be used.
The Algorithm  
Pascal Source Code Used Variables in program: A[n,n] : Stores relations between nodes. C[]: Stores color letters B[]: Stores colored nodes. Element 1: 1'rst node Element 2: 2'nd node .. .. S[]:array holds 0(zero)s in every line. k | Red | m | Blue | y | Green | s | Yellow | t | Orange | b | White | f | |
Program Graf_coloring;
uses crt;
const
c:array[1..7] of char=('k','m','y','s','t','b','f');
var
a:array[1..7,1..7]of integer;
b:array[1..7]of string[5];
s:array[1..7]of integer;
i,j,k,n,r,t,p,f,d:integer; ch:char;
{ "a" relation matrix
"b" colored elements' array
"c" coloring array
"s" array holds 0(zero)s in every line
}
Begin
clrscr;
write('Relation matrix's size:');readln(n);
writeln('Write the relation matrix...');
i:=1;
gotoxy(5,3);
repeat
write(i:4);i:=i+1;
until i=n+1;
for i:=1 to n do
begin
k:=3;
for j:=1 to n do
begin
gotoxy(k+4,i+3);read( a[i,j] );k:=k+4;
end;
end;
t:=0;
for i:=1 to n do
begin {2}
t:=t+1;
f:=0;
j:=i;
if b[i]='' then
begin
while j < n do
begin
if a[i,j]=0 then
begin {1}
k:=1;
if (b[j]='') then k:=n+1;
if k>n then
begin
b[j]:=c[t];{generating coloring array}
if j<>i then
begin
f:=f+1;
s[f]:=j;{ holds 0's place number }
end;
end
else j:=n;
end;{1}
end;
if f<>0 then { controlling matrix and changing colored array'}
begin
for k:=1 to f-1 do
for d:=k+1 to f do
begin
if a[s[k],s[d]]=1 then b[s[d]]:='';
end;
end;
end
else t:=t-1;
end; {2}
writeln('Colored elements and their colors');
for i:=1 to n do
begin
for j:=1 to n do
begin
if b[i]=c[j] then
case j of
1:writeln(i,' īs color is red');
2:writeln(i,' īs color is blue');
3:writeln(i,' īs color is green');
4:writeln(i,' īs color is yellow');
5:writeln(i,' īs color is orange');
6:writeln(i,' īs color is white');
end;
end;
end;
repeat ch:=readkey until ch=#27;
end.
Sample Executions 1)
Relation matrix's size:7
Write the relation matrix... 1 2 3 4 5 6 7 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Colored elements and their colors 1 īs color is red 2 īs color is blue 3 īs color is green 4 īs color is yellow 5 īs color is blue 6 īs color is red 7 īs color is orange 2)
Relation matrix's size:7
Write the relation matrix... 1 2 3 4 5 6 7 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Colored elements and their colors 1 īs color is red 2 īs color is red 3 īs color is red 4 īs color is blue 5 īs color is blue 6 īs color is blue 7 īs color is blue
|
Studies 
