В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 25
Текст из файла (страница 25)
Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такон сети естественно сопоставить граф; вершины — центры, ребра — каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надежность (живучесть) сети, под которой обычно згодразумевают способность сети функционировать при выходе пз строя одного или нескольких центров или (и) каналов.
Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается прп повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений. Числом вершинной связности (или просто числом связности) к(С) графа С называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. 133 Т '., например, х(К~)= О, х(К ) п — 1, х(С )= 2. Это вполне согласуется с интуитивным представлением о том, что при п ) 3 граф К„ сильнее связен, чем С„. Граф С, представленный на рис.
33.1, связен, но его связность можно нарушить, удалив вершину 4. Поэтому х(С) = 1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, 6 распадается а Ь Рас. 33.2 Рис. ЗЗЛ на две компоненты при удалении ребер (4, 5), (4, 6), (4, 7). Чтобы учесть это обстоятельство, введем еще одно определение. Пусть 6 — граф порядка п ) 1, Числом реберной связности ),(6) графа 6 назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберпой связности графа будем считать равным нулю, если этот граф одновершинный.
В качестве иллюстрации снова обратимся к графу С на рис. 33.1. Здесь ) (6)= 3 и, следовательно, Х(С)) ) х(С). Е(иже будет показано, что противополон«ное неравенство невозможно ни для какого графа. Определим некоторые элементы графа, играющие особую роль в дальнейших рассмотрениях. Вершина о графа 6 называется точкой сочленения (илп разделя«си~ей вершиной), если граф С вЂ” о имеет больше компонент, чем С. В частности, если С связеп н о — точка сочленения, то 6 — о не связеп. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент.
Таким образом, точки сочленения и мосты — это своого рода «узкие места» графа. Граф, изображенный на рнс. 33.2, имеет три точки сочленения а, Ь, с и одип мост аЬ. Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, кнцпдентные этой вершине. 134 Возвращаясь к рассмотренной в начале параграфа сети, нетрудно заметить, что число вершинной связности и число реберной связности ее графа отражают чувствительность сети к разрушению центров и каналов соответственно, а мостам и точкам сочленения отвечают наиболее уязвимые места сети.
Если 6(6) — минимальная степень вершин графа 6, то очевидно, что Л(6)«6(6), поскольку удаление всех ребер, инцидентных данной вершине, приводит к увеличению числа компонент графа. Выясним теперь соотношение между чпсламп х(6) и Л(6). Если граф 6 не связен илп имеет мост, то очевидно, что к(6) = Л(С). Пусть 6 — связный граф без мостов. Выберем в этом графе множество Еь состоящее из Л = Л(6) ребер, удаление которых приводит к несвязному граФу.,Пусть Ег ~ Еь ~Ег! = Л вЂ” 1. ГраФ С вЂ” Ег связен и имеет мост, который обозначим через ио. Для кансдого ребра из множества Ег выберем какую-либо инцидентную ему вершину, отличную от и и о.
Удалим теперь выбранные вершины из графа. Этим самым будут удалены, в числе прочих, и все ребра, входящие в Ег. Если оставшийся граф не связен, то и = н(6) «Л. Если же он связен, то ребро ио является мостом. Поэтому удаление одной из вершин и или о приводит к несвязному или одновершннному графу, а это означает, что н «Л, Таким образом, доказана Т е о р е м а 33.1. Для любого графа 6 верньь неравенства н(6) «Л(6) «6(С). Следующее утверждение показывает, что этп неравенства нельзя усилить.
Утверждение 33.2. Для любых натуральных чисел р, д, т, таких, что р «д «т, существует граф 6, у которого н(С) = р, Л(6) = д, 6(С) = г. > Рассмотрим граф 6 порядка 2(т+1), у которого УС = У~ 0 Кг, где Ус= (ос', о,', ..., о„'с,) (с = 1, 2). В множество ребер этого графа включим, во первых, все ребра вида оьо', (с = 1, 2; )с,1 = 1, т + 1, й ~ 1).
Таким образом, каждое пз мноясеств т'с (1 1, 2) является кликой и С. Во-вторых, в мноясество Е6 включим все ребра вида оьоь'(й = 1, р) и вида грор+д (сс = 1, д — р)(строение графа С схематично показано на рис. ЗЗ.З). Учитывая равенство Л(Х„)= и — 1, легко убедпться в том, что построен- 135 ный граф обладает нужными свойствами, т. е. что х(6) = р, Х(6)= о, б(С)= т. 0 Тем не менее верна следующая теорема, приводимая здесь без доказательства (см. обзор [211). Теорема 33.3. Для почти каждого графа С верно равенство х (С) = Х(6). Граф 6 называется И-связным, если х(6)~й, и реберно-'к-связным, если Х(С)~ й. Таким образом, отличный от К1 граф 1-связен (односвязен) тогда и только — тогда, когда он связен, а 2-связные (двусвязные) графы — это связные графы без точек сочленения, не являющиеся одновершиннымн.
Граф 6, изображенный на рис. ЗЗ 1, 1-связен и реберно-3-связен. Легко видеть, что этот граф содержит подграфы, являющиеся «более связными», чем сам граф. Таков, например, д гг подграф, порожденный мнохсеством вершин (1, Рис. 33.3 2, 3, 4, 8). Он З-связен. Чтобы учесть эту и подобные ей ситуации, естественно ввести следующее определение: максимальный к-связный подграф графа называется его к-связной компонентой, или просто к-коз«- понентой.
Это определение иллюстрируется на рис. 33.4. На этом рисунке граф 61 имеет две 2-компоненты, а Сев Рвс. 33.4 две 3-компоненты. Сами графы 61 и Сг являются 1-коипонентами графа 6106«. Легко заметить, что 2-компоненты графа С~ имеют одну общую вершину, а 3-компо- 136 ненты графа 6з — две общие вершины. Следующая теорема показывает, что это обстоятельство не случайно. Теорема 33.4. Две р зличные й-компоненты графа имеют не более чем й -1 общих вершин. с Пусть 61 и Сз — различные Й-компоненты графа 6 и УС, Э УСз = Х.
Предположим, что ~Х~ ~ й, и докажем, что тогда граф 61 0 Сз должен быть й-связным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых й — 1 вершин, т. е. если У ~ У(6~ 0 Сз), ! У! = й — 1, то граф (61 0 Сз) — У связен. Положим У; = (УС,~Х) П У, з = 1, 2, Уз = Х П У, Ясно, что 1 У;! ~ ~Й вЂ” 1, з = 1, 2, 3, У = У~ 0 Уз 0 Уз. Поскольку 1У~ 0 Уз~ ( й — 1, з = 1, 2, и графы С1 и Сз Й-связны, то графы Нз= С~ — (У~В Уз), з 1, 2, связны. Так как по предположению ~Х| ) й, то Х~Уз Ф = Ы, т. е. связные графы Н~ и Нз имеют хотя бы одну общую вершину.
Следовательно, связен граф Н1 0 Нз = =(61 0 Сз) — У. Последнее означает, что граф 6, 0 Сз й-связен. Поэтому, вопреки предполоясению, ни Сь ни 6з не являются й-компонентами графа 6. гз 5 34. Двусвязные графы Случаям, когда й 2 или й = 3, в теории графов отведена особая роль. Это объясняется следующими причинами. Во-первых, 2- и 3-связные графы фигурируют во многих теоретических и прикладных вопросах, в частности, ряд задач достаточно уметь решать для 2-связных компонент.
Во-вторых, при й = 3 и, особенно, при й = 2 удается дать в некоторой степени обозримое описание соответствующих графов. Рассмотрим вначале некоторые простые свойства 2-связных графов, вытекающие непосредственно из определений: 1) степени вершин 2-связного графа больше единицы; 2) если графы 61 и Сз 2-связны и имеют не менее двух общих вершин, то граф 610 Сз также 2-связен; 137 3) если граф С 2-связен и Р— простая цепь, соединяющая две его вершины, то граф С 0 Р также 2-связен; 4) если вершина о не является точкой сочленения связного графа, то любые две его вершины соединены цепью, не содержащей о; в частности, в 2-связном графе для любых трех несовпадающих вершин а, Ь, о имеется (а, Ь)-цепь, не проходящая через о.
Этими сэойстзамп мы будем пользоваться без каких- либо пояснений и дополнительных ссылок на пих. Теорема 34Л. Пусть С вЂ” связный граф и ~С, ') 2, Тогда следующие утверждения эквивалентны: 1) граф 2-связен; 2) любые две вершины графа принадлежат простому циклу; 3) любая вершина и любое ребро принадлежат простому циклу; 4) любые два ребра принадлежат простому циклу; 5) для любых двух вершин а и Ь и любого ребра е существует простая (а, Ь)-цепь, содержащая е; 6) для любых трех вершин а, Ь, с существует простая (а, Ь)-цепь, проходящая через с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
