Образовательная панель 5
Введение в теорию графов
Краткая теория для тебя
Дерево
Дерево — связный ациклический неориентированный граф. То есть между любыми двумя вершинами существует путь, но нет циклов.

Свойства дерева
• Единственность пути: между любой парой вершин ровно один простой путь.
• Существование висячей вершины: в любом дереве есть хотя бы две вершины степени 1 (листья).
• Связь между числом вершин n и числом рёбер m: в дереве m = n − 1.

Правило умножения
Если эксперимент состоит из двух последовательных этапов, где на первом есть k способов, а на втором — m способов (независимо от первого), то всего способов k·m.
Пример: выбрать корону из 3 и мантию из 2 → 3·2 = 6 вариантов.
Проверь себя
Квиз по теме «Введение в теорию графов»
Проверьте свои знания и узнайте, насколько хорошо вы усвоили тему. Вы можете ответить на эти вопросы?
Начать тест
Что такое дерево?
Дальше
Проверить
Узнать результат
Какова формула для числа рёбер в дереве с n вершинами?
Дальше
Проверить
Узнать результат
Что гарантировано в любом дереве?
Дальше
Проверить
Узнать результат
Правило умножения даёт количество способов…
Дальше
Проверить
Узнать результат
Ничего страшного
Повтори еще раз
Пройти еще раз
Ничего страшного
Повтори еще раз
Пройти еще раз
Ничего страшного
Повтори еще раз
Пройти еще раз
Хороший результат
Повтори еще раз
Пройти еще раз
Хороший результат!
Повтори еще раз
Пройти еще раз
Отлично!
Пройти еще раз
Частые вопросы по теме