Связанные неориентированные ациклические графы против деревьев

Question

Пока я изучаю теорию графов с введением книги MIT в «алгоритм», я имел в виду некоторые определения о графах и деревьях.

В Введение в MIT к книге Алгоритм 3-е издание, приложение дерева глава показывает мне теорема В.2, «свойства свободных деревьев»

Пусть G = (V, E) неориентированный граф. Следующие утверждения эквивалентны.

1. G является свободным деревом ...
2. G ациклический, и | E | = | V | - 1.

Есть пример связного неориентированного, ациклический граф, который не является деревом?

Теоретически, если имеется ненаправленный ациклический граф, который удовлетворяет условию, что | E | знак равно | V | - 1, будет ли это работать в качестве примера?

Если есть пример, удовлетворяющий этому условию, вы можете мне показать?

Answer 1

Любой связанный ациклический граф - это дерево. Существует несколько различных эквивалентных определений деревьев:

• Они связаны ациклическими графами.
• Они связаны графиками с еще одним узлом, чем с краем.
• Они минимально связные графы (они связаны, но удаление любого края разъединяют их)
• Они максимально ациклические графы (они ациклические и добавление недостающих края создает цикл)
• Они представляют собой графики, где любые два узла имеют ровно один простой путь между ними.

Нет, вы не можете найти подключенный ациклический граф, который не является деревом. :-)