Число вершинной связности графа

Число вершинной связности графа

Связность

Связный граф был определен как граф, у которого любые две вершины соединены цепью. Так, оба графа Кn и Сn связны, однако интуитивно ясно, что при n > 3 граф Кn «сильнее» связен, чем Сn. В этой главе вводятся и исследуются понятия, характеризующие степень связности графа.

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

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

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

Так, например, x(К1)=0, х(Кn)= n —1, х(Сn)=2. Это вполне согласуется с интуитивным представлением о том, что при n > 3 граф Кn сильнее связен, чем Сn.

Граф G, представленный на рис. 33.1, связен, но его связность можно нарушить, удалив вершину 4. Поэтому x(G) = 1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, G распадается

на две компоненты при удалении ребер <4, 5>, <4, 6>, <4, 7>. Чтобы учесть это обстоятельство, введем еще одно определение.

Пусть G — граф порядка n > 1. Числом реберной связностиλ(G) графа G назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберной связности графа будем считать равным нулю, если этот граф одновершинный.

В качестве иллюстрации снова обратимся к графу G на рис. 33.1. Здесь λ(G)=3 и, следовательно, λ(G)> x(G). Ниже будет показано, что противоположное неравенство невозможно ни для какого графа.

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

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

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

Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине.

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

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

Выясним теперь соотношение между числами х(G) и λ (G). Если граф G не связен или имеет мост, то очевидно, что x(G) = λ (G). Пусть G — связный граф без мостов. Выберем в этом графе множество Е1, состоящее из λ = λ (G) ребер, удаление которых приводит к несвязному графу. Пусть Е2 лежит Е1 Е2 = λ — 1. Граф G — E2 связен и имеет мост, который обозначим через иv. Для каждого ребра из множества Е2 выберем какую-либо инцидентную ему вершину, отличную от и и v. Удалим теперь выбранные вершины из графа. Этим самым будут удалены, в числе прочих, и все ребра, входящие в Ё2. Если оставшийся граф не связен, то х = х(G) i , v2 i , . v i r+1 >(i = 1, 2). В множество ребер этого графа включим, во-первых, все ребра вида v i kv i l (i = 1, 2; k,l= 1, r + 1, k не= I). Таким образом, каждое из множеств Vt (i =1, 2) является кликой в G. Во-вторых, в множество EG включим все ребра вида v 1 kv 2 k (k = 1, р) и вида v 1 pv 2 p (k = 1, q — p)(строение графа G схематично показано на рис. 33.3). Учитывая равенство λ (Kn)= n — 1, легко убедиться в том, что построенный

граф обладает нужными свойствами, т. е. что x(G) = р, K(G)=q, 6(G)=r. =k. Таким образом, отличный от К1 граф 1-связен (односвязен) тогда и только


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

Граф G, изображенный на рис. 33.1, 1-связен и ре-берно-3-связен. Легко видеть, что этот граф содержит подграфы, являющиеся «более связными», чем сам граф. Таков, например, подграф, порожденный множеством вершин <1, 2, 3, 4, 8). Он 3-связен.

Чтобы учесть эту и подобные ей ситуации, естественно ввести следующее распределение: максимальный k-связный подграф графа называется его k-связной компонентой, или просто k-компонентой.

Это определение иллюстрируется на рис. 33.4. На рисунке граф G1 имеет две 2-компоненты, а G2

две 3-компоненты. Сами графы G1 и g2 являются 1-компонентами графа G1 U G2. Легко заметить, что 2-компоненты графа G1 имеют одну общую вершину, а 3-компоненты графа gz — две общие вершины. Следующая теорема показывает, что это обстоятельство не случайно.

Теорема 33.4. Две различные k-компоненты графа имеют не более чем k— 1 общих вершин.

Пусть G1 и G2 — различные K-компоненты графа G и VG1ÇVG2 = X. Предположим, что |Х|³k, и докажем, что тогда граф G1 U G2 должен быть k-связным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых k — 1 вершин, т. е. если Y U V(G1UG2), |Y| =k-1, то граф (G1 U G2)-Y связен. Положим

