что значит компонент связности в графе

Компонента связности графа

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

Для ориентированных графов определено понятие сильной компоненты связности

Алгоритм

Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).

См. также

Ссылки

Полезное

Смотреть что такое «Компонента связности графа» в других словарях:

Компонента сильной связности графа — Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными… … Википедия

Компонента — Компонент (от лат. componens, родительный падеж componentis составляющий) составная часть, элемент чего либо. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике сложилось употребление в… … Википедия

ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… … Математическая энциклопедия

ГРАФА АВТОМОРФИЗМ — изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой… … Математическая энциклопедия

Компонента сильной связности в орграфе — Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.… … Википедия

Связность графа — Связный граф граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь. Содержание 1 Примеры применения 2 Связность для орграфов … Википедия

Компонент — Компонента составная часть чего либо целого. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике Компонента связности Компонента связности графа Компонента вектора или тензора, см.… … Википедия

КС — Компонента связности графа Конституционный суд Контактная сеть Counter Strike Кубок Стэнли Корреспондентский счёт (к/с) Качугин, Солодовников (по другим данным Керосиновая смесь) Координационный совет Кран Самоходный (см. также Подъёмный кран#По… … Википедия

Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Источник

Электронная библиотека

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

Дадим более удобное определение связных графов.

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

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

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

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

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

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

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

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

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

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

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Рис. 3.15. Граф для примера 80

В графе возможно выделить несколько разделяющих множеств и разрезов.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Источник

Лекция 13. Графы

4.2. Связность

Маршруты

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

только из одной вершины графа.

Связные компоненты

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

Отношение связности рефлексивно (вершина всегда связана сама с собой), симметрично (из связности вершины с вершиной следует связность вершины с вершиной ) и транзитивно (если вершины , и вершины , связаны, то связаны и вершины ,). Таким образом, отношение связности для вершин есть отношение эквивалентности. Поэтому существует такое разбиение множества вершин графа на попарно непересекающиеся подмножества (классы эквивалентности), что все вершины в каждом подмножестве связаны, а вершины из различных подмножеств не связаны. Каждое такое подмножество вершин графа вместе с ребрами, инцидентными этим вершинам, образует связный подграф. Следовательно, неориентированный граф представим единственным образом в виде объединения непересекающихся связных подграфов. Эти подграфы называют связными компонентами рассматриваемого графа. Связный граф является своей единственной компонентой связности. На рис.4.21 изображен граф, который имеет три компоненты связности.

Теперь обратимся к ориентированному графу. Если в орграфе существует маршрут, связывающий вершины и , то говорят, что вершина достижима из вершины . Любая вершина считается достижимой из себя самой. Вершина орграфа называется источником, если из нее достижима любая вершина орграфа.

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

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

Рис.4.22 Рис.4.22 Рис.4.22

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

Маршрут, содержащий все вершины орграфа, называется остовным.

Теорема 4.5. Орграф является сильным тогда и только тогда, когда в нем есть остовный контур, является односторонним тогда и только тогда, когда в нем есть остовный путь.

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

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

Орграф, изображенный на рис. 4.25, имеет четыре сильные компоненты с множествами вершин , , , . В орграфе могут быть дуги, не входящие ни в одну из его сильных компонент, например, дуги , , и у орграфа на рис. 4. 25.

Вершинная связность и реберная связность

Сопоставляя, например, полный граф шестого порядка и его любой связный суграф, интуитивно ясно, что сам полный граф «сильнее» связан, чем его суграф. Далее речь пойдет о понятиях, характеризующих степень связности графа.

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

Определение 4.10. Числом вершинной связности (или просто числом связности) графа называется число, равное наименьшему числу вершин, удаление которых приводит к несвязному или одновершинному графу.

Граф , представленный на рис. 4.26, связен, но он перестает быть связным, если удалить вершину 4. Поэтому .

Можно нарушить связность графа, удаляя некоторые его ребра (дуги). У графа (рис. 4.26) для этого придется удалить не менее трех ребер. Например, граф распадается на две компоненты после удаления ребер 4&5, 4&6, 4&7.

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

Выше мы показали, что для графа (рис. 4.26) .

Ребро графа называется мостом, если его удаление увеличивает число компонент связности графа.

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

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

На рис. 4.28 показаны блоки , , графа на рис. 4.26.

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

Теорема 4.6. Для любого графа справедливы неравенства:

.

Граф называется k-связным, если , реберно— k-связным, если .

Граф , изображенный на рис. 4.26, 1-связен и реберно-3-связен.

Источник

Компоненты сильной связности

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

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

Граф с тремя компонентами сильной связности

Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.

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

Конденсация графа

Если мы уже знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: нужно провести некоторые манипуляции со списками смежности, заменив для всех ребер номера вершин номерами их компонент, а затем объединив списки смежности для всех вершин каждой компоненты. Поэтому сразу сведем исходную задачу к нахождению самих компонент.

Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.

После того, как мы сделали это с первой вершиной, мы можем пойти по топологически отсортированному списку дальше и делать то же самое с вершинами, для которых компоненту связности мы ещё не отметили.

Сортируем вершины в порядке убывания времени выхода.

Проходимся по массиву вершин в этом порядке, и для ещё непомеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компонентой связности.

После этого номера компонент связности будут топологически отсортированы.

Источник

2.1. Компоненты сильной связности ориентированного графа

С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

Cоставляем матрицу смежности A(D) размерности (N− количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины Vi и входящая в Vj, то элемент матрицы смежности, стоящий на пересечении I-той строки и J-того столбца равен 1, иначе – 0.).

Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T(D) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S(D) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.

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

1. Присваиваем P=1 (P − количество компонент связности), .

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

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

Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин N=5.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

.

Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:

, ,

,

.

Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:

.

Присваиваем P=1 и составляем множество вершин первой компоненты сильной связности D1: это те вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины .

Вычеркиваем из матрицы S1(D) строку и столбец, соответствующие вершине V1, чтобы получить матрицу S2(D):

.

Присваиваем P=2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S2(D), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V2:

.

И присваиваем P=3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D:

Источник