Что такое несвязный граф

Лекция 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-связен.

Источник

Связность графов

Содержание

Связность

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

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

Примеры

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

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

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

Пусть G(V,E) — несвязный граф. Зафиксируем некоторую вершину v графа и обозначим через V1 множество, состоящее из вершины v и всех тех вершин из V, которые соединены цепями с вершиной v. Множество V1 не пусто (оно содержит, но крайней мере, вершину v) и не совпадает с множеством V (при V1=V граф G(V,E)- связный, т.к. между его любыми двумя различными вершинами существует цепь, проходящая через v). Рассмотрим дополнение V2=V \ V1.

Множество V2— не пусто, и никакое ребро графа G(V,E) не соединяет ни одну вершину из V1 ни с одной вершиной из V2. Поэтому построенные множества V1 и V2 образуют искомое разбиение множества V.

Обратно, пусть существует разбиение V1 ∪ V2, множества V, удовлетворяющее условию теоремы.

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

Следствие из теоремы

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

Свойства графов

1°.Каждая вершина графа входит в одну и только в одну компоненту связности.

2°.Любой конечный граф имеет конечное число компонент связности.

3°.Граф, состоящий из единственной компоненты связности, является связным.

4°.Каждая компонента связности графа является его подграфом.

5°.Для любого графа либо он сам, либо его дополнение является связным.

Доказательства свойств

Докажем свойства 4° и 5°.

Полезное

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

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

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

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

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

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

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

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

теория графов — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] теория графов Математическая теория, содержание которой формулируется двояко, в зависимости от трактовки ее… … Справочник технического переводчика

Теория графов — [graph theo­ry] математическая теория, содержание которой формулируется двояко, в зависимости от трактовки ее исходного понятия граф: теоретико множественной или геометрической. В первом случае предметом теории являются графы как некие объекты,… … Экономико-математический словарь

Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия

Источник

Связный граф, Не связный граф, сильносвязный граф определения и теоремы

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

1. она начинается и заканчивается вершиной;

2. вершины и ребра в ней чередуются;

3. любое ребро последовательности имеет своими концами две вершины: непосредственно предшествующую ему в этой последовательности и следующую сразу за ним.

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

Определение 11.2. Путем называется такой маршрут, в котором никакое ребро не встречается дважды. Иногда его также называют цепью.

Определение 11.3. Граф называется связным если между любыми двумя его вершинами существует маршрут. В противном случае граф называется несвязным.

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

Теорема 1. Граф на n вершинах, степень каждой из которых не менее (n − 1)/2, связен.

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

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

Доказательство. Пусть мы удалили ребро, которое соединяло вершины A и B. Если после этого вершины A и B оказались в разных компонентах связности, то рассмотрим компоненту связности , содержащую вершину A. Поскольку количество ребер, выходящих из вершины A, уменьшилось на единицу, то степень вершины A также уменьшилась на единицу и стала нечетной, а степени всех остальных вершин в остались четными. Но это противоречит тому, что в любом графе количество нечетных вершин четно. (Это утверждение верно и для любой компоненты связности графа, поскольку сама по себе она тоже является графом.) А значит вершины A и B не могли оказаться в разных компонентах связности. Однако если вершины A и B оказались в одной компоненте связности, то существует маршрут M их соединяющий. Пусть X и Y — две произвольные вершины графа. Тогда между ними до удаления ребра существовал маршрут. Если в этом маршруте не содержалось ребра AB, то и в получившемся графе эти вершины связаны тем же маршрутом. Если же в в нем содержалось ребро AB один или несколько раз, то в любом месте, где оно появлялось, его вместе с вершинами A и B можно заменить на маршрут M, проходимый в прямом или обратном порядке в зависимости от того, проходилось ли ребро AB от вершины A к вершине B или наоборот. Но это означает, что граф остался связным.

Теорема 3. Если из полного графа на n вершинах удалить не более n − 2 ребер, то граф останется связным.

Поскольку 1 ≤ k ≤ n − 1, то каждая из скобок (k − 1) и (n − k − 1) неотрицательна, а значит разность k(n−k)−(n−2) больше 0. Тем самым мы доказали, что количество ребер, которое необходимо удалить из полного графа, чтобы сделать его несвязным, больше n−2, откуда и следует утверждение теоремы.

Примеры применения

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

Связность для ориентированных графов

В ориентированных графах различают несколько понятий связности.

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

Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных ребер неориентированными.

Некоторые критерии связности

