244
правки
Изменения
Нет описания правки
# На некоторых клетках таблицы $n\times n$ стоит фишка, причем в каждой горизонтали и в каждой вертикали стоит хотя бы две фишки. Докажите или опровергните, что можно убрать часть фишек, чтобы в каждой вертикали и в каждой горизонтали стояло ровно по две фишки.
# Дан неориентированный регулярный граф, степень каждой вершины которого равна $k^2$. Звездой называется набор из $k$ ребер, инцидентных одной и той же вершине. Докажите или опровергните, что можно разбить все ребра этого графа на звезды.
# Порожденным (также индуцированным) подграфом называется подграф, полученный удалением некоторого множества вершин и всех инцидентных ребер. Докажите или опровергните, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями длины хотя бы 2), то $G$ не гамильтонов.
# Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
# Докажите, что каждое ребро $G^3$ принадлежит его некоторому простому циклу
# Продемонстрируйте пример негамильтонова графа с 10 вершинами, где для любой пары несмежных вершил $u$ и $v$ сумма их ступеней хотя бы 9.
# Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
# Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
# Теорема "Антихватала". Докажите, что если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф со степенной последовательностью, мажорирующей данную, не содержащий гамильтонова цикла.
# Теорема "Антидирака". Для любого $n \ge 3$ постройте граф, степень каждой вершины которого хотя бы $n / 2$, кроме 1 или 2 вершин, у которых степень на 1 меньше, но нет гамильтонова цикла.
# Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
# Докажите, что если в графе с $n$ вершинами хотя бы (n^2-3n+6)/2$ ребер, то он гамильтонов
# Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
# Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
# Постройте минимальный по числу ребер связный граф, рёберный граф которого не пуст и в реберном графе которого нет гамильтонова цикла.
# Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий для каждого ребра графа $G$ хотя бы одну вершину, ему инцидентную.
# Докажите усиленную версию теоремы Редеи-Камеона: в любом сильно связном турнире с $n$ вершинами есть простой цикл любой длины от $3$ до $n$.
# Докажите, что в любом турнире существует вершина, из которой достижимы все остальные за не более, чем 2 шага
# Рассмотрим все такие гамильтоновы графы, что после удаления любой вершины (и всех инцидентных ребер) он становится гамильтоновым. Докажите, что в таком графе хотя бы 10 вершин, постройте такой граф с 10 вершинами.
