Страница 58 номер 91, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Приведите пример графа, который содержит цикл и у которого имеется единственное остовное дерево.
Граф из единственной вершины \(A\) и петли при ней. Петля — это цикл длины 1, значит, цикл в графе есть.
Остовное дерево содержит вершину \(A\), а петля войти в него не может: дерево не имеет циклов. Значит, остовное дерево — сама вершина \(A\) без рёбер, и оно единственное.
Тот же вывод даёт подсчёт: \(v = 1\), \(e = 1\), цикломатическое число \(1 - 1 + 1 = 1\), то есть удалить нужно ровно одно ребро, а ребро в графе всего одно — выбора нет.
Ответ: годится, например, граф из одной вершины с петлёй: петля — это цикл, а единственное остовное дерево такого графа — сама эта вершина без рёбер.
Приведите пример графа, который содержит цикл и у которого имеется единственное остовное дерево.
Возьмём граф, состоящий из единственной вершины \(A\) и петли при ней.
Цикл в этом графе есть: петля — это цикл длины 1.
Остовное дерево должно содержать все вершины графа, то есть вершину \(A\). Петля войти в него не может: дерево не имеет циклов, а петля — цикл. Значит, остовное дерево этого графа — сама вершина \(A\) без рёбер, то есть пустое дерево, и оно единственное.
Тот же вывод даёт подсчёт: \(v = 1\), \(e = 1\), цикломатическое число равно \(1 - 1 + 1 = 1\), то есть удалить нужно ровно одно ребро, а ребро в графе всего одно — выбора нет.
Ответ: годится, например, граф из одной вершины с петлёй: петля — это цикл, а единственное остовное дерево такого графа — сама эта вершина без рёбер.
