Дискретная математика (998286), страница 38
Текст из файла (страница 38)
д < (р — й)(р — й+1)/2. Метод выделения «критических» графов. Число ребер й графа с р вершинами и й компонентами связности не превосходит числа ребер в графе с р вершинами и й компонентами связности, в котором все компоненты связности суть полные графы. Следовательно, достаточно рассматривать гтг Глава В.
Связность только графы, в которых все компоненты связности полные. Среди всех графов с р вершинами и й полными компонентами связности наибольшее число ребер имеет граф ь-т К,,и ЦК,. т=1 Действительно, пусть есть две компоненты связности Ст и Св, такие что 1 < рт = р(Ст) < рг = р(Сз). Если перенести одну вершину из компоненты связности Сг в компоненту связности Са, то число ребер изменится на А1 = рз — (рг — 1) = ра — рт + 1 > О. Следовательно, число ребер возросло.
Таким образом, достаточно рассмотреть случай ь-1 К,,+,и ЦК,. тзм Но при этом ь-1 т7(Кр — ь«г11( (Кт) =(р — й+1)(р — й+1 — 1)/2+0=(р — й)(р — й+1)/2. П т=1 СЛЕДСТВИЕ Если г7 > (р — 1)(р — 2)/2, то граф связен, Доквзатяльство Рассмотрим неравенство (р-1)(р — 2)/2 < д < (р — й)(р- й+1)/2 при различных значениях й. й = 1 (р — 1)(р — 2)/2 < (р — 1)р/2 выполняется, й = 2 (р — 1)(р — 2)/2 < (р — 2)(р — 1)/2 не выполняется, й = 3 (р — 1)(р — 2)/2 < (р — 3)(р — 2)/2 не выполняется и т. д. П 8.2.
Вершинная и реберная связность При взгляде на диаграммы связных графов (сравните, например, рис. 7.9 и 8.1) возникает естественное впечатление, что связный граф может быть «более» или «менее» свяэен. В этом разделе рассматриваются некоторые количественные меры связности. 8.2.1. Мосты и блоки Мостом называется ребро, удаление которого увеличивает число компонент связ- ности. Блоком называется связный граф, не имекнций точек сочленения. Пример В графе, диаграмма которого представлена на рис.
8.1: 8.2., Вершинная н ребарная связность 1. вершнньг и, е -„точки сочленения, и других точек сочленения нет; 2. ребро 'х' — мост, и других мостов нег; 3. правильные подграфы (а,б,и), 1а,и,ш), 1а,б,и,ш)„(с,г(,е), (е,г',е) — блоки, и других блоков нет. Рис. 8.1. Точки сочланення, мосты н блоки Если в графе, отличном от Кз, есть мост, то есть и точка сочленения. Концы всякого моста (кроме висячих вершин) являются точками сочленения, но ие всякая точка сочленения является концом моста.
ТЕОРЕМА Пусть С(У, Е) — связный граф и е В У. Тогда следующие утверждения эквивалентны: 1. е — точка сочленения; 2. 3и,ш 6 У и Ф шЙЧ (и,ш)а е Е (и,ш); 3; 3 П, Иг П Г1 И' = И Й П О И" = У ~ (е) ег Ч и Е П Чш Е И' ч (и, ш)а е В (и, ш)а. Докязятяльство 1=ь3: Рассмотрим С вЂ” е. Этот граф не связен, к(С вЂ” е) > 1, следовательно, С-е имеет (по крайней мере) две компоненты связности, то есть У~(е) = ПОИ', где П вЂ” множество вершин одной из компонент связности, а И' — все остальные вершины Пусть и В П, ш ц И'.
Тогда -3(и,ш) „. Но к(С) = 1, следовательно, 3 (и, ш) а, и значит, Ч (и, ш) а е В (и, ш) а. З=ь2: Тривиально, 2=ь1: Рассмотрим С вЂ” е. Имеем: 3(и,ш)а,. Следовательно, гс(С вЂ” е) > 1, откуда е — точка сочленения. П ТЕОРЕМА Пусть С(У, Е) — связный граф и х Е Е.
Тогда следующие утверждения эквивалентны: 1. х — мост; 2. х не принадлежит ни одному простому циклу; 214 Глава В. Связность 3. 3и, и Е Ъ" Ч (и, и)о х Е (и, и)ос 4. 3 У, Иг У Гт И' = И Й У О Ит = ь' Й Ч и Е У т и Е И~ Ч (и, и) с х Е (н, и) о. Доказатввьство Упражнение 8.2. 8.2.2. Меры связности Вершинной сюпностью графа С (обозначается х(С)) называется наименьшее чи- сло вершин, удаление которых приводит к несвязному или тривиальному графу.
Пример х(С) = О, если С несвязен; х(С) = 1, если С имеет точку сочленения; х(Кр) = р — 1, если ʄ— полный граф. Граф С называется я-связным, если х(С) = я. Реберной связностью графа С (обозначается Л(С)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу. Пример Л(С) = О, л(с) =1, л(К,) =р-1, если С несвязен; если С имеет мост; если ʄ— полный граф. ТЕОРЕМА х(С) < Л(С) < б(С).
Докааатвльство х< Л: Если Л = О, то х = О. Если Л = 1, то есть мост, а значит либо есть точка сочленения, либо С = Кз. В любом случае х = 1. Пусть теперь Л > 2. Тогда удалив Л вЂ” 1 ребро, получим граф С', имеющий мост (и, о).
Для каждого из удаляемых Л вЂ” 1 ребер удалим инцидентную вершину, отличную от и и е. Если после такого удаления вершин граф несвязен, то х < Л вЂ” 1 < Л. Если связен, то удалим один из концов моста — и или и. Имеем х < Л. Л < о: Если о = О, то Л = О.
Пусть вершина и имеет наименьшую степенгс о(о) = б. Удалим все ребра, инцидентные и Тогда Л < б. П 8.3. Теорема Менгера Интуитивно очевидно, что граф тем более связен, чем больше существует различных цепей, соединяющих одну вершину с другой, и тем менее связен, чем 215 8.3. Теорема Мангера меньше нужно удалить промежуточных вершин, чтобы отделить одну вершину от другой. В этом разделе устанавливается теорема Менгера, которая придает этим неформальным наблюдениям точный и строгий смысл. 8.3.1. Непересекающиеся цепи и разделяющие множества Пусть С(К Е) — связный граф, и и о — две его несмежные вершины.
Две цепи (и, о) называются вершинно-непересекающимися, если у них нет общих вершин, отличных от и и и. Две цепи (и, о) называются реберно-непересекающимися, если у них нет общих ребер. Если две цепи вершинно не пересекаются, то они и реберно не пересекаются. Множество вершинно-непересекающихся цепей (и,о) обозначим через Р(и, о). Р(и и): = ) (и о> 1 (и о> е Р 8г (и, о>, е Р =ь (и, и>, и (и о>г = (и оИ Множество Я вершин (и/или ребер) графа С разделяет две вершины и и о, если и и о принадлежат разным компонентам связности графа С вЂ” Я.
Разделяющее множество ребер называется разрезом. Разделяющее множество вершин для вершин и и о обозначим Я(и, о). Я(и,и):=(шЕ ь' !С вЂ” Я=СгОСг,оЕСыиЕСг). ЗАМЕЧАНИЕ Если и и и принадлежат разным компонентам связности графа С, то )Р(и,е)! = О и (Я(и, е) ~ = О. Поэтому без ограничения обшности можно считать, что С вЂ” связный граф. 8.3.2. Теорема Менгера в «вершинной форме» ТЕОРЕМА (Менгера) Пусгпь и и о — несмежные вершины в графе С. Наименьшее число вершин в множестве, разоеляющем и и о, равно наибольшему числу вершинно-непересекающихся простыл (и, о)-цепей: шах~Р(и,о)) = ппп(Я(и,о)1 ЗАМЕЧАНИЕ Пусть С вЂ” связный граф, и вершины и н е несмежпы. Легко видеть, что )Р) < !Я!.
Дейотвительно, любая (и,е)-цепь проходит через Я. Если бы (Р) > ф), то в Я была бы вершина, принадлежащая более чем одной цепи из Р, что противоречит выбору Р. Таким образом, т Р У Я )Р) < )Я~. Следовательно, шах )Р! < пап )Я). Утверждение теоремы состоит в том, что а любом графе существуют такие Р и Я, что достигается равенство )Р) = )Я).
доказательство Пусть С вЂ” связный граф, и и о — несмежные вершины. Совместная индукция по р и д. База: наименьший граф, удовлетворяющий условиям теоремы, состоит 216 Глава В. Связность из трех вершин и,тсг в и двух ребер (и,тс) и (ш,и). В нем Р(и,о) =,(и,тс,о) и Я(и,о) = (тс). Таким образом, ~Р(и,о)~ = ф(игр)( = 1.
Пусть утверждение теоремы верно для всех графов с числом вершин меньше р и/или числом ребер меньше д. Рассмотрим граф С с р вершинами и о ребрами. Пусть и, с я к", и, и— не смежны и Я вЂ” некоторое наименьшее множество вершин, разделяющее и и о, н: = ~Я~. Рассмотрим три случая. 1. Пусть в Я есть вершины, несмежные с и и несмежные с с. Тогда граф С- Я состоит из двух нетривиальньп графов Ст и Сз. Образуем два новых графа С„и С„, стягивая нетривиальные графы Ст и Сз к вершинам и и о, соответственно: С„: = С/Сы С„: = С/Сз (рис.
8.2). Рнс. В.2. Доказательство теоремы Мангера, случай 1 Я по-прежнему является наименьШим разделяющим множеством для и и и как в С„, так и в С„. Так как Ст и Сз нетривиальны, то С„и С„имеют меньше вершин и/или ребер, чем С. Следовательно, по индукционному предположению в С„и в С„имеется и вершинно-непересекающихся простгях цепей.
Комбинируя отрезки этих цепей от Я до и и от и до Я, получаем и вершиннонепересекающихся простых цепей в С. 2. Пусть все вершины Я смежны с и или с и (для определенности пусть с и), и среди вершин Я есть вершина тс, смежная одновременно с и и с с (рис: 8.3). Рнс. В.З. Доказательство теоремы Мангера, случай 2 Рассмотрим граф С': = С вЂ” и. В нем Я т, (тс) — разделяющее множество для и и и, причем наименьшее.
По индукционному предположению в С' имеется ~Я'т (тс) ~ = и — 1 вершинно-непересекающихся простых цепей. Добавим к ним цепь (и, тс, с). Она простая и вершинно не пересекается с остальными. Таким образом, имеем и вершинно-непересекающихся простых цепей в С. 217 8.3. Теорема Менгера 3. Пусть теперь все вершины 'Я смежны с и или с о (для определенности пусть с и), и среди вершин Я нет вершин, смежных одновременно с вершиной и и с вершиной о.
Рассмотрим кратчайшую (и,о)-цепь (и, ют,юю...,о), ют и б, юз ~ о (рис. оА). Рпс. 8.4. Доказательство теоремы Мангера, рву~ай 3 Рассмотрим граф С':=С/(юыюз), полученный из С склейкой вершин ю, и юз в вершину юь Имеем юз Е о', в противном случае цепь (и,юз,...,о) была бы еще более короткой. Следовательно, в графе С' множество о по- прежнему является наименьшим, разделяющим и и о, и граф С' имеет (по крайней мере) иа одно ребро меньше.
По индукционному предположению в С' существуют и вершинно-непересекающихся простых цепей. Но цепи, которые не пересекаются в С', не пересекаются и в С. Таким образом„имеем п вершинонепересекающихся простых цепей в С. П 8.3.3. Варианты теоремы Менгера Теорема Меигера представляет собой весьма общий факт, который в разных формулировках встречается в различных областях математики. Комбинируя вер'шинио- и реберно-непересекающиеся цепи, разделяя не отдельные вершины, а множества вершин, используя инварианты «и Л, можно получить множество результатов чтица теоремы Менгераь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
