№ 5. На рисунке 3 изображен граф. Перерисуйте в тетрадь, удалив ребра графа так, чтобы граф был деревом.

Решение:

Дерево — это связный граф без циклов. Чтобы граф стал деревом, нужно удалить минимальное количество рёбер так, чтобы не осталось циклов, но граф остался связным.

Исходный граф на рисунке 3 имеет 5 вершин. Для того чтобы граф с \( n \) вершинами был деревом, он должен содержать \( n-1 \) ребро.

В данном случае \( n = 5 \), значит, дерево должно иметь \( 5-1 = 4 \) ребра.

На рисунке 3 видно, что граф имеет 5 вершин и 5 рёбер. Для получения дерева нужно удалить одно ребро, которое образует цикл. Например, если удалить любое одно ребро из пяти, оставшиеся 4 ребра образуют дерево.

Примечание: Требуется перерисовать граф, удалив одно ребро, чтобы исключить циклы и сохранить связность.