Изображает схему посёлков на острове и дорог между ними. (Прочитайте ниже)
Изображает схему посёлков на острове и дорог между ними. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы сохранилась возможность проехать из каждого посёлка в любой другой?
Извините, не понимаю как это делать, объясните пожалуйста.
2: AD, DF
Перед нами задача найти максимальное число рёбер, при удалении которых из графа на картинке он останется связным.
Опр: Деревом называется связный граф без циклов
Факт: В любом дереве на n вершинах ровно n-1 ребро
Дерево это в определенном смысле «самый тощий» связный граф, то есть при удавлении любого ребра из дерева оно теряет связность.
На нашем графе 9 вершин. Стало быть, в его остовном дереве — 8 рёбер. А в графе на рисунке — 10 рёбер. Итого можно максимум удалить 10 - 8 = 2 ребра так, чтобы граф остался связным.
В качестве примера, можно удалить ребра EF и CD, и граф превратится в дерево (но это далеко не единственный способ удалить 2 ребра, только пример)
Спасибо