Основы теории графов

Любой цикл, не проходящий ни по одному ребру дважды, содержит несамопересекающийся цикл.

Любой цикл нечётной длины содержит несамопересекающийся цикл нечётной длины.

Справедливо ли аналогичное утверждение для циклов чётной длины, не проходящих ни по одному ребру дважды?

В графе есть несамопересекающийся цикл, проходящий через рёбра $a$ и $b$, а также есть несамопересекающийся цикл, проходящий через рёбра $b$ и $c$. Тогда есть несамопересекающийся цикл, проходящий через рёбра $a$ и $c$.

В любом дереве найдётся лист, т.е. вершина степени 1.

В любом дереве с $n$ вершинами $n-1$ ребро.

В любом дереве между любыми двумя вершинами существует единственный несамопересекающийся путь.

Последовательность из $n$ натуральных чисел является последовательностью степеней вершин некоторого дерева тогда и только тогда, когда сумма её членов равна $2n-2$.

имеющих изолированную вершину или не имеющих?

связных или несвязных?

Формула Кэли. Число деревьев с данными $n$ вершинами равно $n^{n-2}$.

Если сумма целых положительных чисел $d_{1}, \ldots , d_{n}$ равна $2n-2$, то число деревьев с данными $n$ вершинами, у которых $i$-я вершина имеет степень $d_{i}$, равно $\dfrac {(n-2)!}{(d_{1}-1)! \cdot \ldots \cdot (d_{n}-1)!}$.

Это утверждение можно переформулировать в виде:

где сумма берётся по всем деревьям $T$ с вершинами $1,2,\ldots ,n$ и через $\deg_{T}(k)$ обозначена степень вершины $k$ дерева $T$.

Пусть $T_{1}, \ldots , T_{r}$ — деревья, множества вершин которых не пересекаются. Сколько есть деревьев, множество вершин которых есть объединение множества вершин этих $r$ деревьев и которые содержат $T_{1}, \ldots , T_{r}$?

Найдите код Прюфера дерева с вершинами $1,2,\ldots ,10$ и рёбрами $(8,9), (8,4), (4,10), (10,3), (3,5), (10,6), (10,1), (1,7), (1,2)$.

Восстановите дерево по коду Прюфера $1,1,2,5,4,2,7$.

Код Прюфера определяет взаимно однозначное соответствие между множеством деревьев с данными $n$ вершинами и множеством слов длины $n-2$ из чисел от 1 до $n$.

В коде Прюфера вершина степени $d$ встречается $d-1$ раз.

Каких графов больше: деревьев с данными 100 вершинами или уницикличеких графов с данными 98 вершинами?

Выразите число уницикличеких графов с данными $n$ вершинами в виде суммы не более чем $n$ слагаемых.

В дереве нет непустых подграфов, у которых степень каждой вершины чётная и положительная.

Для графа $G$ обозначим через $h_{1}(G)$ число его подграфов без изолированных вершин, у которых степень каждой вершины чётна. (Пустой подграф удовлетворяет этому условию.) Докажите, что $h_{1}(G)$ — степень двойки. Выразите $h_{1}(G)$ через количества $n$ вершин, $e$ рёбер и $k$ компонент связности графа.

На рёбрах дерева стоят знаки $+$ и $-$. Разрешается менять знаки на всех рёбрах, выходящих из одной вершины. Тогда из любой расстановки можно получить любую другую.

Для графа $G$ обозначим через $h^{1}(G)$ наибольшее количество расстановок знаков $+$ и $-$ на его рёбрах, ни одну из которых нельзя получить из другой описанными выше операциями. Докажите, что $h^{1}(G)$ — степень двойки. Выразите $h^{1}(G)$ через $n$, $e$ и $k$.

Докажите, что $h_{1}(G)$ и $h^{1}(G)$ не меняются при стягивании ребра, и выведите отсюда, что $h_{1}(G) = h^{1}(G)$.

клик размера $k$ в графе $K_{n}$,

клик размера $k$ в графе $K_{m,n}$,

независимых множеств размера $k$ в графе $K_{n}$,

независимых множеств размера $k$ в графе $K_{m,n}$,

подграфов в $K_{n}$, изоморфных $K_{k,l}$,

подграфов в $K_{m,n}$, изоморфных $K_{k,l}$.

графы с четырьмя вершинами,

связные графы с пятью вершинами и пятью рёбрами,

несвязные графы с пятью вершинами.

Верно ли, что получившаяся грань ограничена несамопересекающимся циклом?

Верно ли, что если выкинуть ещё одну вершину, то все грани опять будут ограничены несамопересекающимися циклами?

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

Формула Эйлера. Для любого связного плоского графа с $f$ гранями имеет место равенство $n - e + f = 2$.

(Доказательство см., например, в [Р]. Далее этим результатом можно пользоваться без доказательства. Эта формула часто записывается в виде $V - E + F = 2$.)

Найдите аналог формулы Эйлера для плоского графа с $k$ компонентами связности.

