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

Задача 3.1.1

Раскраска графа (т.е. вершин графа) в несколько цветов называется правильной, если концы любого ребра окрашены в разные цвета.

Докажите, что следующие три условия эквивалентны:

граф двудолен;
граф можно правильно раскрасить в 2 цвета;
граф содержит циклы только чётной длины.

?

Задача 3.1.2

(1)(2)(3)(4)

Раскраска графа (т.е. вершин графа) в несколько цветов называется правильной, если концы любого ребра окрашены в разные цвета.

?

(1)

Если в графе степень каждой вершины не превосходит $d$ , то его можно правильно раскрасить в $d+1$ цвет.

(2)

Если в связном графе степень каждой вершины не превосходит $d$ и есть вершина степени менее $d$ , то его можно правильно раскрасить в $d$ цветов.

(3)

Если в связном графе степень каждой вершины не превосходит $d$ и есть вершина, после удаления которой граф перестаёт быть связным, то граф можно правильно раскрасить в $d$ цветов.

(4)

Если связный граф, имеющий более двух вершин, при удалении некоторого ребра распадается на два графа, каждый из которых можно правильно раскрасить в $d$ цветов, то и исходный граф можно правильно раскрасить в $d$ цветов.

Задача 3.1.3

Раскраска графа (т.е. вершин графа) в несколько цветов называется правильной, если концы любого ребра окрашены в разные цвета.

Если граф с $n$ вершинами не содержит $(k+1)$ -антиклики, то граф невозможно правильно покрасить менее чем в $n/k$ цветов.

?

Задача 3.1.4

В выпуклом многоугольнике провели несколько диагоналей, не имеющих общих внутренних точек. Полученный плоский граф можно правильно раскрасить в 3 цвета.

?

Задача 3.1.5

(1)(2)(3)

?

(1)

В связном графе степень каждой вершины не превосходит трёх. Известно, что его можно правильно раскрасить в 3 цвета так, чтобы соседи некоторой вершины были одного цвета. Добавили одну вершину и выходящие из неё рёбра так, что по-прежнему степени всех вершин не превосходят трёх. Докажите, что полученный граф можно правильно раскрасить в 3 цвета.

(2)

В связном графе степень каждой вершины не превосходит трёх. Известно, что его можно правильно раскрасить в 3 цвета и при любой такой раскраске у каждой вершины есть соседи разных цветов. Добавили одну вершину и выходящие из неё рёбра так, что по-прежнему степени всех вершин не превосходят трёх и полученный граф отличен от $K_{4}$ . Докажите, что полученный граф можно правильно раскрасить в 3 цвета.

(3)

Теорема Брукса. Если степень каждой вершины графа не превосходит $d \geq 3$ и нет $(d+1)$ -клики, то граф можно правильно раскрасить в $d$ цветов.

Задача 3.1.6

Натуральные числа $d, k, d_{1}, \ldots , d_{k}$ таковы, что $d_{1}+d_{2}+\ldots +d_{k} = d+1-k$ . Степень любой вершины графа не превосходит $d$ . Докажите, что вершины можно разбить на $k$ групп так, что любая вершина $i$ -й группы соединена не более чем с $d_{i}$ вершинами своей группы.

?

Задача 3.1.7

Трём смышлёным девочкам Ире, Тане и Юле выдали по копии одного и того же графа. Юля и Таня раскрасили свои графы правильно. Юля использовала меньше цветов, чем Таня, зато у Тани в каждый цвет покрашено не менее двух вершин. Докажите, что Ира может правильно раскрасить свой граф, использовав не больше цветов, чем Юля, и чтобы в каждый цвет было покрашено не менее двух вершин.

?

Задача 3.1.8

(1)(2)(3)

?

(1)

Если граф невозможно правильно раскрасить в $k-1$ цвет, то для любой его правильной раскраски в $k$ цветов существует путь, в котором встречается ровно по одной вершине каждого цвета.

(2)

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

(3)

Если максимальный нечётный несамопересекающийся цикл в графе проходит через $d-1$ вершину, то граф можно правильно раскрасить в $d$ цветов.

Задача 3.1.9

Ориентированный граф, из каждой вершины которого выходит не более $d$ рёбер, можно правильно раскрасить в $2d+1$ цвет.

?

Задача 3.1.10

Имеется несколько цветов. Каждой вершине двудольного графа с $n \leq 2^{k-1}$ вершинами сопоставлено не менее $k$ цветов. («Списки» цветов, сопоставленные разным вершинам, могут быть и одинаковыми, и различными.) Тогда существует правильная раскраска графа, приписывающая каждой вершине некоторый сопоставленный ей цвет.

?

Задача 3.1.11

(1)(2)

Раскраска рёбер графа называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета.

?

(1)

Если степень каждой вершины графа не превосходит $d$ , то рёбра графа можно правильно раскрасить в $d+1$ цвет.

(2)

Существует такая раскраска рёбер графа $K_{m,n}$ в два цвета, что число одноцветных подграфов $K_{a,b}$ не больше $\binom {m}{a}\binom {n}{b}2^{1-ab}$ .

Раскраски графов