Изменения

Перейти к: навигация, поиск

Список заданий по АСД

2193 байта добавлено, 18:12, 28 сентября 2014
Нет описания правки
# Харари 3.7
# Харари 3.9
# Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.# Граф называется вершинно k-связным, если он остаётся связным после удаления любых (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.# Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.# Харари 4.2# Харари 5.5# Харари 5.6# Харари 5.7# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.# В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.# Харари 7.2# Харари 7.4# Харари 7.5# Харари 7.7# Харари 7.9# Харари 7.14# Харари 7.17# Харари 7.18
</wikitex>
Анонимный участник

Навигация