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