Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Рекуррентная формула нахождения матрицы достижимости



1.

2

3.

Теорема. Матричное условие взаимной достижимости.

Вершины взаимно достижимы ó, когда соответствующие им строки в матрице достижимости равны.

Доказательство.

Необходимость.

Пусть взаимно достижимы.

Если вершина достижима из и , то стоят единицы в строках, если нет – то не стоят. Значит, строки равны.

Достаточность.

Пусть строки и равны (вершина достижима сама из себя). Тогда элемент , аналогично (вершины взаимно достижимы)

Необходимое и достаточное условие, для того, чтобы орграф был Эйлеровым. Необходимое и достаточное условие для существования Эйлерова пути в орграфе.

Эйлеров путь – путь длины m (в данном случае, ребро – дуга в обе стороны)

Эйлеров орграф – орграф, в котором есть циклический Эйлеров путь.

Связный орграф – орграф, симметризация которого является связной.

Теорема. Критерий эйлеровости орграфа.

Связный орграф Эйлеров ó, когда для любой вершины степень ее исхода равна степени захода. Без доказательства.

Теорема. Критерий существования Эйлерова пути в орграфе.

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

Орсети, кратчайшие пути, алгоритм Дейкстры.

Ориентированная сеть (орсеть) – связный граф с положительными весами на дугах.

Если в сети существует вершина, из которой достижимы все остальные вершины, то сеть называется корневой, а вершина – корнем.

Вес сети – сумма весов всех дуг сети.

Кратчайший путь – путь, сумма весов дуг которого наименьшая из всех путей из корня до вершины.

Алгоритм Дейкстры.

1)Положим метку , метки всех остальных вершин . ?

Множество окрашенных вершин . ?

2)Пересчитываются метки всех неокрашенных вершин :

, среди них выбираются вершины с наименьшей меткой и окрашиваются одна из дуг , которая инцидентна.

3)Если все вершины окрашены, то конец алгоритма – длина кратчайшего пути, окрашенные дуги – длина кратчайшего пути; в противном случае переходим к шагу 2.

Необходимое и достаточное условие существования правильной нумерации в орграфе. Следствия.

Гамильтонова цепь – бесконтурный путь длины .

Гамильтонов контур – контур длины .

Гамильтонов орграф – орграф, в котором существует Гамильтонов контур.

Орграф правильно занумерован, если .



Теорема. Критерий существования правильной нумерации в орграфе.

В орграфе существует правильная нумерация ó, когда это бесконтурный орграф.

Доказательство.

Необходимость.

Пусть существует правильная нумерация вершин.

От противного: есть контур.

Если нумерация правильная, то:

– противоречие.

Достаточность – отсутствует.

Следствие 1: в каждом бесконтурном орграфе есть по крайней мере 1 источник и 1 сток.

Доказательство.

Если орграф бесконтурный, то существует правильная нумерация вершин.

Нет дуги, входящей в . Нет дуги исходящей из .

Следствие 2: в каждом бесконтурном орграфе существует единственная база.

Следствие 3: в каждом неориентированном графе можно ввести ориентацию ребер так, что граф превращается в бесконтурный орграф.

Очевидно: ; .

Направленный граф – орграф с антисимметричным отношением смежности, нет встречных дуг.

Следствие 4: в каждом направленном графе можно переориентировать дуги так, что граф превращается в бесконтурный.

Доказательство.

. Если – оставляем, если – меняем ориентацию.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!