Здесь приведены некоторые критериальные (эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:

Сильно связные графы и компоненты графа

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

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

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

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

Граф приведенный на рис. 1.7(а), как легко проверить, сильно связанный. Граф, показанный па рис. 1.7(б), не является сильным (так как в нем нет пути из х1, в х3), но односторонне связный. Граф, изображенный на рис. 1.7(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от х2 к х5 и от х5 к х2. Он — слабо связный. Наконец, граф, приведенный на рис. 1.7(г), является несвязным.

Пусть дано некоторой свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства Р называется порожденный подграф графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа , у которого , и который также обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связность, то максимальным сильным подграфом графа С является сильный подграф, который не содержится в любом другом сильном подграфе. Такой подграф называется сильной компонентой графа С. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента — максимальный слабый подграф.

Например, в графе G, приведенном на рис. 1.7(6), подграф является сильной компонентой графаG. С другой стороны, подграфы ине являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графеи, следовательно, не максимальные. В графе, показанном на рис. 1.7(в). подграфявляется односторонней компонентой. В графе, приведенном на рис. 1.7(г), оба подграфа и являются слабыми компонентами, и у этого графа только две такие компоненты.

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

Задачи

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

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

3 В государстве 50 городов, причем от каждого города можно доехать до любого другого, возможно с пересадками. Какое наименьшее число дорог может быть в этом государстве?

4 На плоскости нарисованы вершины графа, пронумерованные числами от 2 до 30. При этом две вершины с номерами a и b соединены ребром только в том случае, если одно из чисел a или b делится на другое. Сколько компонент связности имеет этот граф?

5. Летом Иван отдыхал в молодежном лагере «Восход», где вместе с ним находилось всего 53 школьника. После окончания отдыха некоторые пары обменялись адресами, причем у каждого из отдыхающих оказалось не менее 26 адресов. Через некоторое время Ивану понадобился адрес Николая, с которым он адресом не обменивался. Докажите, что Иван может узнать адрес Николая, т.е. существует цепочка из школьников, которая начинается с Ивана и оканчивается Николаем и в которой каждая пара соседей обменялась адресами.

6. Степень каждой вершины связного графа – не менее 100. Одно ребро выкинули. Может ли получиться несвязный граф?

7. В локальной компьютерной сети от сервера отходит 21 провод, от остальных компьютеров – по 4 провода, а от принтера – один провод. Докажите, что с сервера можно послать документ на принтер.

8. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.

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

10. В стране любые два города соединены или железной дорогой, или авиалинией. Доказать, что один из видов транспорта позволяет добраться из любого города в любой.

11. На листе бумаги отмечено 2011 точек. Двое играют в следующую игру: каждый своим ходом соединяет две отмеченные точки линией. Запрещается соединять пару точек повторно. Проигрывает тот, после хода которого из любой точки можно пройти в любую другую, двигаясь от вершины к вершине по проведенным линиям. Кто выигрывает при правильной игре?

12. В стране, кроме столицы, больше 100 городов. Столица страны соединена авиалиниями со 100 городами. Каждый из остальных городов соединен авиалиниями ровно с 10 городами. Известно, что из любого города можно перелететь в любой другой (может быть, с пересадками). В связи с экономическим кризисом было принято решение закрыть половину дорог из столицы. Докажите, что это можно сделать таким образом, чтобы после этого снова можно было бы из любого города перелететь в любой другой.

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

14. Между некоторыми из 2n городов установлено воздушное сообщение, причем каждый город связан (беспосадочными рейсами) не менее чем с n другими. Докажите, что если отменить любые n − 1 рейсов, то все равно из любого города можно добраться в любой другой на самолетах (с пересадками).

15. В некотором государстве города соединены дорогами. Длина любой дороги меньше 500 км, и из любого города в любой другой можно попасть, проехав по дорогам меньше 500 км. Когда одна дорога оказалась закрытой на ремонт, выяснилось, что из каждого города можно проехать по оставшимся дорогам в любой другой. Доказать, что при этом можно проехать меньше 1500 км.

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

17. На турбазе 12 домиков, между которыми крот прокопал 56 непересекающихся подземных ходов (два домика соединяются не более чем одним ходом). Докажите, что крот из любого домика может попасть в любой другой, передвигаясь по этим ходам.

18. Докажите, что граф на n вершинах, имеющий более (n − 1)(n − 2)/2 ребер, связный.

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

а) Какое наименьшее число открыток могло быть послано?

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

а) Приведите примеры графа, для которого χ = 2, λ = 3.

б) Докажите, что для любого связного графа выполняется соотношение χ ≤ λ ≤ δ, где δ — минимальная из степеней вершин графа.

См. также

Источник