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

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

Компонента сильной связности графа — Орграф называется сильно связным (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 Кубок Стэнли Корреспондентский счёт (к/с) Качугин, Солодовников (по другим данным Керосиновая смесь) Координационный совет Кран Самоходный (см. также Подъёмный кран#По… … Википедия

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

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

4.2. Связность

Маршруты

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

Пусть маршрут задан ребрами и ребру соответствует пара вершин , где . Говорят, что маршрут замкнут, если , и не замкнут, если . Для не замкнутого маршрута вершина называется начальной вершиной, а вершина конечной. В этом случае говорят, что маршрут соединяет вершины и . Еще говорят, что вершина связана с вершиной .

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

Маршрут назовем нетривиальным, если он содержит хотя бы одно ребро; для систематичности рассуждений вводится еще нульмаршрут, вообще не содержащий ребер, — этот маршрут состоит

Читайте также:  Как хитро расставить корабли в морском бое

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

На рис.4.18 приведен пример составной цепи, на рис.4.19 приведен пример пути, а на рис.4.20 — пример простой цепи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Дэу нексия или шевроле лачетти

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

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

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

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

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

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

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

Таким образом, точки сочленения и мосты — это своего рода «узкие места» графа. Граф на рис. 4.27 имеет три точки сочленения — это вершины , , , и один мост — ребро .

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

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

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

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

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

.

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

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

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

Неорграф называется связным, если любая пара вершин в нем связана. Орграф называется связным, если соответствующий ему неорграф связен. Орграф называется сильно-связным, если для любой пары несовпадающих вершин vi и vj существуют оба маршрута (vivj) и (vjvi).


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

На рисунке 26 изображены два графа: неорграф (слева) связным не является и состоит из четырех компонент – <1,2,3>, <4,5>, <6,7,8>и <9>. Орграф (справа) связен, но не сильно-связен, имеет три сильные компоненты – <1,2,3>, <4>и <5>.

Читайте также:  Как в симс фриплей устроить фальшивое рукопожатие

Свойства связных графов

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

2) Изолированная вершина является компонентой.

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

4) Удаление циклического ребра не нарушает связности графа.

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

Теорема 3.9.1. (Оценка числа ребер в простых графах)

Пусть G=(V, E) – простой граф с в вершинами и k компонентами. Тогда число его ребер р удовлетворяет неравенству:

Доказательство: 1) рассмотрим левую часть неравенства. Если граф связен, то число его компонент k равно 1. Удалим из графа все циклические ребра, в результате этого будет получено дерево. Дальнейшее удаление ребер из дерева будет нарушать связность. Поэтому среди всех связных простых графов дерево имеет наименьшее число ребер. Но число ребер в дереве равно максимальной длине пути, построенного на в вершинах, и по свойствам путей равно (в‑1). Тем самым, в связном графе число ребер р ³ в‑1, что совпадает с оценкой снизу при k=1. Пусть теперь G несвязный граф. Тогда он разбивается на k связных компонент, для каждой из которых число ребер рi ³ вi‑1, где i=1,2,¼,k и рi, вi – это число ребер и вершин в i‑ой компоненте. Но и , а . Поэтому р ³ в‑k, и левая часть неравенства доказана.

2) Теперь рассмотрим правую часть неравенства (оценку сверху). Если граф связен, то добавим к нему новые ребра, соединяя все пары несмежных вершин. В результате этого будет получен полный граф. Дальнейшее добавление ребер к полному графу будет нарушать его простоту. Поэтому среди всех связных простых графов полный граф имеет наибольшее число ребер. Для подсчета этого числа воспользуемся теоремой о степенях вершин в графе. Поскольку каждая вершина полного графа смежна со всеми остальными его вершинами, то степень каждой вершины равна (в‑1), а сумма степеней всех вершин равна в×(в‑1). По теореме о степенях вершин это число равно удвоенному числу ребер, поэтому число ребер в полном графе равно . И число ребер в связном графе р £, что совпадает с оценкой сверху при k=1. Пусть теперь G – несвязный граф. Тогда число ребер в каждой i‑ой компоненте рi £. Однако, простое суммирование этого неравенства по числу компонент, как это было сделано в первом пункте доказательства, ничего не даст, поэтому выполним над графом следующую процедуру. Выберем произвольно две компоненты: i‑ую и j‑ую. Можно считать, что число вершин выбранных компонент вi ³ вj > 1. Заменим i‑ую компоненту на полный граф с числом вершин (вi +1), а j‑ую компоненту – на полный граф с числом вершин (вj ‑1). Общее число вершин в выбранных компонентах при этом не изменится, а число ребер изменится на величину, равную

Таким образом, выполненная процедура только увеличивает число ребер. Будем выполнять её над выбранными компонентами до тех пор, пока от j‑ой компоненты не останется одна изолированная вершина. Затем выберем другую пару компонент с числом вершин больше единицы в каждой. И выполним над этой парой такую же процедуру. И т.д. до тех пор, пока не будет получен граф, в котором с (k‑1) компонента являются изолированными вершинами и одна компонента – полный граф на (вk+1) вершинах. Число ребер в полученном графе равно , и оценка сверху доказана.

Следствие. Любой простой граф с в вершинами и числом ребер, большим, чем связен.

Не нашли то, что искали? Воспользуйтесь поиском:

Ссылка на основную публикацию
Клавиатура на айфоне фото
Восемь лет назад Стив Джобс анонсировал первый смартфон компании Apple. Одной из главных особенностей iPhone являлась возможность навигации по меню...
Какие комбинации клавиш необходимы для получения символов
Здравствуйте! Вы никогда не задумывались, сколько порой приходится тратить времени на обычные операции: выделить что-то мышкой, скопировать, затем вставить в...
Какие компрессоры стоят в холодильниках бирюса
С появлением широкого ассортимента импортного холодильного оборудования бытовая техника отечественного производства постепенно отошла на второй план. Однако ошибочно думать, что...
Клавиатура не отрывая пальца
Непрерывный ввод — это функция, которая позволяет вводить текст, проведя пальцем по клавиатуре. Это работает следующим образом. Допустим, вам нужно...
Adblock detector