Маша построила дерево. А потом посчитала количество вершин и рёбер в нём. У неё получилось, что количество вершин равно 9, а рёбер 9. Правильно ли Маша построила дерево?
Вероятность и статистика 8 класс Теория графов дерево граф вершины рёбра формула Эйлера связный
Маша допустила ошибку.
Объяснение:
Дерево – это связный граф без циклов. В любом дереве количество рёбер всегда на одно меньше, чем количество вершин. Это можно доказать по индукции или рассмотреть так:
В случае Маши, если вершин 9, то рёбер должно быть 8. Поэтому дерево, которое построила Маша, либо содержит цикл, либо несвязно, и, следовательно, не является деревом.