Эйлеровы и гамильтоновы графы

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

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

(Задача о кёнигсбергских мостах) Два острова (назовём их Восточный остров и Западный остров) на реке Прегель (ныне известной как Преголя), протекающей с востока на запад через город Кёнигсберг (ныне Калининград) в восточной Пруссии (ныне часть России), были соединены мостом. Два моста соединяли западный остров $(W)$ с северным берегом $(N)$, и два моста соединяли его с южным берегом $(S)$. Один мост соединял восточный остров $(E)$ с северным берегом, а ещё один — с южным берегом. Покажите, что следующая задача, поставленная перед Леонардом Эйлером (в 1736 году) жителями Кёнигсберга, неразрешима: начать с одного из этих четырёх участков суши города и вернуться в эту же точку, пройдя по каждому мосту ровно один раз.

Решите модифицированную задачу о кёнигсбергских мостах путём:

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

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

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

С помощью алгоритма Флёри найдите эйлеров контур в графе на рис. 3-18.

Fig. 3-18

Если число нечётных вершин связного графа $G=(V, E)$ равно $2 k$, покажите, что множество $E$ можно разбить на $k$ подмножеств, таких что рёбра каждого подмножества образуют цепь между двумя нечётными вершинами.

Найдите нечётные вершины в графе на рис. 3-19, а затем разбейте множество рёбер графа на подмножества, такие что рёбра каждого подмножества образуют цепь.

Fig. 3-19

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

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

Слабо связный орграф является полуэйлеровым тогда и только тогда, когда в нём есть две вершины $v$ и $w$, такие что (1) (полустепень исхода $v)=($ полустепень захода $v)+1$, (2) (полустепень исхода $w)=($ полустепень захода $w)-1$, и (3) полустепень исхода каждой другой вершины равна её полустепени захода. Покажите, что в слабо связном орграфе, удовлетворяющем этим трём свойствам, любая ориентированная эйлерова цепь идёт из $v$ в $w$.

Если каждая вершина графа $G$ чётна, никакое ребро этого графа не является мостом.

Найдите все положительные целые числа $n$, для которых $K_{n}$ является:

Если $L(G)$ — рёберный граф простого графа $G$, покажите, что $L(G)$ эйлеров всякий раз, когда $G$ эйлеров.

Покажите, что если рёберный граф простого графа $G$ эйлеров, отсюда не следует, что $G$ эйлеров.

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

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

Покажите, что если степень каждой вершины связного мультиграфа $G=(V, E)$ равна 4, граф имеет два остовных подграфа, таких что (1) степень каждой вершины в этих двух подграфах равна 2, (2) эти два подграфа не имеют общих рёбер, и (3) $E$ является объединением множеств рёбер этих двух подграфов.

Найдите разложение на 2-факторы 4-регулярного графа, показанного на рис. 3-20.

Fig. 3-20

Найдите разложение на 2-факторы полного двудольного графа $K_{4.4}$.

Граф называется чётным графом, если степень каждой его вершины чётна. Найдите число неэквивалентных помеченных чётных графов с $(n+1)$ вершинами, помеченными $1,2, \ldots ,(n+1)$.

Граф $G$ называется случайно эйлеровым из вершины $\boldsymbol {v}$, если любую цепь графа, начинающуюся в $v$, можно расширить до контура, оканчивающегося в $v$ и состоящего из всех рёбер графа. Покажите, что граф на рис. 3-22 является случайно эйлеровым только из вершины 1.

Fig. 3-22

Докажите, что

Покажите, что если $G$ случайно эйлеров из $v$, то $G-v$ ацикличен. Также покажите, что если $v$ — вершина эйлерова графа $G$, такая что $G-v$ ацикличен, то $G$ случайно эйлеров из $v$.

Если граф $G$ случайно эйлеров из некоторой вершины, покажите, что степень этой вершины равна $\Delta (G)$ — максимальной среди степеней всех его вершин. Покажите, что произвольный эйлеров граф не обязательно является случайно эйлеровым из вершины максимальной степени.

Покажите, что если $G$ случайно эйлеров из $v$, и $w$ — другая вершина, такая что $v$ и $w$ имеют одинаковую степень, то $G$ также случайно эйлеров из $w$.

Граф называется случайно эйлеровым, если он случайно эйлеров из каждой своей вершины. Найдите необходимое и достаточное условие того, что граф случайно эйлеров.

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

Орграф называется случайно эйлеровым орграфом из вершины $\boldsymbol {v}$, если любую ориентированную цепь орграфа, начинающуюся в $v$, можно расширить до эйлерова контура. Докажите, что:

Пусть $W$ — множество $\left\{ 0,1,2, \ldots , p-1\right\}$; любое линейное расположение (повторения допускаются), использующее некоторые или все эти числа, называется словом в алфавите $W$. Любое слово из $n$ чисел из $W$ называется $n$-буквенным словом в $W$. Множество всех $n$-буквенных слов в алфавите $W$ из $p$ чисел обозначается $W(p, n)$. Орграф де Брёйна $\boldsymbol {G}(\boldsymbol {p}, \boldsymbol {n})$ строится следующей индуктивной процедурой. Пусть все слова в $W(p, k)$ известны для $k=1,2, \ldots ,(n-1)$. Множество вершин $G(p, n)$ — это $W(p, n-1)$. Если $t$ — произвольное $(n-2)$-буквенное слово, а $i$ и $j$ — числа (не обязательно различные) из $W$, проведём дуги (для каждого $i$) из вершины $it$ в вершину $tj$, где $j$ пробегает от 0 до $p-1$. Тогда дуга из $xt$ в $ty$ представляет $n$-буквенное слово $xty$. Найдите порядок и размер орграфа де Брёйна $G(p, n)$ и покажите, что это эйлеров орграф.

Постройте орграф де Брёйна $G(3,2)$.

Если $x=21134$ — слово в $W(4,5)$, постройте дуги:

Если $p$ и $n$ — два положительных целых числа и $p^{n}=r$, последовательность $\langle a(0), a(1), \ldots , a(r-1)\rangle$, где каждое $a(i)$ принадлежит $W=\left\{ 0,1,2, \ldots , p-1\right\}$, называется последовательностью де Брёйна, обозначаемой $B(p, n)$, тогда и только тогда, когда любое $n$-буквенное слово в $W$ имеет вид $a(i) a(i+1) \cdots a(i+n-1)$, где $i$ не превышает $r$ и сложение индексов ведётся по модулю $r$. (Эквивалентно, эти $r$ чисел последовательности образуют круговое расположение, такое что любой выбор $n$ последовательных (по часовой стрелке) чисел в этом расположении даёт уникальное слово.) Покажите, что последовательность де Брёйна существует для любого выбора $p$ и $n$.

Найдите последовательность де Брёйна, такую что любое трёхбуквенное слово с использованием 0,1, и 2 можно получить из этой последовательности.

Вращающийся барабан имеет $2^{p}$ секторов. Задача состоит в том, чтобы присвоить каждому сектору метку 0 или 1 так, чтобы никакие две последовательности из $p$ последовательных меток не совпадали. Решите эту задачу при:

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

(Бонди и Хватал) Пусть $u$ и $v$ — две несмежные вершины простого графа $G=(V, E)$ порядка $n$, такие что сумма их степеней не менее $n$, и пусть $G+uv$ — граф, полученный из $G$ соединением этих двух несмежных вершин. Тогда $G$ гамильтонов тогда и только тогда, когда $G+uv$ гамильтонов.

Замыкание $\boldsymbol {c}(\boldsymbol {G})$ графа $G$ порядка $n$ получается из $G$ последовательным соединением пар несмежных вершин, сумма степеней которых не менее $n$, пока такие пары не закончатся. Покажите, что каждый граф имеет единственное замыкание.

Покажите, что граф гамильтонов тогда и только тогда, когда его замыкание гамильтоново.

Покажите, что для установления гамильтоновости графа достаточно показать, что его замыкание является полным графом.

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

(Теорема Хватала) Если $n$ вершин $(n \geq 3)$ графа $G=(V, \mathrm{E})$ помечены так, что их степени $d_{i}(i=1,2, \ldots , n)$ можно расположить в виде последовательности $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, и если $d_{n-k} \geq (n-k)$ всякий раз, когда $d_{k} \leq k<n / 2$, то $G$ гамильтонов.

Если $n$ вершин $(n \geq 3)$ графа $G=(V, \mathrm{E})$ помечены так, что их степени $d_{i}(i=1,2, \ldots , n)$ можно расположить в виде последовательности $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, и если $d_{j}+d_{k} \geq n$ всякий раз, когда $d_{j} \leq j<k$ и $d_{k} \leq (k-1)$, то $G$ гамильтонов.

