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


 

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

38786. Техническая характеристика грузового автомобиля ЗИЛ-130 1.06 MB
  Для обеспечения длительной и безопасной работы автомобиля при проведении ТО сборочные единицы смазывают. Места агрегатов автомобиля требующие периодически пополнения или смены масла и смазок указаны в таблице смазывания таблица №7. Замену масла смазку сборочных единиц и их соединений выполняют при неработающем двигателе. При замене масла в картере двигателя и в других сборочных единицах сливают масло сразу после остановки автомобиля когда оно горячее.
38787. ОРГАНИЗАЦИЯ УЧЁТА ПРОЧИХ ДОХОДОВ И РАСХОДОВ ООО «СТРОЙИНДУСТРИЯ» 263.5 KB
  Доходы и расходы: понятие их сущность значение виды 10 1. Проанализировать прочие доходы и расходы. Предметом исследования являются прочие доходы и расходы ООО Стройиндустрия.Доходы и расходы: понятие их сущность значения виды В соответствии с п.
38789. Конкурентоспособность и ее повышение ООО «Урал-инструмент-Пумори» 1.13 MB
  Продвижение товара с помощью интернеттехнологий. Повышение конкурентоспособности ООО УралинструментПумори на основе интернеттехнологий продвижения товара. Организационная структура управления ООО УралинструментПумори. Экспертная оценка конкурентоспособности ООО УралинструментПумори.
38790. ДИНАМИКА ЦЕННОСТНЫХ ОРИЕНТАЦИЙ МОЛОДЕЖИ В ОТНОШЕНИИ СЕМЬИ И БРАКА В УСЛОВИЯХ МОДЕРНИЗАЦИИ РОССИЙСКОГО СОЦИУМА 758 KB
  Теоретикометодологические основы исследования и ценностных ориентаций молодежи в отношении семьи и брака. Некоторые теоретические подходы к изучению ценностных ориентаций молодежи в отношении семьи и брака. Факторы формирования и тенденции развития ценностных ориентаций современной российской молодежи в отношении семьи и брака.
38791. Влияние восстановленного глутатиона и ингибитора каталазы на пероксидную резистентность и скорость лизиса эритроцитов при действии хлорида железа 650 KB
  Установлено, что при ингибировании каталазной активности азидом натрия, в том числе при действии хлорида железа скорость гемолиза эритроцитов возрастает. Хлорид железа (III) в концентрации 0,5% вызывал полный лизис эритроцитов человека за 5 мин инкубации с максимумом лизиса от 1,5 до 3,5 минут инкубации вне зависимости от предварительной обработки эритроцитов
38792. Методы оценки кредитоспособности ссудозаемщика коммерческого банка 1.08 MB
  Кредит выступает опорой современной экономики, неотъемлемым элементом экономического развития. Его используют как крупные предприятия и объединения, так и малые производственные, сельскохозяйственные и торговые структуры; как государства, правительства, так и отдельные граждане. Он становится неизбежным атрибутом товарного хозяйства.
38793. Лісові природно-заповідні території як осередки еволюційного збереження лісового дендрофіторізноманіття 403 KB
  Сучасний стан лісових генетичних ресурсів та стратегії їх збереження. Стратегії збереження генетичної мінливості лісової дендрофлори. Підходи до збереження генетичної мінливості лісового генофонду. Збереження видів деревних рослин іn situ.
38794. ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ В РЫНОЧНЫХ УСЛОВИЯХ (НА ПРИМЕРЕ ООО «ДАБАН») 856.5 KB
  Анализ объема и ассортимента продукции. Анализ структуры продукции и влияние структурных сдвигов на изменение стоимости продукции. Понятие эффективности Целью деятельности любого промышленного предприятия является выпуск определенной продукции выполнение работ оказание услуг установленного объема и качества в определенные сроки. Но при установлении масштабов производства следует исходить не только из народнохозяйственных и индивидуальных потребностей в данной продукции но и в необходимости учитывать достижение максимального...