Читайте также:

  1. Атактическое мышление и его виды, бессвязность, их основные отличия.
Читайте также:  Где на компьютере хранятся резервные копии iphone

связны. Так как по предположению |Х| ³k, то ХY3не равно =Æ, т. е. связные графы H1 и H2 имеют хотя бы одну общую вершину. Следовательно, связен граф H1U H2 = =(G1 U G2)— Y. Последнее означает, что граф G U G2 k-связен. Поэтому, вопреки предположению, ни G1, ни G2 не являются k-компонентами графа G.

Дата добавления: 2015-01-30 ; просмотров: 33 | Нарушение авторских прав

Меры связности графа. Вершинная и реберная связность

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

=0, если граф G несвязен; =1, если граф G имеет точку сочленения;

, если (G – полный граф с p вершинами).

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

На рис. 3 приведен пример 2-связного графа.

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

Дата добавления: 2014-01-05 ; Просмотров: 970 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

6.3.1. Компоненты связности

Теорема 6.1. Пусть в графе G n вершин и m ребер. Пусть St(v i )

– степень вершины v i . Тогда суммарная степень всех вершин равна удвоенному числу ребер графа.

По этой причине суммарная степень всех вершин графа всегда является четным числом.

Иными словами, количество вершин с нечетной степенью в графе всегда четное. Это один из критериев, который помогает иногда доказать невозможность построения некоторых графов. Например нельзя построить регулярный граф степени 5 на 7 вершинах, так как его суммарная степень вершин получается равна 35, и в нем должно быть 17,5 ребер, что невозможно.

Маршрутом ( путем ) в данном графе G называется конечная последовательность ребер вида: < v 0 , v 1 >, < v 1 , v 2 >,…,< v m- 1 , v m >, обозначаемая также через v 0 → v 1 → v 2 → …→ v m .

Каждому маршруту соответствует последовательность вершин v 0 ,v 1 ,v 2 , …,v m . В этом случае v 0 называется начальной вершиной, а v m

– конечной вершиной маршрута, а сам маршрут называется маршрутом из v 0 в v m . Длиной маршрута называется число ребер в нем.

Читайте также:  Как перевести оперативную память на видеокарту

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

все вершины v 0 ,v 1 ,v 2 , …,v m различны.

Иными словами, цепь – это маршрут (путь) без повторяющихся ребер, простая цепь – это маршрут (путь) без повторяющихся вершин.

Маршрут (путь) называется простой замкнутой цепью или простым циклом , если все вершины v 0 ,v 1 ,…, v m различны, кроме

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

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

Приведем без доказательства два простых, но полезных утверждений.

Утверждение 1. Если граф G = ( V,U ) связный и a V , b V , а≠b и ( a , b ) U , то при добавлении к графу G ребра ( a,b ) в полученном графе будет простой цикл.

Утверждение 2. Если граф G = ( V,U ) связный и ребро ( a,b ) содержится в некотором цикле в графе G , то при выбрасывании из графа G ребра ( a,b ) снова получится связный граф.

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

Теорема 6.2. Пусть в графе G = (V,E) n вершин и m ребер. Тогда в G не менее (n-m) связных компонент. Если при этом в G нет циклов, то G состоит ровно из (n-m) связных компонент.

Следствие. Если m ≤ n –2, то любой граф с n вершинами и m ребрами не связен.

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

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

Для несвязного графа вершинная связность равна нулю. Для полного графа на n вершинах вершинная связность полагается равной ( n – 1) (так как сколько вершин ни удалять из графа, он всe равно не перестанет быть связным).

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

