Урок Тема Основы теории графов Деревья. Лекция
 Скачать 84.98 Kb.
|
|
Урок 9.
Лекция. Деревья. Решение комбинаторных задач с помощью деревьев. https://vk.com/video/@id21896087?z=video21896087_456241498%2Fpl_21896087_-2 Справочные материалы. Теория графов не обладает устоявшейся терминологией. Поэтому в разных публикациях могут использоваться разные термины.  Деревья. Граф связный, если из любой вершины в любую другую можно пройти по ребрам. Циклом называется замкнутый путь из ребер. Деревом называется связный граф без циклов. Дерево – это связный граф без циклов, у которого между парами вершин имеется только одно ребро. Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья. С помощью деревьев или леса удобно решать комбинаторные задачи или иллюстрировать их решение. Задача 1. У ковбоя Джека две лошади: каурой и гнедой масти, два седла: красное и зелёное, две пары шпор: длинные и короткие, два револьвера: один марки «Кольт», другой – «Смит – и – Вессон». Сколькими способами Джек может экипироваться для конной прогулки по прериям?  Получается 16 способов экипировки. Задача 2.  Задача 3. В столовой есть на выбор два первых блюда: щи (Щ) и борщ (Б) три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т) два напитка: компот (К) и сок (С) Сколько вариантов обедов можно составить из этих блюд и каких? Построим дерево для перечисления вариантов:  Количество вариантов обедов: 12 |