Дано:
Граф: дерево.
Найти:
1. Будет ли связным граф при удалении ребра, связывающего две неконцевые вершины.
2. Будет ли связным граф при удалении концевой вершины вместе с выходящим из неё ребром.
Решение:
а) Удаление ребра, связывающего две неконцевые вершины:
- В дереве любое ребро соединяет две подгруппы вершин. Удаление ребра между двумя неконцевыми вершинами разделяет дерево на два подграфа.
- Оба подграфа останутся несвязанными, так как не будет пути между ними.
Таким образом, граф не будет связным.
Ответ:
Граф не будет связным.
б) Удаление концевой вершины вместе с выходящим из неё ребром:
- Концевая вершина имеет только одно ребро, соединяющее её с деревом. Удаление концевой вершины и ребра, выходящего из неё, не повлияет на связи остальных вершин.
- Оставшаяся часть дерева останется связной, так как в дереве всегда есть другие пути для связи вершин.
Таким образом, граф останется связным.
Ответ:
Граф будет связным.