I.
Раскраска графов.
1.) Вершинная раскраска графа.
Пусть дан граф G=(X,E) – связный
граф.
• Определение №1: ( Вершинная
раскраска)
Отображение f: X(G)→ {1,
2,…, k}
называется вершинной
раскраской графа G.
• Определение №2:
( Правильная вершинная раскраска)
Вершинная раскраска называется правильной
если для любых 2-ух смежных вершин f(u) ≠ f(v).
f(u), f(v) – цвета вершин.
Очевидно, что при правильной
раскраске, в общем случае, возможно использование менее чем k различных цветов.
Если для графа G существует правильная
раскраска k-цветами, говорим, что граф G
k – раскрашиваемый.
• Определение №3:
( Хроматическое число)
Наименьшее значение k, при котором
существует правильная раскраска вершин графа, называется хроматическим
числом графа G.
Обозначается: χ(G).
2.) Реберная раскраска графа.
Пусть дан граф G=(X,E) – связный
граф.
• Определение №1: ( Реберная
раскраска)
Отображение g: E→ {1, 2,…,
k} называется реберной раскраской графа
G.
• Определение №2:
( Правильная реберная раскраска)
Реберная раскраска называется правильной
если любые 2 смежные ребра получают разные цвета в указанной раскраске.
• Определение №3:
( Хроматический индекс)
Минимальное
количество красок в правильной реберной раскраске графа называется хроматическим
индексом графа G.
Обозначается: χ’(G).
II.
Практический пример.
• Задача :
a.
Определить
хроматическое число данного графа.
b.
Определить
хроматический индекс данного графа.
c.
Описать
графы, хроматический индекс которых равен 2.
d.
Привести
пример графа, последовательная раскраска вершин которого не является
минимальной.
e.
Показать,
что для раскраски карты, получающейся при пересечении окружностей на плоскости,
достаточно двух цветов.
• Решение :
a.
Хроматическое
число χ(G) = 4.
c.
Любой граф,
хроматический индекс которого равен 2, представляет собой простую цепь или простой цикл,
т.к. каждая вершина этого графа не будет инцидентна более чем 2-ум ребрам.
d.
e.
Если
несовпадающие окружности пересекаются на плоскости, то они могут иметь максимум
2 общие точки.
Карта, полученная таким образом, представляет собой граф, состоящий из
2-ух вершин и 4-ех ребер.
Чтобы раскрасить такой граф потребуется k цветов, а
т.к. число k не должно превышать количество вершин графа (1 < k <= n), то для раскраски карты достаточно 2-ух цветов
1. Произвольной вершине xi графа G
припишем цвет 1.
2. Если
вершины x1, x2, ..., xi раскрашены l
цветами 1, 2, ..., l, l≤i,
то новой произвольно взятой вершине xi+1
припишем минимальный цвет, не использованный при раскраске вершин из ее
окружения.
IV.
Текст программы.
//obieavlenie bibliotek
#include <graphics.h> // initgraph,
graphresult, line, circle, closegraph, setcolor, getmaxx, getmaxy
#include <stdlib.h> // randomize, random
#include <stdio.h> // scanf, printf
#include <conio.h> // clrscr, getch
int main () {
//Peremennye dlea initsializatsii grafiki
int
gdriver = DETECT, gmode, errorcode;
//Massiv SM - matritsa smejnosti
//Massiv A - koordinaty vershin i tsvet vershin
int
A[10][3], SM[10][10];
//Massiv
int
COL[]={2,3,4,5,6,7,8,9,10,11};
//Massiv SM_COL - massiv tsvetov smejnyh
vershin
int
SM_COL[10];
//n - koli4estvo vershin
//i, j, k, c - s4et4iki
int
n, i, j, k, c;
//Vvod koli4estva vershin
do
{
clrscr
();
printf
("Vvedite kolichestvo vershin [1,10]: ");
scanf
("%d",&n);
}
while (n>10 || n<1);
//Initializatia grafi4eskogo rejima
initgraph
(&gdriver, &gmode, "D:/BORLANDC/BGI");
errorcode
= graphresult();
if
(errorcode != grOk) {
printf("Graphics
error: %s\n", grapherrormsg(errorcode));
printf("Press
any key to halt:");
getch();
return
0;
}
//Obnulenie vseh massivov
for
(i=0; i<n; ++i) {
for
(j=0; j<3; ++j)
A[i][j]
= 0;
for
(j=0; j<n; ++j)
SM[i][j]
= 0;
SM_COL[i]
= 0;
}
//Naznachenie koordinat pervoi vershyni
A[0][0]
= getmaxx()/2-n*15;
A[0][1]
= getmaxy()/2;
randomize
();
//Vse vershiny razdeleny po 4etverteam
//Nazna4enie koordinat vershin I-oi 4etverti
for
(i=1; i<=n/4; ++i) {
A[i][0]
= A[i-1][0]+random(60)+60;
A[i][1]
= A[i-1][1]-random(60)-60;
}
//Nazna4enie koordinat vershin II-oi 4etverti
for
(j=i; j<=n/2; ++j) {
A[j][0]
= A[j-1][0]+random(50)+50;
A[j][1]
= A[j-1][1]+random(50)+50;
}
//Nazna4enie koordinat vershin III-ei 4etverti
for
(i=j; i<=3*n/4; ++i) {
A[i][0]
= A[i-1][0]-random(40)-40;
A[i][1]
= A[i-1][1]+random(40)+40;
}
//Nazna4enie koordinat vershin IV-oi 4etverti
for
(j=i; j<=n; ++j) {
A[j][0]
= A[j-1][0]-random(30)-30;
A[j][1]
= A[j-1][1]-random(30)-30;
}
//Zapolnenie matritsy smejnosti
for
(i=0; i<n; ++i)
for
(j=0; j<n; ++j)
if
(i<j) {
SM[i][j]
= random(2);
SM[j][i]
= SM[i][j];
}
//Risovanie grafa
setcolor
(RED);
for
(i=0; i<n; ++i) circle (A[i][0],A[i][1],2);
setcolor
(BLUE);
for
(i=0; i<n; ++i)
for
(j=i; j<n; ++j)
if
(SM[i][j]==1)
line
(A[i][0],A[i][1],A[j][0],A[j][1]);
getch
();
//Nazna4enie pervoi vershine minimal'nogo
tsveta
A[0][2]
= 2;
//Dlea i-toi vershiny
for
(i=1; i<n; ++i) {
//Obnulenie
massiva tsvetov smejnyh vershin
for
(j=0; j<n; ++j)
SM_COL[j]
= 0;
//Zapolnenie
massiva tsvetov smejnyh vershin
for
(j=0; j<n; ++j)
if
(SM[i][j] == 1 && i!=j)
SM_COL[j]
= A[j][2];
//Vybiraiu
j-tiy tsvet iz massiva tsvetov
//s4etaiu
koli4estvo nesovpadenii v massive SM_COL
//i
esli vybranniy j-tiy tsvet ne soderjitsea v massive SM_COL
//prisvaivaiu
ego i-toi vershine i perehoju k sleduiushei vershine
for
(j=0; j<n; ++j) {
c
= 0;
for
(k=0; k<n; ++k)
if
(
if
(c==n) {
A[i][2]
=
goto
NEXT;
}
}
NEXT:
}
//Raskraska vershin
for
(i=0; i<n; ++i) {
setcolor
(A[i][2]);
circle
(A[i][0],A[i][1],2);
}
//Jdem najatiea liuboi klavishi i zakryvaem
grafi4eskiy rejim
getch();
closegraph();
return 0;
}
V.
Вывод.
Проделав данную
лабораторную работу, мы узнали различия между вершинной и реберной раскраской,
научились определять хроматическое число и хроматический индекс графа, и теперь
способны самостоятельно раскрасить произвольный граф, основываясь на алгоритме
последовательной раскраски.