244
правки
Изменения
Нет описания правки
# Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
# Докажите, что каждое ребро $G^3$ принадлежит его некоторому простому циклу
# Продемонстрируйте пример негамильтонова графа с 10 вершинами, где для любой пары несмежных вершил $u$ и $v$ сумма их ступеней степеней хотя бы 9.
# Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
# Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
# Докажите усиленную версию теоремы Редеи-Камеона: в любом сильно связном турнире с $n$ вершинами есть простой цикл любой длины от $3$ до $n$.
# Докажите, что в любом турнире существует вершина, из которой достижимы все остальные за не более, чем 2 шага
# Рассмотрим все такие гамильтоновы негамильтоновы графы, что после удаления любой вершины (и всех инцидентных ребер) он становится гамильтоновым. Докажите, что в таком графе хотя бы 10 вершин, постройте такой граф с 10 вершинами.
