Новиков Ф.А. Дискретная математика для программистов (860615), страница 50
Текст из файла (страница 50)
Пусть k(G) > 1. Тогда существуют две вершины и и v, песоединённые цепыо. Следовательно, вершины и и v принадлежат разным компонентам связности. Положим G1 — компонента связности для и, а G2 — всеостальное. Имеем G = G\ U G2.•1Карл Менгер (1902-1985).266Глава 8. СвязностьЗАМЕЧАНИЕНесвязный граф всегда можно представить как объединение связных компонент.
Этикомпоненты можно рассматривать независимо. Поэтому во многих случаях можно безограничения общности предполагать, что рассматриваемый граф связен.8.1.2. Точки сочленения, мосты и блокиВершина графа называется точкой сочленения, или разделяющей вершиной, еслиеё удаление увеличивает число компонент связности. Мостом называется ребро,удаление которого увеличивает число компонент связности. Блоком называетсясвязный граф, не имеющий точек сочленения.ПримерВ графе, диаграмма которого представлена на рис. 8.1:1) вершины u,v — точки сочленения, и других точек сочленения нет;2) ребро х — мост, и других мостов пет;3) правильные подграфы{а, Ь, w}, {b,u,w},и других блоков нет.w{a,b,u,w},с{с, d, v}, {e,f,v}— блоки,dРис.
8.1. Точки сочленения, мосты и блокиЛЕММАВ любом нетривиальном графе есть по крайней мере две вершины, которые не являются точками сочленения.ДОКАЗАТЕЛЬСТВОНапример, таковыми являются концы любого диаметра.•Пусть G(V, Е) — связный граф и v е V. Тогда следующие утверждения эквивалентны:ТЕОРЕМА 11. v — точка сочленения.2. Эи, w G V [и фи) & V ( u , w ) G (v G ( u , w ) ) ) .3. 3 U, W {U П W = 0 & U U W = V - v & Vu е U, w Е W (V (и, w)G (v G (и, w)G))).8.1. Компоненты связности267ДОКАЗАТЕЛЬСТВО[ 1 = ^ 3 ] Рассмотрим G' : = G — v. Граф G' не связей, k(G') > 1, следовательно,G' имеет по крайней мере две компоненты связности, то есть V — v = U и W,где U — множество вершин одной из компонент связности, a W — все остальныевершины. Пусть и е U, w € W.
Тогда ->3{u,w) G ,. Но k(G) = 1, следовательно,3(u,w)G,и значит, V (u,w)G(v Е(u,w)G).[ 3 = ^ 2 ] Тривиально.[ 2 = И ] Рассмотрим G' : = G - v. Имеем:откуда v — точка сочленения.Следовательно, k(G') > 1,•СЛЕДСТВИЕЕсли вершина инцидентна мосту и не является висячей, то она является точкой сочленения.Пусть (и, v) — мост и d(v) > 1. Тогда v смежна с w, причём w ФФ и.
Далее разбор случаев. Если 3 (и, w) (v £ (и, w)), то ребро (и, v) принадлежитциклу, что противоречит тому, что (и, v) — мост. Если же -i3 (и, w) (v £ {u,w)),то V (и, w) (v е (и, w)), и значит, v — точка сочленения по пункту 2 теоремы.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕОтнюдь не всякая точка сочленения является концом моста.Пусть G(V, Е) — связный граф их е Е.
Тогда следующие утверждения эквивалентны:ТЕОРЕМА 21.x—мост.2. хне принадлежит ни одному простому циклу.3. 3u,w€ V (V(u,w)G(х е(u,w)G)).4. 3 U, W {U П W = 0 & U U W = V k Vw Е U (Угу G W (V {и, w)GДОКАЗАТЕЛЬСТВОУпражнение 8.16.{х 6 (и,w))G))).•8.1.3. Вершинная и рёберная связностьПри взгляде на диаграммы связных графов (сравните, например, рис. 7.5 и 8.1)возникает естественное впечатление, что связный граф может быть «более» или«менее» связен. В этом подразделе рассматриваются некоторые количественныемеры связности.Вершинной связностью графа G (обозначается x(G)) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.268Глава 8.
СвязностьПримерx(G) = 0,если G несвязен;x(G) — 1,если G имеет точку сочленения;х(Кр) = р - 1, если Кр — полный граф.Граф G называется п-связным, если x(G) = п.Рёберной связностью графа G (обозначается Л(G)) называется наименьшее числорёбер, удаление которых приводит к несвязному или тривиальному графу.ПримерX(G) = 0,если G несвязен;Л(G) = 1,если G имеет мост;Л(К р ) = р — 1, если Кр — полный граф.ТЕОРЕМАyc(G)< Л(G)^6{G).ДОКАЗАТЕЛЬСТВО[ х ^ А ] Если Л = 0, то к = 0. Если А = 1, то есть мост, а значит, либо естьточка сочленения, либо G = К2.
В любом случае к — 1. Пусть теперь А ^ 2.Тогда, удалив Л — 1 ребро, получим граф G', имеющий мост (и, v). Для каждогоиз удаляемых Л — 1 рёбер удалим инцидентную вершину, отличную от и и v. Еслипосле такого удаления вершин граф несвязен, то х ^ Л — 1 < Л. Если связей, тоудалим один из концов моста — и или v. Имеем к ^ Л.[ Л ^ 6 ] Если 5 = 0, то Л = 0. Пусть вершина v имеет наименьшую степень:d(v) = 5. Удалим все рёбра, инцидентные v. Тогда Л ^ 6.•8.1.4. Оценка числа рёберЛегко заметить, что инварианты p{G), q(G) и k(G) не являются независимыми.Пусть р — число вершин, q — число рёбер, к — число компонент связности графа. ТогдаТЕОРЕМАДОКАЗАТЕЛЬСТВО[ р - k ^ q ] Индукция по р. База: р = 1, q = 0, к = 1.
Пусть оценка верна для всехграфов с числом вершин меньше р. Рассмотрим граф G, p{G) = р. Удалим в Gвершину v, которая не является точкой сочленения: G' : — G — v. Тогда если v —изолированная вершина, то р' = р — 1, к' = к — 1, q' = q. Имеем р — к = р' — к' <^ q' = q. Если v — пе изолированная вершина, то р' — р— 1, к' = к, q' < q. Имеем:р - к = 1 + р' - к' ^ 1 + q' < q.2698.2. Теорема Менгера[ Я ^ (р - к)(р - к + 1)/2 ] Метод выделения «критических» графов.
Число рёберq графа с р вершинами и к компонентами связности не превосходит числа рёберв графе с р вершинами и к компонентами связности, в котором все компонентысвязности суть полные графы. Следовательно, достаточно рассматривать толькографы, в которых все к о м п о н е н т ы с в я з н о с т и полные.
С р е д и всех графов с рвершинами и к полными компонентами связности наибольшее число рёбер имеетграф Кр, в котором все рёбра сосредоточены в одной компоненте связности:k-1Kp: = Kp-k+i U ( J Кг.г=1Действительно, пусть есть две компоненты связности Gi итакие, что 1 < р\ == p(Gi) ^ р2 = p{G2). Если перенести одну вершину из компоненты связностиG\ в компоненту связности G2, то число рёбер изменится на Aq = р2 — {pi — 1) == Р2 ~ Pi + 1 > 0.Следовательно, число рёбер возросло.
Таким образом, достаточно рассмотретьграф Кр. Имеем:q{Kp) = (р-кСЛЕДСТВИЕ 1+ 1 ){р -к + 1 - 1)/2 + 0 = (р - к){р -к+Рассмотрим неравенство (р—1)(р—2)/2 < q ^при различных значениях к.к — 1 (р - 1)(р - 2)/2 < (р - 1)р/2к = 2 (р - 1)(р - 2)/2 < (р - 2){р - 1)/2к = 3 (р - 1)(р - 2)/2 < (р - 3)(р - 2)/2(р—к)(р—к+1)/2выполняется,пе выполняется,не выполняетсяи т. д.ДОКАЗАТЕЛЬСТВО•Если q > (р - 1){р — 2 ) / 2 , то граф связен.ДОКАЗАТЕЛЬСТВОСЛЕДСТВИЕ 21)/2.•В связном графе р - 1 ^ q ^ р(р - 1 ) / 2 .Следует из теоремы при к = 1.•8.2. Теорема МенгераИнтуитивно очевидно, что граф тем более связен (при использовании различныхмер связности), чем больше существует различных цепей, соединяющих однувершину с другой, и тем менее связен, чем меньше нужно удалить промежуточных вершин, чтобы отделить одну вершину от другой.
В этом разделе устанавливается теорема Менгера, которая придает этим неформальным наблюдениямточный и строгий смысл.270Глава 8. Связность8.2.1. Непересекающиеся цепии разделяющие множестваПусть G(V, Е) — связный граф, и и v — две его несмежные вершины.
Две цепи(и, v) называются веришнно-непересекающимися, если у них пет общих вершин,отличных от и и v. Две цепи (и, v) называются рёберно-непересекающимися, еслиу них нет общих рёбер. Если две цепи вершинио не пересекаются, то они ирёберно не пересекаются. Обозначим через Р(и, v) множество вершинно-пепересекающихся цепей (u,v).Множество S вершин (и/или рёбер) графа G разделяет две вершины unv, еслии и v принадлежат разным компонентам связности графа G—S.
Разделяющее множество рёбер называется разрезом. Разделяющее множество вершин для вершини и v обозначим S(u,v).Для заданных вершин и иу множества Р(и, v) и S(u, v) можно выбирать различным образом.Из определений следует, что любое множество P(u,v)ющихся цепей обладает тем свойством, чтовершиино-непересека-(u,v)EP(u,v)а любое разделяющее множество вершин S(u, v) обладает тем свойством, чтоG - S = GiUG2 k v €GIк и е G2.ЗАМЕЧАНИЕЕсли и и v принадлежат разным компонентам связности графа G, то \P(u,v)\ = 0 и\S(u, г>)| = 0.
Поэтому без ограничения общности можно считать, что G — связный граф.Пример В графе, диаграмма которого представлена на рис. 8.2, можно выбрать множества вершипио-иепересекающихся путей Р\ = {(u,a, d, v), (и, Ь, е, ?;)}и Р2 = {(и, 6, d, г>), (и, с, е, г;)}. Заметим, что путь (и, с, Ь, d, v) образует множество Рз вершиппо-непересекающихся путей, состоящее из одного элемента. Множества вершин Si = {а, Ь, с} и S2 = {d,e} являются разделяющими для вершин и И V.Р\р2и»——РзРис. 8.2. Вершинно-непересекающиеся пути и разделяющие множества вершин2718.2.
Теорема Менгера8.2.2. Теорема Менгера в «вершинной форме»(Менгера) Пусть и и v — несмежные вершины в графе G. Наименьшеечисло вершин в множестве, разделяющем и и v, равно наибольшему числу вершиннонепересекающихся простых (и, v)-цепей:ТЕОРЕМАmax\Р(и, v)| = min \S(u, г»)|.ЗАМЕЧАНИЕПусть G — связный граф и вершины и и v несмежны. Обозначим Р: = P(u,v), S\ =: = S(u,v). Легко видеть, что \Р\ ^ |5|.
Действительно, любая (^,г>)-цепь проходит черезS. Если бы |Р| > |5|, то в S была бы вершина, принадлежащая более чем одной цепииз Р, что противоречит выбору Р. Таким образом, VP (VS (|Р| ^ |<5|)). Следовательно,шах|Р| ^ minimi. Утверждение теоремы состоит в том, что в любом графе существуюттакие Р и4S, что достигается равенство |Р| = |5|.Пусть G — связный граф, и и v — несмежные вершины. Совместная индукция по р и q. База: наименьший граф, удовлетворяющий условиямтеоремы, состоит из трех вершин u,w,v и двух рёбер (u, w) и (w,v). В нёмP(u,v) = {(и, w, и)} и S(u,v) = {u>}.
Таким образом, \P(u,v)\ = \S(u, г»)| = 1.Пусть утверждение теоремы верно для всех графов с числом вершин меньше ри/или числом рёбер меньше q. Рассмотрим граф G с р вершинами и q ребрами.Пусть u,v eV, причём и} v — не смежны и 5 — некоторое наименьшее множествовершин, разделяющее и и v. Обозначим п: = \S\. Рассмотрим три случая.ДОКАЗАТЕЛЬСТВО[ 1 ] Пусть в S есть вершины, несмежные с и и несмежные с v. Тогда граф G — Sсостоит из двух нетривиальных графов G\ и G2. Образуем два новых графа Guи Gv, стягивая нетривиальные графы Gi и G2 к вершинам unv соответственно:Gu : = G/Gi, Gv : = G/G2 (рис. 8.3).Рис. 8.3.
К доказательству теоремы Менгера, случай 1S по-прежнему является наименьшим разделяющим множеством для и и v как вGu, так и в Gv. Так как G\ и G2 нетривиальны, то Gu и Gv имеют меньше вершини/или рёбер, чем G. Следовательно, по индукционному предположению в Gu ив Gv имеется п вершинпо-пепересекающихся простых цепей. Комбинируя отрезки этих цепей от и до S и от 5 до v, получаем п вершинно-непересекающихсяпростых цепей в G.[ 2 ] Пусть все вершины S смежны с и или с v (для определённости пусть с и)и среди вершин S есть вершина w, смежная одновременно с и и с г; (рис. 8.4).272Глава 8. СвязностьРис.
8.4. К доказательству теоремы Менгера, случай 2Рассмотрим граф G' : = G — w. В нем S — w — разделяющее множество дляи и v, причём наименьшее. По индукционному предположению в G' имеется15 — w\ = n - 1 вершинпо-пепересекающихся простых цепей. Добавим к нимцепь (u,w,v). Она простая и вершиино не пересекается с остальными. Такимобразом, имеем п вершинпо-пепересекающихся простых цепей в G.[ 3 ] Пусть теперь все вершины S смежны с и или с v (для определённостипусть с и) и среди вершин S нет вершин, смежных одновременно с вершинойit и с вершиной v. Рассмотрим кратчайшую (п,г;)-цепь (u,w\,w 2 , ...,v),w\€ S,w2 ф v (рис. 8.5).Рис. 8.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
