Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.39. Поиск несмежных вершин 
bool IsBorder(int i, int k) 
{ 
5 / 23

---

190 
int j = -1; bool result = false; 
int N = Nodes.Length; 
while ((j < N - 1) && !result) 
result = Nodes[++j].visit && (Nodes[j].color 
==
Colors[k]) && (A[i, j] != 0xFFFFF); 
return result; 
} 
На рисунке 5.21 показан пример раскраски графа с 13-ю вершинами. 
В данном случае хроматическое число оказалось равным 4. 
Рис. 5.21. Пример раскраски 
5.7.2.3. Раскраска ребер 
Задачу раскраски можно сформулировать и для ребер графа. Реберной 
k-раскраской называется некоторая функция 
ϕ, задающая отображения мно-
жества ребер E: 
ϕ: E → A = {a
1
, ... , a
k
}. 
6 / 23

---

191 
Реберная раскраска называется правильной, если все ребра, инцидент-
ные любой вершине графа имеют разные цвета. Граф, для которого сущест-
вует правильная реберная k-раскраска называется k-раскрашиваемым. Ми-
нимальное число k, при котором существует правильная реберная k-
раскраска называется реберным хроматическим числом или индексом (ис-
пользуется обозначение X(G) = k). Граф G называется реберно k-
хроматическим, если хроматический индекс равен k. 
На рисунках 5.22 а и б приведены примеры графов, для раскраски ре-
бер которых потребовалось 3 и 2 краски соответственно. 
4
2
3
1
2
2
1
1
 
1
2
3
1
2
3
 
а 
 
 
б 
Рис. 5.22. Графы, для раскраски ребер которых потребовалось 2 (а) и 3 (б) 
краски 
Хроматический индекс для полного графа с четным числом вершин ра-
вен X(K
2n
) = 2n 
− 1, а с нечетным числом вершин X(K
2n + 1
) = 2n + 1. Так, на-
пример, для полного графа с четырьмя вершинами (рис. 5.23) необходимо 
3 краски для раскрашивания 6 ребер. 
4
2
3
1
2
2
1
1
3
3
Рис. 5.23. Раскраска графа с четырьмя вершинами