Если $n$ вершин $(n \geq 3)$ графа $G=(V, \mathrm{E})$ помечены так, что их степени $d_{i}(i=1,2, \ldots , n)$ можно расположить в виде последовательности $S: d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, и если $d_{k}>k$ всякий раз, когда $1 \leq k<n / 2$, то $G$ гамильтонов.

Докажите теорему Оре (теорема 3.5), используя теорему Поша.

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

Покажите, что условие Хватала не является необходимым условием существования остовного цикла в графе.

Покажите, что теорема Хватала сильнее теоремы Бонди.

Покажите, что теорема Бонди сильнее теоремы Поша.

Покажите, что теорема Поша сильнее теоремы Оре.

Покажите, что теорема Оре сильнее теоремы Дирака.

Если $G=(V, W, E)$ — двудольный граф с $\left|V\right|=\left|W\right|=n$, и степень каждой вершины больше $n / 2$, то $G$ гамильтонов.

Покажите, что если $G$ эйлеров, его рёберный граф $L(G)$ гамильтонов. Приведите контрпример, показывающий, что обратное неверно.

Покажите, что если граф $G$ гамильтонов, его рёберный граф $L(G)$ гамильтонов. Приведите контрпример, показывающий, что обратное неверно.

Докажите теорему 3.7: граф $G$ с $n$ вершинами ($n$ не менее трёх) гамильтоново-связен, если сумма степеней любых двух несмежных вершин больше $n$. В частности, он гамильтоново-связен, если степень каждой вершины больше $n / 2$.

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

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

Приведите пример гамильтоново-связного графа, замыкание которого, определённое в задаче 3.62, не является полным.

Покажите, что если граф с $n$ вершинами $(n>3)$ и $m$ рёбрами гамильтоново-связен, необходимо, чтобы $m \geq (3 n) / 2$. Покажите, что это условие ни в коем случае не является достаточным для гамильтоновой связности графа.

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

Покажите, что гамильтоново-связный граф является сильно гамильтоновым графом. Верно ли обратное?

Найдите достаточное условие сильной гамильтоновости графа.

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

Если сумма степеней каждой пары несмежных вершин графа порядка $n$ не менее $(n-1)$, граф имеет гамильтонов путь. В частности, если степень каждой вершины не менее $(n-1) / 2$, граф имеет гамильтонов путь.

Граф $G$ называется случайно обходимым, если гамильтонов путь получается при старте из любой вершины и последовательном переходе к любой смежной вершине, ещё не входящей в путь. Более того, если $G$ имеет не менее трёх вершин, и конечная вершина каждого такого пути смежна с начальной вершиной, граф называется случайно гамильтоновым. Очевидно, циклические графы и полные графы с тремя или более вершинами случайно обходимы и случайно гамильтоновы. Покажите, что:

Покажите, что если $C=\left\langle v_{1}, v_{2}, \ldots , v_{n}, v_{1}\right\rangle$ — гамильтонов цикл случайно гамильтонова графа, и в графе есть ребро между $v_{j}$ и $v_{k}$, то есть ребро между $v_{j+i}$ и $v_{k+i}$ для $i= 1,2, \ldots , n-1$. (Здесь сложение индексов ведётся по модулю $n$.)

Покажите, что если $C=\left\langle v_{1}, v_{2}, \ldots , v_{n}, v_{1}\right\rangle$ — гамильтонов цикл случайно гамильтонова графа $G$, и существует ребро между $v_{p}$ и $v_{p+2}$ (для некоторого $p$), то $G$ — полный граф.

Пусть $G$ — случайно гамильтонов граф порядка $n$, и пусть $C$ — произвольный фиксированный гамильтонов цикл этого графа. Рёбра в $C$ называются рёбрами цикла, а рёбра, не входящие в $C$, называются диагональными рёбрами. Любой цикл $C^{\prime }$, состоящий из $(k-1)$ рёбер цикла и ровно одного диагонального ребра, называется внешним $\boldsymbol {k}$-циклом. Покажите, что минимальное значение $k$, при котором $G$ имеет внешний $k$-цикл, равно либо 3, либо 4. Более того, если $k=3$, граф является полным графом, а если $k=4$, число вершин графа чётно.

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

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

