Дискретка / diskretochka (1)

В связном орграфе существует Эйлеров путь , когда найдутся такие вершины и , что , а степени исхода и захода остальных вершин совпадают. Без доказательства.

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.