Презентации лекций / Презентация лекции 10 ДМ 20
.pdf
Тема 10 «Деревья»
«Дискретная математика» Олейник Татьяна Анатольевна
кафедра ВМ-1
План лекции
1.Определение и основные свойства деревьев
2.Остовы графа
3.Построение минимального остова
4.Кодирование деревьев
2
|
|
1 |
|
|
2 |
|
Вграфе нет циклов |
3 |
Графсвязный |
4 |
дерево
Дерево? |
Дерево? |
Дерево?
3
Нет |
Да |
|
|
Нет |
|
Задача. Нарисовать диаграммы всех деревьев с 1, 2, 3, 4 вершинами. |
3 |
|
= − |
Графсвязный |
Вграфенетциклов |
= − |
Вграфенетциклов |
Дерево- |
|
|
|
Графсвязный |
||
|
Графсвязный |
||
Добавлениелюбогоребра |
|
||
|
|
||
приводиткобразованию |
Вграфенет |
Каждоеребро-мост |
|
ровноодногопростого |
циклов |
||
|
|||
цикла |
|
||
|
|
Любыедвевершины графаможносоединить простойцепью,причем
единственной
4
1
2
3
4
Лес
Лес? |
Лес? |
Лес?
5
Да |
Да |
|
|
Нет |
|
Как можно охарактеризовать компоненты связности леса? |
5 |
|
|
|
|
|
|
|
1 |
|
|
Подграфграфа = ( ,) |
|
|
- |
2 |
|
|
|
|
|
3 |
|||
|
|
|
|
|
|
||
= |
, |
: |
|
|
|
остовный |
4 |
|
|
|
= |
|
|
подграф |
|
|
|
|
|
|
|
|
|
= ( ,) |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|||
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
1 |
|
|
|
Подграфграфа = ( ,) |
2 |
|||||
|
|
3 |
||||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
|
|
= |
, : |
= |
|
остовграфа |
||||
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Дерево
= ( ,) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
7
|
1 |
|
2 |
|
3 |
1способ–последовательноеудалениереберизциклов |
4 |
Если вграфеестьциклы, выбираемлюбой из них, удаляем из негокакое-нибудь ребро(«разрываемцикл»).
Если вновомграфе есть циклы, то выбираемлюбой из них, удаляемиз него какое-нибудьребро(«разрываемцикл»)…
Итак дотех пор, пока вграфеестьциклы.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
Сколькореберпридется |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
удалить? |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|||
|
|
|
|
|
||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
|
1 |
|
2 |
|
3 |
2способ–добавлениеребербезобразованияциклов |
4 |
Берем остовныйподграфбез ребер.
|
Добавляемкнему какое-нибудьребрографа– любое, нотак,чтобыне |
|
||||
|
образовалисьциклы. |
|
|
|
||
|
|
|
|
К новомуподграфудобавляемкакое-нибудьребро графа– любое, |
|
|
|
|
|
|
нотак, чтобыне образовалисьциклы... |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
Сколькореберпридется |
|
|
|
|
|
|
|
|
||
|
|
|
добавить? |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|||
|
|
|
|
|
||
|
|
|
|
|
||
|
|
|
|
9 |
||
|
|
|
|
|
|
|
1
2
3
4
= …
|
|
… |
|
|
|
Числоостововвсвязном |
|
|
… |
|
− |
Алгебраические |
обыкновенномграферавно |
… |
… |
… |
дополнениявсехэлементов |
алгебраическому |
||
|
|
… |
|
|
матрицыКирхгофаравны |
дополнениюлюбого |
|
|
|
||||
|
|
|
|
|
междусобой |
элементаегоматрицы |
матрицаКирхгофа |
|
|
|
Кирхгофа |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
−1 |
−1 |
|
2 |
|
2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
= |
−1 |
2 |
−1 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|||||
1 |
|
|
|
|
−1 |
−1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
, |
= (−1) |
2 |
−1 |
= 3 |
1 |
3 |
1 |
|
3 |
1 |
|
|
|
|
3 |
|
|
|
−1 |
2 |
|
|
|
|
|
3 |
||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |