АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Матрица достижимостей

Читайте также:
  1. Nikon D7100 - матрица APS-C в идеальном оформлении
  2. SWOT- матрица
  3. V2: ДЕ 4 – Линейные отображения. Линейные операции над матрицами
  4. Анализ матричных данных (матрица приоритетов)
  5. Б1 2. Линейный оператор в конечномероном пространстве, его матрица. Характеристический многочлен линейного оператора. Собственные числа и собств векторы.
  6. Билет 11. Различные уравнения прямой в пространстве. Матрица перехода к новому базису.
  7. Билет 13. Линейные операторы. Матрица линейного оператора.
  8. Билет 23. Матрица SWOT – анализа.
  9. Билет 27 Ортогональный оператор и его матрица в ортонормированном базисе
  10. Билет 27. Жорданов базис и жорданова матрица линейного оператора в комплексном пространстве.
  11. Билет 32. Сопряженный оператор. Существование и единственность. Матрица сопряженного оператора.
  12. Билет26 Самосопряженный оператор и его матрица в ортонормированном базисе.

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

Множество вершин 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.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)