Ни один из графов $K_{5}$ и $K_{3,3}$ невозможно без самопересечений нарисовать на плоскости.

Рис. 5. Непланарные графы

На плоскости отмечено $n$ точек. Разрешается соединять некоторые две из них ломаной, не проходящей через другие точки. Два игрока по очереди соединяют ломаной какие-то две ещё не соединённые точки. При этом требуется, чтобы эти ломаные не самопересекались и не пересекались нигде, кроме отмеченных точек. Проигрывает тот, кто не может сделать ход. Для каких $n$ при правильной игре выигрывает тот, кто ходит первым?

Перечислите все связные плоские графы (с точностью до изоморфизма), у которых степени всех вершин равны и «степени» всех граней равны (т.е. граница каждой грани состоит из одного и того же числа рёбер).

Замечание. Если пункты (1), (2) или (3) не получаются, решайте следующие пункты. Определение изоморфизма см. в п. 2.3.

Выпуклых правильных многогранников (все грани — правильные многоугольники с одинаковым числом сторон, степени всех вершин равны) ровно 5 (с точностью до изоморфизма их графов). Конструкцию соответствующих многогранников нужно привести, она не предполагается известной.

Для любого плоского связного графа без петель и кратных рёбер, имеющего более двух вершин, $2e \geq 3f$ и $e \leq 3n - 6$.

В любом плоском графе есть вершина степени не более 5.

Если каждая вершина плоского связного графа имеет степень $d$, а граница каждой грани состоит из ровно $k \geq 3$ рёбер, то

6 цветов;

5 цветов;

распознавания планарности графа (здесь можно использовать без доказательства теорему Куратовского);

рисования без самопересечений заведомо планарного графа на плоскости.

Теорема Фари. Плоский граф можно нарисовать без самопересечений на плоскости так, что все рёбра будут отрезками.

Дан невыпуклый многоугольник с непрозрачными сторонами. Назовем вершину $A$ видимой из точки $X$, если внутренность отрезка $AX$ не пересекается с границей многоугольника. Назовем ядром многоугольника множество его внутренних точек, из которых видны все вершины многоугольника. Докажите, что если точку из ядра соединить отрезками с произвольно выбранными несколькими (не менее чем с двумя, и не обязательно со всеми) вершинами исходного многоугольника, то многоугольник разобьется на многоугольники с непустыми ядрами.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$;

$K_{7}$;

$K_{4,4}$.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$.

в 5 цветов;

в 6 цветов;

в 7 цветов?

ориентированных без кратных рёбер, но, возможно, с петлями?

неориентированных без петель, но, возможно, с кратными рёбрами?

неориентированных без петель и кратных рёбер?

неориентированных, у которых допускаются кратные рёбра и петли?

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

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

При каком условии в мультиграфе существует эйлеров путь?

При каком условии в ориентированном мультиграфе существует ориентированный эйлеров цикл?

При каких $n$ граф $K_{n}$ имеет эйлеров цикл?

То же для графа $K_{m,n}$.

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

На рёбрах графа, у которого степень каждой вершины чётна, можно поставить стрелки так, что у каждой вершины входящая степень будет совпадать с исходящей.

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

В нарисованном на плоскости без самопересечений связном графе есть эйлеров цикл тогда и только тогда, когда грани можно раскрасить в 2 цвета правильно, т.е. так, что при переходе через каждое ребро цвет меняется.

29 секунд, если в коде могут быть использованы только цифры 1, 3 и 7;

1002 секунды, если в коде могут быть использованы десять цифр.

Сформулируйте и докажите правило «$0 < 1 < 2 < \ldots < 8 < 9$» открытия замка за 1002 секунды.

$n=3$, начинающуюся с 111;

$n=4$, начинающуюся с 1011;

$n=4$, заканчивающуюся на 1010.

Существует дерево, содержащее все вершины этого мультиграфа, все рёбра которого направлены в сторону вершины 1.

Фиксируем дерево $T$ из п. (1). Будем обходить этот граф (по стрелкам), проходя по каждому ребру не более одного раза. Сначала выйдем из вершины 1 в произвольном направлении. Далее, пусть мы пришли в некоторую вершину $v$. Выходим из нее по любому ребру, не принадлежащему $T$, если это возможно. А если невозможно, то выходим из нее по ребру, принадлежащему $T$ (такое ребро единственно). Докажите, что движение закончится в вершине 1 и что в результате получится ориентированный эйлеров цикл.

Число ориентированных эйлеровых циклов в этом мультиграфе кратно числу $(d_{1}-1)! \cdot \ldots \cdot (d_{n}-1)!$.

Если граф связен и $2e \geq n^{2} - 3n + 6$, то в нём есть гамильтонов цикл.

Теорема Дирака — Оре. Граф, сумма степеней любых двух несмежных вершин которого не меньше $n$, имеет гамильтонов цикл.

