Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Базовые конкурентные стратегии компании и основные предпосылки их использования. Матрица конкуренции М. Портера.
  2. Взаимные многополюсники. Недиссипативные многополюсники. Определение “недиссипативность” в терминах “матрица сопротивлений” и “матрица рассеяния”.
  3. Для оценки возможности выведения на рынок новых товаров используется матрица Ансоффа, которая позволяет выбрать тип стратегии роста.
  4. Идеальный циркулятор. Идеальный направленный ответвитель. Матрица рассеяния, принцип действия, области применения.
  5. Концепция базовой стратегии (виды базовых стратегий, матрица возможностей, условия выбора).
  6. Линейные операции над матрицами. Умножение матриц. Свойства.
  7. Матрица SWOT
  8. Матрица Абеля
  9. Матрица Бостонской Консультативной Группы (БКГ).
  10. Матрица Бостонской консультационной группы

Задач, в которых используется понятие достижимости, довольно много. Вот одна из них. Граф может быть моделью какой-то организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица хi быть передана другому лицу хj , т. е. существует ли путь, идущий от вершины хi к вершине хj . Если такой путь существует, то говорят, что вершина хj достижима из вершины хi . Можно интересоваться достижимостью вершины хj из вершины хi только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. п. задачи.

 

Достижимость в графе описывается матрицей достижимости R=[rij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

 

rij=1, если вершина хj достижима из хi ,

 

rij=0, в противном случае.

 

Множество вершин R(xi)графа G, достижимых из заданной вершины xi , состоит из таких элементов xi , для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г+1(xi) является множеством таких вершин xj , которые достижимы из xi с использованием путей длины 1, то множество Г++1(xi)) = Г+2(xi) состоит из вершин, достижимых из xi с использованием путей длины 2. Аналогично Г+p(xi)является множеством вершин, которые достижимы из xi с помощью путей длины p.

 

Так как любая вершина графа, которая достижима из xi , должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, ..., или p, то множество вершин, достижимых для вершины xi , можно представить в виде

 

R (xi) = { xi } Г+1(xi) Г+2(xi) ... Г+p(xi).

 

Как видим, множество достижимых вершин R(xi) представляет собой прямое транзитивное замыкание вершины xi , т. е. R (xi) = T+(xi). Следовательно, для построения матрицы достижимости находим достижимые множества R (xi)для всех вершин xi X. Полагая, rij=1, если xj R (xi)и rij=0 в противном случае.

Рис. 4.1. Достижимость в графе: а –граф; б – матрица смежности; в – матрица достижимости; г- матрица контрдостижимости.



 

 

Для графа, приведенного на рис. 4.1,а, множества достижимостей находятся следующим образом:

 

R (х1) = { х1 } { х2, х5 } { х2, х4, х5 } { х2, х4, х5 } = { х1, х2, х4, х5 },

 

R (х2) = { х2 } { х2, х4 } { х2, х4, х5 } { х2, х4, х5 } = { х2, х4, х5 },

 

R (х3) = { х3 } { х4 } { х5 } { х5 } = { х3, х4, х5 },

 

R (х4) = { х4 } { х5 } { х5 } = { х4, х5 },

 

R (х5) = { х5 } { х5 } = { х5 },

 

R (х6) = { х6 } { х3, х7 } { х4, х6 } { х3, х5, х7 } { х4, х5, х6 } = { х3, х4, х5, х6, х7},

 

R (х7) = { х7 } { х4, х6 } { х3, х5, х7 } { х4, х5, х6 } = { х3, х4, х5, х6, х7 }.

 

Матрица достижимости имеет вид, как показано на рис. 4.1,в. Матрицу достижимости можно построить по матрице смежности (рис. 4.1,б), формируя множества T+xi)для каждой вершины xi .

 


Дата добавления: 2015-04-18; просмотров: 496; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты