Банк задач по математике

Задача 3.2.1

Хроматическим числом $\chi (G)$ графа $G$ называется минимальное количество цветов, в которые можно правильно покрасить вершины графа $G$ .

Если при удалении из графа любой вершины хроматическое число уменьшается, то $\chi (G) \leq 1 + \left[2e/n\right]$ .

?

Задача 3.2.2

(1)(2)(3)

Хроматическим числом $\chi (G)$ графа $G$ называется минимальное количество цветов, в которые можно правильно покрасить вершины графа $G$ .

?

(1)

На какое число может измениться хроматическое число графа, если добавить к графу одно ребро? Или, формально, найдите все целые $k$ , для которых существует граф $G$ и его ребро $u$ такие, что $\chi (G) - \chi (G-u) = k$ .

(2)

$\chi (V, E_{1} \cup E_{2}) \leq \chi (V, E_{1})\chi (V, E_{2})$ . (Напомним, что через $(V, E)$ обозначается граф со множеством вершин $V$ и множеством рёбер $E$ .)

(3)

Для любых $r_{1}, r_{2} \in \mathbb {N}$ постройте такие графы $(V, E_{1})$ и $(V, E_{2})$ , что $\chi (V, E_{1} \cup E_{2}) = \chi (V, E_{1})\chi (V, E_{2})$ , $\chi (V, E_{1}) = r_{1}$ и $\chi (V, E_{2}) = r_{2}$ .

Задача 3.2.3

(1)(2)

Следующий алгоритм раскраски вершин графа называется жадным. Сначала все вершины произвольно нумеруются. После этого последовательно каждую вершину, начиная с первой, красим в цвет с минимальным номером, отсутствующим среди уже покрашенных соседей этой вершины.

?

(1)

Вершины произвольного графа $G$ можно занумеровать так, чтобы жадный алгоритм его раскраски использовал ровно $\chi (G)$ цветов.

(2)

Для каждого целого $k > 0$ постройте такие двудольный граф и нумерацию его вершин, что раскраска графа, построенная жадным алгоритмом, отвечающим построенной нумерации, имеет не менее $k$ цветов.

Примечание.

?

Эта задача показывает, что «качество» раскраски, построенной жадным алгоритмом, сильно зависит от упорядочения вершин.

Задача 3.2.4

Исследуйте на планарность (см. п. 2.4), найдите хроматическое число и хроматический индекс графов с рис. 11 и 12.

Хроматический индекс графа --- минимальное число цветов, в которые можно правильно раскрасить рёбра этого графа.

Рис. 11. Граф Петерсена

Рис. 12. Исследуйте на планарность, найдите хроматическое число и хроматический индекс графов

?

Хроматическое число и индекс