Лемма Дирака. Если $a_{0} \ldots a_{s}$ — максимальный из путей в графе, проходящих по каждой своей вершине только один раз, $s \geq 3$ и $\deg a_{0} + \deg a_{s} > s$, то в этом графе есть несамопересекающийся цикл длины $s$.

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

Граф, сумма степеней любых двух несмежных вершин которого не меньше $n-1$, имеет гамильтонов путь.

В этом графе есть хотя бы один несамопересекающийся цикл.

Обозначим через $v_{1}, \ldots , v_{s}$ максимальный несамопересекающийся цикл в этом графе. Обозначим через $W$ любую компоненту связности графа, полученного удалением вершин этого несамопересекающегося цикла из исходного графа. Обозначим через $X$ множество вершин несамопересекающегося цикла, соседних с $W$.

Тогда $\left|X\right| \geq k$.

Вершины $v_{i}, v_{i+1}$ не лежат одновременно в $X$.

Если $v_{i}, v_{j} \in X$, то в графе нет ребра $v_{i+1} v_{j+1}$.

Есть ли гамильтонов путь в графе на рис. 8?

Рис. 8. Есть ли в этом графе гамильтонов путь?

Есть ли гамильтонов цикл в графе на рис. 9?

Рис. 9. Граф многогранника Гринбергса. Есть ли в нём гамильтонов путь?

Для каких $n$ есть гамильтонов цикл в графе, вершинами которого являются 3-элементные подмножества $n$-элементного множества, и два подмножества соединены ребром, если они пересекаются ровно по одному элементу?

В любом турнире имеется ориентированный гамильтонов путь.

Для любого $n$ существует турнир с $n$ вершинами, в котором имеется не менее $n! / 2^{n}$ ориентированных гамильтоновых путей.

Если граф не содержит треугольников, то $e \leq n^{2}/4$.

Если $e = [n^{2}/4] + 1$, то в графе есть по крайней мере $[n/2]$ треугольников.

Если $n = km$ и граф не содержит $(k+1)$-клики, то $2e \leq k(k-1) \times m^{2}$. (Переходя к дополнительному графу, получаем, что если $n = km$ и граф не содержит $(k+1)$-антиклики, то $2e \geq km(m-1)$.)

Если граф не содержит $(k+1)$-антиклики, то $2e \geq km(m-1) + 2mr$, где $m := [n/k]$ и $r := k\{ n/k\}$.

Если граф не содержит несамопересекающегося цикла длины 4, то $e < n^{3/2}$.

Если граф не содержит подграфа $K_{3,2}$, то $e < 2n^{3/2}$.

Если граф не содержит подграфа $K_{3,3}$, то $e < 2n^{5/3}$.

Для любых целых $s, t$, $2 \leq s \leq t$, если граф не содержит подграфа $K_{s,t}$, то $e < t n^{2-1/s}$.

$E_{n}(2) > n[\log_{2} n]/4$;

$E_{n}(2) \leq 2n^{3/2}$;

$E_{n}(3) \leq 2n^{5/3}$;

$\dfrac {(n-1)^{2}}{4} \leq E_{n}(4) \leq \dfrac {2(n+4)^{2}}{5}$.

Пусть $V$ — $11^{q}$-элементное подмножество пространства $\mathbb {R}^{q}$ (определение пространства $\mathbb {R}^{q}$ см. в гл. 7), любое $10^{q}$-элементное подмножество которого содержит две точки $x,y$ на расстоянии 1: $\left|x-y\right|=1$. Докажите, что для достаточно большого $q$ количество единичных расстояний между точками множества $V$ больше чем $12^{q}/2$:

Докажите, что в условиях предыдущего пункта можно заменить число $12^{q}/2$ на $12{,}1^{q}$.

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

Верно ли, что для любого пути $P$ в мультиграфе, имеющем не менее трёх вершин, найдётся другой путь в том же мультиграфе с теми же концами, не пересекающийся с $P$ нигде, кроме концов?

Для любого ребра $u$ двусвязного графа $G$, отличного от $K_{3}$, хотя бы один из графов $G-u$ и $G/u$ двусвязен.

Для любых двух вершин выпуклого многогранника существуют три непересекающихся (нигде, кроме этих вершин) пути по его рёбрам из одной вершины в другую. (Такие графы называют трёхсвязными.)

Для трёхсвязного графа $G$ с ребром $xy$ (вершины которого — $x,y$) граф $G/xy$ трёхсвязен тогда и только тогда, когда граф $G-x-y$ двусвязен.

Теорема Уитни (вершинная). Мультиграф остаётся связным после удаления любых $k-1$ вершин тогда и только тогда, когда любые две его вершины можно соединить $k$ путями, пересекающимися только в этих двух вершинах.

Теорема Менгера (вершинная). Если вершины $a$ и $b$ мультиграфа $G$, не соединённые ребром, остаются в одной компоненте связности после удаления любых $k-1$ других вершин, то $a$ и $b$ можно соединить $k$ путями, пересекающимися только в этих двух вершинах.