Граф $G$ называется сильно случайно обходимым, если для каждых двух различных вершин $u$ и $v$ гамильтонов путь между $u$ и $v$ существует всякий раз, когда мы начинаем с $u$ и последовательно переходим к другой ещё не встреченной вершине, с ограничением, что $v$ будет выбрана только тогда, когда нет другой альтернативы. Покажите, что граф $G$ порядка $n$ является сильно случайно обходимым графом тогда и только тогда, когда он является полным графом $K_{n}$.

Полустепень исхода вершины турнира можно рассматривать как счёт игрока, представленного этой вершиной. Игрок с максимальным счётом называется победителем. Если $u$ — игрок, победивший победителя $w$ турнира, покажите, что $w$ победил некоторого игрока, победившего $u$.

Граф (орграф) порядка $n(n \geq 3)$ называется вершинно-панциклическим, если каждая его вершина содержится в цикле (ориентированном цикле) длины $p$ для каждого $p(3 \leq p \leq n)$. Покажите, что сильно связный турнир вершинно-панциклический.

Докажите теорему 3.13: турнир гамильтонов тогда и только тогда, когда он сильно связен.

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

Турнир $G=(V, E)$ называется неприводимым, если для любого подмножества $W$ множества $V$ должна существовать дуга из вершины в $W$ в вершину в $V-W$. Покажите, что в турнире $G=(V, E)$ следующие понятия эквивалентны:

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

Последовательность $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ неотрицательных целых чисел называется последовательностью очков (турнира), если существует турнир порядка $n$, вершины которого можно пометить $v_{i}$ так, что полустепень исхода каждой $v_{i}$ равна $s_{i}$ для каждого $i=1,2, \ldots , n$. Покажите, что неубывающая последовательность из $n$ неотрицательных целых чисел является последовательностью очков транзитивного турнира тогда и только тогда, когда эта последовательность равна $\langle 0,1,2, \ldots , n-1\rangle$.

Покажите, что последовательность $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ неубывающих неотрицательных целых чисел является последовательностью очков турнира тогда и только тогда, когда $s_{1}+s_{2}+\cdots +s_{k} \geq k(k-1) / 2$ при $1 \leq k \leq n$, причём равенство выполняется при $k=n$.

Покажите, что последовательность $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ неубывающих неотрицательных целых чисел является последовательностью очков сильно связного турнира тогда и только тогда, когда $s_{1}+s_{2}+\cdots +s_{k}>k(k-1) / 2$ при $1 \leq k \leq (n-1)$ и $s_{1}+ s_{2}+\cdots +s_{n}=n(n-1) / 2$.

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

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

Покажите, что если граф имеет контур нечётной длины, он имеет цикл нечётной длины.

Пусть в группе из $n$ человек $(n>3)$ любые два из них вместе знают всех остальных людей группы. Покажите, что этих $n$ человек можно рассадить за круглым столом так, чтобы каждый человек сидел между двумя знакомыми.

Покажите, что $k$-регулярный граф с $(2 k-1)$ вершинами гамильтонов.

Покажите, что любой $k$-регулярный простой граф с $(2 k-1)$ вершинами гамильтонов.

Нетривиальный связный граф эйлеров тогда и только тогда, когда каждый блок графа эйлеров.

Найдите число гамильтоновых графов в $K_{n}$.

Найдите число гамильтоновых циклов в $K_{n, n}$.

Покажите, что если $n$ нечётно, множество рёбер $K_{n}$ можно разбить на $\frac{1}{2}(n-1)$ непересекающихся гамильтоновых циклов.

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

Покажите, что сумма квадратов членов последовательности очков турнира равна сумме квадратов полустепеней захода вершин.

Покажите, что регулярный турнир сильно связен.

Покажите, что если $\left\langle s_{1}, s_{2}, \ldots , s_{n}\right\rangle$ — последовательность очков турнира, то $\left\langle t_{1}, t_{2}, \ldots , t_{n}\right\rangle$ также является последовательностью очков турнира, где $t_{i}=(n-1)-s_{i}$ для $i=1,2, \ldots , n$.

Рассмотрите случай, когда все неравенства в формулировке задачи 3.85 являются равенствами.

Покажите, что в турнире с $n$ игроками число игроков со счётом $(n-1)$ не превышает 1.

Покажите, что если $n$ — нечётное число, отличное от 1, существует турнир порядка $n$, в котором каждая вершина является победителем.

Покажите, что $k$-куб (см. решённую задачу 1.56) — гамильтонов граф.

При каком значении $k$ граф $k$-куба является эйлеровым графом?

Покажите, что орграф де Брёйна — гамильтонов граф.