Настройки
Прогресс
Завершите тренировку, чтобы освоить навык.
Деревья: вершины и ребра
Дерево — это связный граф без циклов. Между любыми двумя вершинами дерева есть единственный путь, а ребер в нем на одно меньше, чем вершин. Деревья используют для перебора вариантов и для описания случайных опытов.
Для кого этот тренажер
Тренажер предназначен для учеников 8 класса, которые знакомы с основными понятиями теории графов.
Какие задания
- число ребер дерева по числу вершин и наоборот;
- количество висячих вершин на рисунке;
- длина пути между двумя вершинами;
- сколько ребер удалить из графа, чтобы получить дерево.
Ученик применяет свойство дерева или считает по рисунку и вводит число.
Чему научится ученик
Ученик научится использовать связь между числом вершин и ребер дерева и находить единственный путь между вершинами.
Теория
Почему в дереве на одно ребро меньше, чем вершин
Дерево — связный граф без циклов. Начните с одной вершины: в таком дереве ребер еще нет. При присоединении каждой новой вершины достаточно одного ребра. Второе ребро от нее к уже построенному дереву замкнуло бы цикл. Так получается правило: у дерева с n вершинами ровно n − 1 ребро.
Например, соединим станции А, Б, В в цепочку и добавим к станции Б ветку до станции Г. Теперь есть четыре вершины и три ребра. От А до Г ведет единственный простой путь: А — Б — Г. Его длина равна двум ребрам. Вершины А, В и Г висячие: из каждой выходит ровно одно ребро.
Если в связном графе есть цикл, одно ребро этого цикла можно убрать: его концы все еще соединены обходным путем. Так удаляют лишние ребра, пока граф не станет деревом на тех же вершинах.