Вершина v графа G называется точкой сочленения (разделяю-

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

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

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

– это вершины a, b, c и один мост – ребро ( a,b ).

Для любого графа справедливо соотношение Уитни между реберной связностью λ, вершинной связностью κ и наименьшей из степеней вершин δ: κ≤λ ≤δ .

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

Задача 6.1. Построить или обосновать невозможность построения графа на 11 вершинах, у которого наименьшая степень вершин равна 7, а вершинная связность равна 8.

Решение. Наименьшей из степеней вершин является степень 7. По условию вершинная связность равна 8. Это противоречит соотношению Уитни: κ≤λ ≤δ , так как получим, что 8≤ λ ≤7. Значит, такого графа не существует.

6.3.3. Сильная связность в графах

Термин «сильная связность» относится только к ориентированным графам. Введем необходимые предварительные понятия.

Полустепенью исхода St (v) — вершины v в ориентированном графе называется число дуг, выходящих из данной вершины.

Полустепенью захода St + (v) вершины v в ориентированном графе называется число дуг, входящих в данную вершину.

Изолированной вершиной называется вершина, у которой и полустепень захода, и полустепень исхода равны 0.

Истоком называется вершина, полустепень исхода которой положительна, а полустепень захода равна 0.

Стоком называется вершина, полустепень захода которой положительна, а полустепень исхода равна 0.

Читайте также:  Сколько может проскакать лошадь без остановки

Путем в ориентированном графе G от v 1 до v m называется последовательность ориентированных дуг (ребер) < v 1 , v 2 >, < v 2 , v 3 >,…,< v m- 1 , v m >, такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей, и ни одна дуга (ребро) не встречается более одного раза. Если в ориентированном графе G нашелся путь от v a до v b , то обратного пути от v b к v a может и не быть.

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

Замкнутый путь в ориентированном графе называется ориенти-

Длиной пути называется число дуг (ребер) в этом пути. Расстоянием от v a до v b в ориентированном графе называется длина наикратчайшего пути от v a до v b . Если пути от v a до v b не существует, то расстояние от v a до v b называется бесконечным. Оно обозначается ∞. Расстояние от v a до v b будем обозначать S ( v a , v b ).

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

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

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

Эту задачу можно решать двумя различными способами. Первый способ построен на классическом алгоритме нахожде-

ния пересечения положительной и отрицательной окрестности каждой из вершин. Он характеризуется значительной надежностью,

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

Шаг 1. Поиск стоков и истоков. Каждый найденный сток или исток в любом случае является отдельной компонентой, так как по своему определению не может входить в состав других компонент.

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

Шаг 3. Склейка циклов. Если на предыдущем шаге будут найдены циклы, имеющие хотя бы одну общую вершину, то такие циклы необходимо объединить в единую компоненту. Это связано с тем, что общие вершины являются узловыми в том смысле, что при операции объединения они связывают за счет склейки исходные циклы, и с их помощью возможно добраться из любой вершины первого цикла в любую вершину второго.

Шаг 4. Проверка. Необходимо проверить, что в результате шагов 1-3 полученные компоненты сильной связности включают в себя все вершины исходного графа, причем ровно по одному разу. Иными словами. Ни одна из вершин не должна быть включена более чем в одну компоненту, и в результате процедуры все вершины должны быть распределены по компонентам. Если суммарное число вершин по всем компонентам меньше, чем общее количество вершин в исходном графе, то необходимо выявить те вершины, которые не вошли в список найденных компонент сильной связности и с особой внимательностью их рассмотреть. Причин обычно две. Первая: не слишком внимательно был произведен поиск циклов, и на самом деле «забытые» вершины входят в один из пропущенных циклов. Вторая: эти «забытые» вершины действительно представ-

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

Ссылка на основную публикацию
Фотографии купе в поезде
Интересный фотоотчет о поездке на одном из первых рейсов двухэтажных поездов. Смотрим далее, как все устроено внутри таких двухэтажных вагонов...
Уравнение окружности в полярных координатах
Определение: замкнутая плоская кривая, все точки которой одинаково удалены от данной точки (центра О), лежащей в той же плоскости, что...
Уравнение пучка прямых проходящих через точку
Совокупность прямых, проходящих через некоторую точку, называется пучком прямых с центром в этой точке. Если и - уравнения двух пересекающихся...
Фотография с самым большим разрешением в мире
Представляем вашему вниманию нашу подборку самых больших фотографий в мире. Для их просмотра вам будет необходим FlashPlayer. Его можно скачать...
Adblock detector