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


 

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

7472. Исследование электромеханических свойств двигателя постоянного тока последовательного возбуждения 108.09 KB
  Исследование электромеханических свойств двигателя постоянного тока последовательного возбуждения. Цель работы: Исследовать способы регулирования скорости вращения и реверсирования якоря двигателя, построить рабочие характеристики двигателя. Пояснен...
7473. Снятие кривой нагрева электродвигателя и определение постоянной времени нагрева 63.24 KB
  Снятие кривой нагрева электродвигателя и определение постоянной времени нагрева. Цель работы: Изучить процесс нагрева двигателя, получить опытным путем данные построения кривой нагрева электродвигателя и определить значение постоянной времени нагрев...
7474. Исследование трехфазного асинхронного двигателя 55.54 KB
  Исследование трехфазного асинхронного двигателя Цель работы: Экспериментально снять механическую характеристику трехфазного асинхронного двигателя и осуществить его реверс. Пояснения к работе: Для выполнения данной работы используют трехфазный асинх...
7475. Предпринимательство в России на современном этапе его развития 149 KB
  Введение Рыночная экономика предполагает становление и развитие предприятий различных организационно-правовых форм, основанных на разных видах частной собственности, появление новых собственников - как отдельных граждан, так и трудовых коллекти...
7476. Право граждан на отпуск и гарантия его реализации 260 KB
  Право граждан на отпуск и гарантия его реализации Введение Дипломная работа на тему: Право граждан на отпуск и гарантия его реализации определяет круг лиц, пользующихся ежегодными оплачиваемыми отпусками, обобщает положения законодательства о мини...
7477. Проект саду на даху торгівельного центру Центрум в м. Києві 3.8 MB
  Проект саду на даху торгівельного центру Центрум в м. Києві Вступ Слід зазначити, що на сьогодні Київ втратив незліченну кількість зон рекреації. З кожним роком високоповерхові будинки приходять на зміну міським, в минулому численним, садам і...
7478. Конструкция роликомаятниковой мельницы 1.9 MB
  ВВЕДЕНИЕ Объем производства различных строительных материалов возрастает из года в год. Увеличивается выпуск нерудных материалов, сборных железобетонных изделий и конструкций при значительном повышении их качества. Для производства строительных мате...
7479. Сортировочная горка. Пояснение назначения и работы устройств защиты на сортировочной горке 504.5 KB
  ВВЕДЕНИЕ. Неотъемлемой частью перевозочного процесса на железно-дорожном транспорте является технологическая работа, связанная с переработкой грузовых составов на специальных станциях, называемых сортировочными. Для выполнения сортировочной работы ...
7480. Проектирование технологии изготовления корпуса червячного редуктора в условиях автоматизированного производства 489.35 KB
  Тема проекта: Проектирование технологии изготовления корпуса червячного редуктора в условиях автоматизированного производства. Исходные данные к проекту: чертеж редуктора, годовой объем выпуска деталей - 1000 шт., работа участка...