Дискретка / diskretochka (1)
.pdfВ связном орграфе существует Эйлеров путь , когда найдутся такие вершины и , что , а степени исхода и захода остальных вершин совпадают. Без доказательства.
46.Обход орграфа. Необходимое и достаточное условие существования обхода.
Обходом орграфа называется маршрут, содержащий все его дуги.
Слои орграфа (сильные компоненты) – классы отношения взаимной достижимости.
Теорема (критерий существования обхода). В связанном орграфе существует обход
для каждого слоя существует не более одной дуги с началом(концом) в этом слое и концом(началом) вне его.
Доказательство.
Необходимость.
Имеется обход. От противного, что существует слой (сильная компонента) и есть 2 дуги.
1 достижима из
Пусть есть обход П = П1 1, 1 П2 2, 2 П3 , значит существует путь из 1 в , то есть достижима из 1 – противоречие. Существует не более одной дуги. Достаточность. (?)
Предположим, что есть много слоѐв, также существует слой, в которой не входит ни одна дуга, и существует слой, из которого не выходит ни одна дуга.
П1 1 2 П2 2 3 … П−1 −1 П
47.Орсети, кратчайшие пути, алгоритм Дейкстры.
Ориентированная сеть (орсеть) – связный орграф с положительными весами на дугах. Если в сети существует вершина, из которой достижимы все остальные вершины, то сеть называется корневой, а вершина – корнем.
Вес сети – сумма весов всех дуг сети.
Кратчайший путь – путь, сумма весов дуг которого наименьшая из всех путей из корня до вершины.
Алгоритм Дейкстры.
1)Положим метку , метки всех остальных вершин .
Множество окрашенных вершин . 2)Пересчитываются метки всех неокрашенных вершин :
, среди них выбираются вершины с наименьшей меткой и окрашиваются одна из дуг , которая инцидентна.
3)Если все вершины окрашены, то конец алгоритма – длина кратчайшего пути, окрашенные дуги – длина кратчайшего пути; в противном случае переходим к шагу 2.