Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад
Новый рекорд!

Очки опыта

0

Обракоины

0
Как вам тренажер?
Следующая тема
Очки
0
Решено
0
Время
00:00:00

Бесплатные занятия

Оформите подписку, чтобы заниматься без ограничений.

Вы не вошли в аккаунт

Создайте бесплатный аккаунт, чтобы сохранить прогресс и получить персональную подборку полезных материалов.

Настройки

Остановка

Длительность тренировки

Времени на один вопрос

Другие тренажеры по теме
Cледующая тема
Все тренажеры

Ошибки

Здесь появятся ошибки, допущенные во время тренировки.

Прогресс

Завершите тренировку, чтобы освоить навык.

О тренажере

Деревья: вершины и ребра

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

Для кого этот тренажер

Тренажер предназначен для учеников 8 класса, которые знакомы с основными понятиями теории графов.

Какие задания

  • число ребер дерева по числу вершин и наоборот;
  • количество висячих вершин на рисунке;
  • длина пути между двумя вершинами;
  • сколько ребер удалить из графа, чтобы получить дерево.

Ученик применяет свойство дерева или считает по рисунку и вводит число.

Чему научится ученик

Ученик научится использовать связь между числом вершин и ребер дерева и находить единственный путь между вершинами.

Теория

Почему в дереве на одно ребро меньше, чем вершин

Дерево — связный граф без циклов. Начните с одной вершины: в таком дереве ребер еще нет. При присоединении каждой новой вершины достаточно одного ребра. Второе ребро от нее к уже построенному дереву замкнуло бы цикл. Так получается правило: у дерева с n вершинами ровно n − 1 ребро.

Например, соединим станции А, Б, В в цепочку и добавим к станции Б ветку до станции Г. Теперь есть четыре вершины и три ребра. От А до Г ведет единственный простой путь: А — Б — Г. Его длина равна двум ребрам. Вершины А, В и Г висячие: из каждой выходит ровно одно ребро.

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

Вернуться к тренажерам

Предложить улучшение