Презентации лекций / Презентация лекции 13 ДМ 20
.pdf
Элементыориентированного дерева
Вершины, из которых невыходят дуги,- листья. Если – начало, – конец дуги,то –отец, –сын.
Если – начало, – конец пути, то –предок, –потомок.
Путь из корня в лист–ветвь.
Максимальнаяиз длин ветвей– высотадерева.
Длина пути из корня ввершину –глубинавершины .
Подграф, состоящий из вершини дуг всехветвейс началом –поддеревоскорнем .
Высота поддерева с корнем –высотавершины .
|
|
Желтыми |
|
|
|||
|
пунктирными |
||
|
|
||
|
линиями |
||
|
|
||
|
обведены |
||
|
|||
|
|
поддеревья |
|
|
|
|
-корень
,,, -листья
– отец, и – егосыновья– предок, ,, – его потомки
→ → -ветвь
→ → → -ветвь Высотадереваравнатрем
Глубина равна1, высотаравна2
1
2
3
4
5
6
21
Бинарное ориентированное дерево
Ориентированноедеревоназывается бинарным,
еслиу каждой еговершиныимеется неболеедвух сыновей,
причем дуги, ведущие к ним,помечены разными метками.
Бинарноедеревоназывается полным,
еслиу всехеговершин (кромелистьев) имеетсяровнодва сына
и всееговетвиимеютодинаковую длину.
0
0 0
0 1 1
0
01
1 0 
1
1
2
3
4
5
6
22
План лекции
1.Понятие ориентированного графа
2.Изоморфные орграфы
3.Матрицы смежности и инцидентности
4.Ориентированные пути, циклы и цепи на орграфе
5.Ориентированные деревья
6.Отыскание кратчайших путей
23
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
||
|
Граф = ( ,) |
|
|
|
: → [ ;+∞) |
|
|
3 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
4 |
|||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
5 |
|
ρ( ) –вес= длина |
взвешенныйориентированныйграф (сеть) |
-путь |
|||||||
6 |
|||||||||
|
|
|
|
|
|
||||
дуги |
|
|
|
|
|
( ) = ∑ |
( ) - |
||
|
|
|
|
|
вес= длинапути |
|
|||
|
|
|
|
|
|
|
|||
Пусть и – вершиныграфа.Рассмотрим путииз в . Сравнимих длины(веса). 
Кратчайшийпуть |
|
Путьиз в наименьшей |
|
||
от до |
|
длины(веса) |
|
Длинакратчайшегопутииз в –расстояниеот до
Здесь«длина»- этовес,
анечислодуг!!!
|
2 |
|
|
|
Пути из в: |
|
|
|
|||
|
|
|
|
|
→ -путь длины2 |
|
5 |
|
|
→ → → -путь длины12 |
|
|
|
|
|
|
|
1 |
4 |
3 |
|
|
→ → -путь длины4 |
|
|
|
|
|
Кратчайший путьиз в: → . |
|
|
|
|
|
Расстояниеот до равно 2. |
|
|
|
|
|
|
Задачаократчайшихпутях:
Взаданнойсети найти расстояниеикратчайшийпуть
отфиксированнойвершины
до остальныхвершин
24
Общееописаниеалгоритма
Кначалукаждого -гошагавершиныделятсянадве группы:впервую( )входятвершины,расстояниедо которыхот уженайдены,вовторую( )-докоторых расстоянияещененайдены.
Вершины,докоторыхот расстоянияуженайдены, имеютпостояннуюметку (какразравнуюэтому расстоянию).
Меткиостальныхвершин–временные,иихнужно пересчитыватьна -мшаге:
временнаяметка ( )вершины -вескратчайшего путиот до, проходящеготолькочерезвершиныс постояннымиметками.
Вершинас самоймаленькойвременнойметкой -го шагаполучаетпостояннуюметку,равнуювременной. Этаметкаиестьискомоерасстояниеот доэтой вершины.Асамавершина-ближайшаяк среди вершинсвременнымиметками.
Обозначения
-расстояниеот до
|
вессамой«легкой»издуг , |
|
(еслиониесть) |
|
, = |
|
+∞, еслидуг , нет |
|
|
–множествовершин,расстояниедокоторыхоткначалу -гошаганайдены
–множествовершин,расстояниедокоторыхоткначалу -гошаганенайдены
( )–временнаяметкавершины,рассчитаннаяна-мшаге
1
2
3
4
5
6
25
|
|
-расстояниеот до |
|
|
|
|
|
|
|
|
вессамой «легкой»из дуг , |
|
|
(еслиони есть) |
|
, = |
|
|
|
+∞, еслидуг , нет |
|
|
|
– множествовершин,расстояниедокоторых откначалу -го шага найдены
– множествовершин,расстояниедокоторых откначалу -го шага ненайдены
( ) –временнаяметкавершины ,рассчитаннаяна-мшаге
Пример: |
|
|
1 |
|
1 |
|
|
|
|
|
4 |
|
||
|
2 |
|
|
|
5 |
|
1 |
1 |
|
|
|
|
|
|
|
1 |
1 |
3 |
3 |
|
|||
|
|
|||
|
|
|
||
|
|
|
|
|
|
|
|
|
-йшаг |
|
= , |
|
= = |
|
. |
|
|
|
|
|
||
|
|
|
|
|
|
|
-йшаг
Пусть = , ,…, , = \ . Если -пусто,
товсевозможныерасстоянияуженайдены.
Если ≠ ,тодлякаждойвершины из находимвременнуюметку
= { + ( ,)}.
Еслинидляоднойиз из минимумопределить нельзя,товсевозможныерасстоянияуженайдены. Впротивномслучаенаходимвершину(обозначимее
|
),длякоторой |
|
имеетнаименьшеезначение: |
||||||
|
|
|
|
|
|
= ( ). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вершине |
даемпостояннуюметку,равную |
|
|
||||
|
|
|
|
временной . |
|
|
|||
Тогда |
|
= |
|
-расстояниеот до |
и |
||||
|
|
|
|
≤ |
длявсех из . |
|
|
||
1
2
3
4
5
6
26