![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Матрицы достижимостей и контрадостижимостей ⇐ ПредыдущаяСтр 4 из 4
Матрица достижимостей Множество вершин
Матрица контрадостижимостей (обратных достижимостей) Аналогично построению достижимого множества
Из определений следует, что Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, приведенного на рис. 5. °
° °
° ° ° ° Рис. 5.
Определим множества достижимостей для вершин графа:
Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:
Так как Можно определить также матрицы ограниченных достижимостей и контрдостижимостей, если потребовать, чтобы длины путей не превышали некоторого заданного числа. Тогда Граф называют транзитивным, если из существования дуг
|