Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Достижимость

Вершина графа хi называется достижимой из вершины xj того же графа, если существует по крайней мере один путь из xi в xj.

Множество вершин R(xi), достижимых из некоторой вершины , определяется следующим выражением:

(2.9)

Действительно, первым элементом множества R(xi) является вершина xi, которая достижима из себя самой с помощью пути длины нуль; Г(xi) – множество вершин xj, достижимых из xi с использованием путей длины единица; Г2(xi) – множество вершин, достижимых из xi с использованием путей длины два; - множество вершин, достижимых из xi с использованием путей длины p. Таким образом, множество R(xi) получается путем последовательного выполнения слева направо операции объединения в выражении (2.9) до тех пор, пока мощность текущего множества не перестанет увеличиваться при очередной операции объединения. С этого момента последующие операции объединения не будут давать новых элементов множеству R(xi). Число объединений, которые необходимо выполнить, зависит от графа G. Но если граф конечен, то p<n, где n – число вершин графа.

Матрицей достижимостей называется квадратная матрица порядка n, элемент которой di,j =1, если , и di,j=0 в противном случае.

Пример. Построить матрицу достижимостей графа 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, так как каждая вершина достижима из себя самой.

 

Матрица контрдостижимостей (обратных достижимостей) определяется следующим образом:

где Q(xi) – множество таких вершин xiÎX, что из любой вершины этого множества можно достигнуть вершину xi:

(2.10)

где - множество вершин, из которых достижима вершина xi с исполь-зованием пути длины единица; ) – множество вершин, из которых достижима вершина xi с использованием пути длины два и т.д. Операция объединения в выражении (2.10) выполняется слева направо до тех пор, пока очередное объединение не перестанет изменять “текущее множество”.

Пример. Построить матрицу контрдостижимостей Q для графа G рис. 2.6.

Решение.

Матрица контрдостижимостей будет иметь вид:

.

Из определения матриц D и Q следует, что Q=DT. Так как D(xi) является множеством вершин, достижимых из , а Q(xj) – множество вершин, из которых достижима вершина xj, то D(xi) - множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от xi к xj. Эти вершины называются существенными (неотъемлемыми) относительно двух концевых вершин xi и xj. Вершины называются несущественными (избыточными), так как их удаление не влияет на пути от xi к xj.

 


Дата добавления: 2015-10-13; просмотров: 73 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Матричные представления графа| Основные определения

mybiblioteka.su - 2015-2024 год. (0.007 сек.)