В графе n вершин и n-1 рёбер. Обязательно ли это дерево? Дайте контрпример и дополнительное достаточное условие.
Quant ResearchУровень: БазаNecessary not sufficient
В графе n вершин и n-1 рёбер. Обязательно ли это дерево? Дайте контрпример и дополнительное достаточное условие.
Подсказки
- Поместите цикл в одну компоненту.
- Числу рёбер нужно структурное условие.
Ответ
Нет: треугольник и изолированная вершина имеют 4 вершины и 3 ребра. Если добавить связность, граф будет деревом. Либо ацикличность вместе со счётом заставляет иметь одну компоненту.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros