210
правок
Изменения
Нет описания правки
# Будем называть последовательность $(d_1, \ldots, d_n)$ степенной последовательностью, если существует граф с такими степенями вершин. Приведите критерий, проверяемый за полиномиальное время, что заданная последовательность является степенной.
# Теорема "Антихватала". Докажите, что если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф со степенной последовательностью, мажорирующей данную, не содержащий гамильтонова цикла.
# Теорема "Антидирака". Для любого $n \ge 3$ постройте граф, степень каждой вершины которого хотя бы $\lceil n / 2\rceil - 1$, кроме 1 или 2 вершин, у которых степень на 1 меньше, но нет гамильтонова циклакоторый не является гамильтоновым.
# Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
# Докажите, что если в графе с $n$ вершинами хотя бы $(n^2-3n+6)/2$ ребер, то он гамильтонов
