В связном графе 100 вершин и 200 ребер. Докажите ,что можно стереть несколько ребер,образующих цикл так ,чтобы граф остался связным.(вершины не стираем)
В связном графе 100 вершин и 200 ребер. Докажите ,что можно стереть несколько ребер,образующих цикл так ,чтобы граф остался связным.(вершины не стираем)
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Исходный граф с 100 вершинами и 200 ребрами имеет цикл, так как количество ребер больше, чем количество вершин - 1. Рассмотрим случайный цикл в графе и удалим одно из его ребер. Граф останется связным, так как все оставшиеся вершины цикла останутся связаны другими ребрами графа. Повторяя эту операцию до тех пор, пока в графе остаются циклы, мы можем удалим несколько ребер, образующих циклы, и граф все еще будет оставаться связным.