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


 

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

38551. ШЛЯХИ ВДОСКОНАЛЕННЯ МАРКЕТИНГОВОЇ ДІЯЛЬНОСТІ ТОВ «ЧАЙКА» 1.47 MB
  Ефективність управління маркетинговою діяльністю фірми визначається досягненням концепцією маркетингової взаємодії таких цілей: максимально можливого рівня споживання; максимально широкий вибір товарів, які надаються споживачам; максимальне підвищення якості життя суспільства в цілому та його окремих членів
38552. Розробка заходів щодо зниження викидів прокатного виробництва на стан навколишнього середовища на прикладі прокатного цеху ВАТ «Донецький Металургійний завод» 1.45 MB
  Аналіз складу викидів в атмосферу свідчить що в 2008 році в порівнянні з 2000 роком знизилися викиди оксиду вуглецю на 12 діоксиду сірки на 44 і пилу на 37 однак при цьому зросли викиди зєднань азоту на 48 . Жителі промислових центрів дихають не тільки пилом але і важкими металами фенолом фтористим воднем бензапіреном діоксидом азоту і іншими сполуками. По найбільш небезпечних інгредієнтах: діоксиду азоту пилу бензапірену і формальдегіду рівень забруднення атмосфери залишається високим. Як паливо використовується...
38553. Информационное и программное обеспечение для решения задач автоматизации хранения и обработки информации при организации работы парабанковского предприятия 2.58 MB
  Объединение компьютеров в сети позволило значительно повысить производительность труда. Именно здесь происходит соединение трех основных элементов этого процесса и достигается его главная цель производства предметов труда оказание услуг либо техникоэкономическое обеспечение и управление этими процессами. От того как организованы рабочие места во многом зависит эффективность использования самого труда орудий и средств производства и соответственно производительность труда себестоимость выпускаемой продукции ее качество и многие...
38554. Процесс взаимного формирования массовой культуры и социума, состоящего из потребителей продуктов этой культуры 55 KB
  Таков социальнопсихологический аспект механизма потребления производства медиапродукта.Достижения этой индустрии сегодня позволяют продюсерам не только быть посредниками между интересами потребителей и творчеством производителей но и с одной стороны формировать эти интересы а с другой создавать медиапроекты являющиеся оптимальными для конкретной социальной коньюктуры духовными продуктами. Медиапродукт является необходимым товаром и в то же время способен сам коррегировать количественную и качественную степень необходимости...
38556. СОВЕРШЕНСТВОВАНИЕ КОММУНИКАТИВНОЙ ПОЛИТИКИ ПРЕДПРИЯТИЯ (на примере ООО «Фудсервис ЛТД») 4.85 MB
  Конкурентное окружение компании и использование коммуникаций в конкурентной борьбе. В условиях рыночных экономических отношений торговопосреднические компании играют огромную роль влияя на всю систему распределения товаров от производителей к розничным покупателям. Так как эффективность работы и конкурентоспособность торговопосреднической компании всецело зависит от успешного взаимодействия с различными рыночными субъектами: производителями розничными продавцами и покупателями то особую важность приобретает построение...
38557. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКИХ И АППАРАТУРНЫХ СХЕМ ПРОИЗВОДСТВА И ОТДЕЛЬНЫХ СТАДИЙ ПРОЦЕССА 2.81 MB
  Точки контроля Норма частиц в 1 литре воздуха Из заборной шахты 1000030000 После висциносного фильтра 750025000 Перед головным фильтром 20006000 После головного фильтра 4001200 После индивидуального фильтра Не более 10 Стерильность воздушность систем проверяют ежедневно с помощью чашек Петри или путём прохождения воздуха из продувок коллектора через стерильный фильтрик заполненный углём или пропускают через стерильный мембранный фильтр с последующим пересевом на мясопептонные среды. Готовят 2 среды контрольную и опытную в которой один...
38558. ВПЛИВ ПОСТІЙНОГО МАГНІТНОГО ПОЛЯ НА СТРУКТУРУ ТА ЕЛЕКТРИЧНІ ВЛАСТИВОСТІ ПОЛІМЕРНИХ КОМПОЗИТІВ 12.58 MB
  Вплив постійного магнітного поля на структуру і електричні властивості полімерних композитів. Досліджено сплив постійного магнітного поля ПМП на електричні властивості композиту на основі утвореної поліуретанової матриці з наповнювачем феромагнітним оксидом заліза Fe2O3 показано що під впливом постійного магнітного поля композиція набуває упорядкованої структури з анізотропними властивостями а саме зміна діелектричної проникності яка залежать від напрямку ПМП. Влияние постоянного магнитного поля на структуру и электрические свойства...
38559. Модифікація гена kanMX4, що забезпечує резистентність до антибіотика генетицину 1.36 MB
  Це у значній мірі відбувається тому що клітинний цикл та фізіологічні процеси клітин дріжджів дуже подібні до відповідних процесів людських клітин і тому основні клітинні механізми реплікація ДНК рекомбінація поділ клітини і метаболізм мають багато спільних рис. пар основ плазмідної ДНК яку в деяких штамах складають кіллерні плазміди; мітохондріальний геном 75 тис. Отримані гелі можуть бути використані для проведення Саузернблот аналізу що супроводжується гібридизацією або для ізоляції хромосомної ДНК в чистому вигляді. Досить...