67600

Связность. Компоненты связности

Лекция

Математика и математический анализ

Компоненты связности Определения. Компонентой связности графа G сильной связности орграфа D наз. Матрицы достижимости и связности Пусть D матрица смежности ориентированного псевдографа D=VX или псевдографа G=VX где V={v1 vn}. Тогда отношение эквивалентности...

Русский

2014-09-12

135 KB

11 чел.

Лекция 9

Связность. Компоненты связности  

Определения.

Подграфом графа G  называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).

Подграф наз. собственным, если он отличен от самого графа.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

Орграф наз односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой.

Псевдографом, ассоциированным с ориентированным псевдографом D=(V,X) наз. псевдограф G=(V,X0), в котором X0 получается из X заменой всех упорядоченных пар (v,w) на неупорядоченные {v,w}.

Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.

Компонентой связности графа G (сильной связности орграфа D) наз. его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).

Примеры.

Матрицы достижимости и связности

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v1,…, vn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D).

Утверждение. Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из vi в vj.

Д-во

Для k=1 очевидно в силу построения матрицы A(D).

Пусть это справедливо для n=k-1. Т.е. в матрице Ak-1 в i-той строке на l-том месте стоит число, означающее кол-во маршрутов из vi в vl длины k1. Столбец под номером j матрицы A содержит числа, означающие кол-во дуг (ребер) из vl в vj (l-номер строки). Тогда скалярное произведение i-той строки матрицы Ak-1 на j-тый столбец матрицы A равен сумме произведений. Каждое произведение означает кол-во путей из vi в vj, проходящих через vl на предпоследнем шаге. В сумме получается общее кол-во.

Утверждение. Для того, чтобы n-вершинный орграф D с матрицей смежности A=A(D) имел хотя бы один контур, чтобы матрица K=A2+A3+… An имела ненулевые диагональные элементы (следствие предыдущего).

Пусть -отношение достижимости на множестве V всех вершин (неориентированного) графа G. (либо v=w, либо маршрут, соединяющий v и w).

Тогда

  1.  -отношение эквивалентности;
  2.  vw  вершины v,w принадлежат одной компоненте связности;
  3.  для класса эквивалентности V1 псевдограф G1, порожденный множеством V1, является компонентой связности псевдографа G.

Для орграфа.

Пусть 1-отношение достижимости на множестве V всех вершин ориентированного псевдографа D. Пусть 2-отношение двусторонней достижимости на множестве V. (2=11-1). Тогда

  1.  1 - рефлексивно, транзитивно;
  2.  2 – эквивалентность на V;
  3.  v2w  когда вершины v,w  одной компоненте сильной связности;
  4.  для класса эквивалентности V1 ориент. псевдограф D1, порожденный множеством V1, является компонентой связности ор. псевдографа G.

Число компонент сильной связности орграфа D обозначается P(D). (для неор. - P(G).

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

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

Пример.

Утверждение. Если D' – орграф, полученный в результате удаления нескольких вершин из орграфа D, то матрица смежности A(D') получается из матрицы смежности A(D) в результате удаления строк и столбцов, соответствующих удаленным вершинам. (Для неор. графа то же самое).

Определение. Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, элементы которой равны

Определение. Матрицей сильной связности орграфа D называется квадратная матрица S(D)=[sij] порядка n, элементы которой равны

Определение. Матрицей связности графа G называется квадратная матрица S(G)=[sij] порядка n, элементы которой равны

Утверждение. Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A2+A3+… An-1] (E- единичная матрица порядка n).

(Следует из предыдущего).

Утверждение. Пусть D=(V,X) – орграф, V={v1,…, vn}, A(D) – его матрица смежности. Тогда

  1.  T(D)=sign[E+A+A2+A3+… An-1],
  2.  S(D)=T(D)TT(D)  (TT-транспонированная матрица, - поэлементное умножение).

Алгоритм выделения компонент сильной связности.

1. Присваиваем p=1, S1=S(D).

2. Включаем в множество вершин Vp компоненты сильной связности Dp=(Vp,Xp) вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.

3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- кол-во компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу Sp+1, присваиваем p:=p+1 и переходим к п. 2.

Пример.

,

,

,

,

T(D)=sign[E+A+A2+A3+A4]=,

S(D)=TTT=.

Выделение компонент (сильной) связности.

1. p=1,

2. V1={v1, v3, v5},   

D1

3. ,

2'. V2={v2 },   

D2

3'. ,

2''. V3={v4 },

D3


 

А также другие работы, которые могут Вас заинтересовать

19109. Спектральный анализ непериодических сигналов 246 KB
  Лекция № 5. Спектральный анализ непериодических сигналов Для практических приложений является важным установление связи между преобразованием сигнала и соответствующим этому преобразованию изменением спектральных характеристик. Спектральная плотность сигнала...
19110. Физические измерительные системы и их математические модели 243.5 KB
  Лекция № 6. Физические измерительные системы и их математические модели Динамические измерительные системы в которых связи между измеряемыми величинами входными сигналами и выходными сигналами описываются дифференциальными уравнениями разнообразны по принци
19111. Динамические характеристики измерительных систем 245 KB
  Лекция № 7. Динамические характеристики измерительных систем Импульсная характеристика системы. Импульсной характеристикой стационарной измерительной системы описываемой оператором называют функцию являющуюся откликом системы на входной сигнал в виде функци...
19112. Модуляция сигналов в измерительных системах 185.5 KB
  Лекция № 8. Модуляция сигналов в измерительных системах Информационные преобразования в аналоговых блоках измерительных систем осуществляются над сигналами имеющими различные информативные параметры или другими словами над сигналами с различными видами модуля...
19113. Первичные преобразователи систем измерения физических величин 113.5 KB
  Лекция № 9. Первичные преобразователи систем измерения физических величин Эффективное управление сложными техническими объектами атомные электростанции объекты топливноэнергетического комплекса и пр. автоматизация технологических процессов дальнейшее разви...
19114. Пьезоэлектрические преобразователи 246 KB
  Лекция №10. Пьезоэлектрические преобразователи Пьезопреобразователи электромеханические преобразователи принцип действия которых основан на пьезоэлектрическом эффекте явлении возникновения электрической поляризации под действием механических напряжений. Е
19115. Пьезоэлектрические преобразователи, метод электромеханических аналогий 207.5 KB
  Лекция №11. Пьезоэлектрические преобразователи продолжение Так как пьезоэлектрический преобразователь представляет собой электроакустическую систему в которой электрические и механические характеристики взаимосвязаны то используя метод электромеханических ...
19116. Тензорезисторные методы измерения деформаций 234.5 KB
  Лекция №12. Тензорезисторные методы измерения деформаций Измерение деформаций в объектах контроля осуществляют тензометрами приборами для измерения деформаций. Часто в тензометрах в качестве первичного измерительного преобразователя используют тензорезисторы. ...
19117. Емкостные преобразователи 203 KB
  Лекция №13. Емкостные преобразователи Емкостный преобразователь представляет собой конденсатор электрические параметры которого изменяются под действием входной величины. Конденсатор состоит из двух электродов к которым подсоединены выводные концы. Пространство...