 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Матрица достижимостей
Вершина графа 
называется достижимой из вершины 
того же графа, если существует по крайней мере один путь из в .
Множество вершин R(vi), достижимых из некоторой вершины 
, определяется следующим выражением:
2.9
Действительно, первым элементом множества 
является вершина , которая достижима из себя самой с помощью пути длины нуль; Г(vi) – множество вершин vj, достижимых из vi с использованием путей длины единица; Г2(vi) – множество вершин, достижимых из vi с использованием путей длины два; 
- множество вершин, достижимых из vi с использованием путей длины p. Таким образом, множество R(vi) получается путем последовательного выполнения слева направо операции объединения в выражении (2.9) до тех пор, пока мощность текущего множества не перестанет увеличиваться при очередной операции объединения. С этого момента последующие операции объединения не будут давать новых элементов множеству R(vi). Число объединений, которые необходимо выполнить, зависит от графа G. Но если граф конечен, то p<n, где n – число вершин графа.
Матрицей достижимостей 
называется квадратная матрица порядка n, элемент которой
Пример. Построить матрицу достижимостей графа G, представленного на рис. 2.6.
Рис. 2.6
Решение. X={x1, x2, x3, x4}; Г(х1)={x2}; Г(х2)={x3}; Г(х3)={x4}; Г(х4)={x3}.
;
;
;
.
Следовательно, матрица достижимостей имеет вид:
.
Очевидно, что элементы di,i=1, i=1, 2, …, n, так как каждая вершина достижима из себя самой.
Матрица контрдостижимостей (обратных достижимостей) 
определяется следующим образом:
2.10
где Q(vi) – множество таких вершин viÎV, что из любой вершины этого множества можно достигнуть вершину vi:
2.11
где 
- множество вершин, из которых достижима вершина vi с использованием пути длины единица; 
) – множество вершин, из которых достижима вершина vi с использованием пути длины два и т.д. Операция объединения в выражении (2.10) выполняется слева направо до тех пор, пока очередное объединение не перестанет изменять “текущее множество”.
Пример. Построить матрицу контрдостижимостей Q для графа G рис. 2.6.
Решение. 
Матрица контрдостижимостей будет иметь вид:
.
Из определения матриц D и Q следует, что Q=DT. Так как D(vi) является множеством вершин, достижимых из 
, а Q(vj) – множество вершин, из которых достижима вершина vj, то D(vi) 
- множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от vi к vj. Эти вершины называются существенными (неотъемлемыми) относительно двух концевых вершин vi и vj. Вершины 
называются несущественными (избыточными), так как их удаление не влияет на пути от vi к vj.
Поиск по сайту: