Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Доказательство. , когда существует , такое, что: .
|
|
, когда существует 
, такое, что: 
.
По индукции (для 
верно).
Предположим, что это справедливо для всех 
.
Докажем для 
:
Если верно для 
и будет существовать дуга, то верно для . (
)
Следствие.
В -вершинном орграфе 
, 
матрицы достижимости
, когда вершина 
достижима из вершины 
.
Рекуррентная формула нахождения матрицы достижимости.
1. 
2 
3. 
Теорема. Матричное условие взаимной достижимости.
Вершины 
взаимно достижимы ó, когда соответствующие им строки в матрице достижимости равны.
Доказательство.
Необходимость.
Пусть взаимно достижимы.
Если вершина 
достижима из 
и 
, то стоят единицы в строках, если нет – то не стоят. Значит, строки равны.
Достаточность.
Пусть строки и равны (вершина достижима сама из себя). Тогда элемент 
, аналогично 
(вершины взаимно достижимы)
|
|