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

Алгоритм нахождения сильных компонент графа

Читайте также:
  1. I. Липидный компонент
  2. I.2.4. Алгоритм симплекс-метода.
  3. II. 4.1. Алгоритм метода ветвей и границ
  4. IX. ПАДЕНИЕ И СМЕРТЬ ГРАФА РОБЕРТА
  5. LU – алгоритм нахождения собственных значений для несимметричных задач
  6. QR- алгоритм нахождения собственных значений
  7. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  8. SPA-компоненты линейки «АЛЬГАНИКА – 8 ВОДОРОСЛЕЙ»
  9. TRACE MODE 6: компоненты инструментальной системы
  10. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  11. Абиотические компоненты экосистемы.
  12. Алгоритм

Шаг 1. G – данный граф. Для G построить матрицу достижимости R. Получить матрицу контрдостижимости Q = RT.

Шаг 2. Положить С = R Ä Q, где Ä – поэлементное умножение матриц.

Шаг 3. Преобразовать матрицу С к блочно-диагональ-ному виду путем перестановки строк и столбцов. Каждая из диагональных подматриц соответствует сильной компоненте графа G. Останов.

 

Граф G*= (X*,V *) определяется так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (xi *, xj *) существует в G * тогда и только тогда, когда в G существует дуга (xi, xj), такая, что xi принадлежит ком­поненте, соответствующей вершине xi *, а xj –компоненте, соответствующей вершине xj*. Граф G* называют конденсацией графа G.

 

Пример решения задачи

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.

Решение. Матрица смежности графа имеет вид:

Матрица инцидентности графа имеет вид:

 

Построим матрицу достижимостей R. Для этого найдем множества достижимостей для каждой вершины графа по формуле (1), используя матрицу смежности А.

Матрица достижимостей графа примет вид:

 

Найдем сильные компоненты графа. Матрица контрдостижимостей Q = R T

Получим матрицу С, осуществив поэлементное умножение матриц R и Q. Матрица С примет вид:

Преобразуем полученную матрицу C к блочно-диагональному виду. Поменяем местами 1-й и 3-й столбцы матрицы.

Поменяем местами 1-ю и 3-ю строчки матрицы, получим

Из преобразованной матрицы видно, что в графе можно выделить три сильные компоненты:

.

Построим граф конденсации, вершинами которого сильные компоненты графа, т. е.

. Так как в исходном графе существует дуга (x2, x1), то в графе конденсации будет дуга, связывающая вершины . Дуга (x2, x3) позволяет сформировать дугу () графа конденсации. Дуга (x3, x4) позволяет сформировать дугу () графа конденсации. Граф конденсации исходного графа примет вид (рис. 7):

 

 

 

Рис. 7

Задание 4

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построить граф конденсации.

Варианты

         
       
       
         
         
       
       
         
         
       

ПЛАНАРНЫЕ ГРАФЫ

 

Во многих случаях не имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацию. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.

Таким образом, возникает понятие плоского графа. Плоским графом называется граф, вершины которого являются точками плоскости, а ребра – непрерывными линиями без самопересечений, соединяющими соответствующие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.

 
 

Примеры плоских графов.

А б

Рис. 8. Плоские графы

 

 
 

Любой граф, изоморфный плоскому графу, будем называть планарным. Граф на рис.9 является планарным, так как он изоморфен графу на рис 8.б.

Рис. 9.

Очевидны следующие утверждения:

1) всякий подграф планарного графа планарен;

2) граф планарен тогда и только тогда, когда каждая его связная компонента – планарный граф.

О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |

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



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