В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 27
Текст из файла (страница 27)
Говорят, что множество вершин Я разделяет несменсные вершины а и Ь связного графа 6, если в графе 6 — Я вершины а и Ь принадлежат различным связным компонентам. В отой ситуации множество Я называют также сепаратором или (а, Ь)-сепаратором. Две (а, Ь)-цепи графа 6 называют непересекающимися, если у них нет общих вершин, за исключением а и Ь, и рвберно-непересекающимися, если у них нет общих ребер. Очевидно, не- >О в А. Емеличев в юь Следствие 34.9.
Всякий 3-связный граф с числом вершин п ~ 5 содержит ребро, стягивание которого приводит к 3-связному графу. З' Доказательство также проведем от противного. Пусть, стягивая некоторое ребро х=из 3-связного графа 6 в вершину а, получаем граф С, для которого х(С )= 2. (Равенство х(6„)= 1 невозможно в силу 3-связности графа 6.) Тогда в графе 6„су-, Д Ъ ществуют две вершины, удаление которых делает его несвязным. Одной из них должна быть У (в противном случае х (6) = 2) . Удалению вершины Ы из С„соответствует удаление вершин или г.„ из графа 6. Поэтому для любого ребра х = ношЕС граф 6 имеет такую вершину и>, что граф 6— — и — и — ш несвязен. Верн>ина и является точкой сочленения графа С„„что противоречит предыдущей теореме. 0 Отметим еще без доказательства следу>ощую теорему (см. обзор [21) ).
Теорема 34.10. Почти всв графы двусвязны. Поскольку каждый мост инцидентен точкам сочленения графа, то из этой теоремы вытекает Следствие 34.11. Почти все графы не содержат мостов. пересекающиеся цепи являются и реберно-непересекающимися, а обратное, вообще говоря, неверно. К. Менгер доказал в 1927 году следующую теорему, устанавливающую соотношение между числом непересекающихся простых цепей, соединяющих две несмежные вершины графа, и его связностью. Т е о р е м а М е н г е р а. Наименьшее число вершин, разделяющих две несмежные вершины графа а и Ь, равно наибольшему числу попарно непересекающихся простьсх (а, Ь)-цепей этого графа. Приведем доказательство, принадлежащее В. Маквайгу (1982 г.).
С' Ясно, что если )с вершин разделяют а и Ь, то существует не более сс попарно непересекающихся (а, Ь)- цепей. Остается показать, что если в графе С нет множества, содержащего менее чем Й вершин, разделяющих несмежные вершины а и Ь, то в нем имеются Й попаряо непересекающихся цепей. Используем индукцию по н. 'Утверждение правильно при )с= 1. Предположим, что оно верно для некоторого се ~ 1.
Рассмотрим граф С, в котором несмеясные вершины а и Ь нельзя разделить мноясеством, содержащим менее чем се+ 1 вершин. По предположению индукции в С имеется сс попарно непересекающихся (а, Ь)-цепей Рь Рг, ..., Р„. Рассмотрим множество вторых (считая а первой) вершин в этих цепях. Это множество состоит из Й вершин и, следовательно, оно не разделяет вершины а и Ь. Значит, имеется (а, Ь)- цепь Р, первое ребро которой не принадлежит ни одной из цепей Рс (1 = 1, (с). Пусть и — первая, считая от а, вершпна Р, принадлежащая одной из Рс (с = 1, (с), и пусть Р,„с обозначает (а, и)-подцепь цепи Р. Цепи Рь ..., Рм Рьчс могут быть выбраны, вообще говоря, многими различными способами.
Выберем их так, чтобы в графе С вЂ” а расстояние от и до Ь было минимально. Вслп окажется, что и = Ь, то Рь Рн ..., Р,ьс будет треоуемым набором из се+ 1 цепей. Допустим, что ать Ь, Тогда в графе С вЂ” и вершины а и Ь нельзя разделить множеством, содержащим менее чем сс вершин. По индуктивному предположенкю в этом графе имеется й непересекасощпхся (а, Ь)-цепей с,сь с,сг, ..., Ю„которые могут быть выбраны разными способами. Выберем их так, чтобы множество сь+с Е=ЕС О ЕР; 1 146 включало минимальное число ребер этих цепей. Иначе говоря, цепи ф должны состоять «в основном» из ребер цепей Рв Рассмотрим теперь граф Н, состоящий из вершин и ребер цепей чь ()г, ..., ~, и вершины и (эта вершина будет в графе Н изолированной). Пусть Р, — одна из цепей Р, (1 1, й + 1), у которой ребро, инцидентное вершине а, не принадлежит ЕН.
Ясно, что такая цепь среди Р, (1 = 1, й + 1) найдется, поскольку число их равно к+ 1, а цепей ф, составляющих Н, только й. Пусть, далее, х — первая, считая от а, вершина Р„входящая в т'Н. Если х = Ь, то, добавив цепь Р, к (7ь (тг, ..., Щ„получим требуемый набор из й+ 1 (а, Ь)-цепей. Допустим, что х т- Ь, и рассмотрим другие возможности для х.
Если х и, то обозначим через В кратчайшую (о, Ь)-цепь в 6 — а. Пусть г — первая, считая от о, вершина цепи В, лежащая на некоторой (7« (у = 1, й). Объединим цепь Р, с (о, г)-подцепью цепи В и обозначим полученную (а, г)-цепь через 6»»1 Цепи гп Дг, О» ~7»»1 обладают тем свойством, что расстояние в графе 6 — а от г до Ь меньше, чем расстояние от о до Ь, а это противоречит выбору Рь Рг, ..., Р„, Р,»ь Рассмотрим теперь последнюю возможность: х принадлежит некоторой цепи ф (1= 1, й). В этом случае (а, х)-подцепь цепи ()«имеет ребра в Е, иначе бы две цепи в (Рь Рг, ..., Єл»1) пересекались в вершинах, отличных от а, Ь, о. Заменив теперь (а, х) подцепь (7; на (а, х)-поддень Р„получим непересекающиеся (а, Ь)-цепи в графе 6 — о, и эти цепи будут использовать меньше ребер из Л, чем (7ь ..., ()», Снова получаем противоречие, которое и завершает доказательство теоремы.
0 Из теоремы Менгера непосредственно вытекает Теорема 35.1 (Х. Уитни, 1932 г.). Граф к-свяген тогда и только тогда, когда любая пара его несовпадоюи1их вершин соединена по крайней мере й непересекаюи1имися пенями. Имеется несколько аналогов и обобщений теоремы Менгера. Здесь мы остановимся на реберпом варн анте этой теоремы. Во многих прикладных задачах приходится рассматривать множество ребер (а не вершин, как ранее), разделяющих вершины а и Ь графа 6, т.
е. такое множество ребер В, что а и Ь входят в различные компоненты графа 6 — В. Минимальное относительно включения мно- 10« 147 жество В с этими свойствами называется (а, Ь)-рагреволс графа С. Т е о р е м а 35.2. Наибольшее число реберно-непересекающихсяя цепей, соединяющих две вершины графа, равно наименьшему числу ребер, разделяющих эти верши ньи > Доказательство атой теоремы легко получить, используя теорему Менгера. С этой целью сопоставим графу С граф С', который получается из С следуютцнм образом. Каждая вершина о сн )тС заменяется группой пз Рке.
35Д с)ед о попарно смежных вершин, а ребра графа С', соединяющие вершины из разных групп, находятся в биективном соответствии с ребрами графа С (рис. 35.)). Еслj в графе С нет (а, Ь)-разрезщ содержащего менее чем !с ребер, то в С' пег множества, имеющего менее чем !с вершин, разделяющего какую-либо пару вершин а', Ь' из групп, соответствующих а и Ь. Тогда по теореме Мепгера вершины а и Ь соединены в С по крайней мере )с вершинка-непересекающимися цепями, которым соответствует столько же реберпо-непересекающихся (а, Ь)-цепей графа С.
С другой стороны, ясно, что граф, имеющий (а, Ь)-разрез пз !с робер, может содержать не более )с реберно-непересекающихся (а, Ь)-цепей. 0 У Н Р Л |И Н Е Н И Я 1. Докаксктс, что Х(К ) = п — Н 2. Докажкте, что для всякого кубкческого графа С справедливо равенство к(С) = Х(6). 3. Докажите, что кубический двудолькый граф ке вмеет мостов. 4.
Пусть (С( =а 4 и С вЂ” минимально 2-связный граф, т. е. такой, который перестает быть 2-связным при удалении любого ребра. Покажите, что С не содержит треугольников. 5. Покажите, что в минимально 2-связном графе любая вершина смежна с вершиной степени 2. 6. Пусть С вЂ” связный граф и (С( > й, Покажите, что граф Сь нвляется й-связным. 7. Покажите, что реберный граф й(С) любого й-связного графа С также является й-связным.
8. Докажите, что в 3-связном графе чорез лгобые три вершины проходит простой цикл. 9. Докажите нли опровергните утверждению всякий 2-связный граф С, для которого б(С) ) 4, содержит дза реберно-непересекающихся остовных дерева. 10. Докажите или опровергните утверждение; граф, являющийся объеднпеаием двух реберно-непересекающнхся остовных деревьев, 2-связен. 11.
Какое наибольшее число точек сочленения может быть в графе порядка в7 12. Докажите, что граф, полученный из 4-связного графа удалением з ребер (г ( Й), является (Й вЂ” з)-связным. 13. Докажите, что для любого в-связного графа С число паросочетания а,(С) удовлетворяет неравенству а~(С) ) ((в + 1)/2) ((а) обозначает наибольшее целое число, не превосходящее а). 14.
Пусть Х вЂ” минимальное разделяющее мложество вершин ~рафа С и Сь Сь..., Сл — компоненты графа С вЂ” Х. Докажите, что для лгобых з ш Х н 1 = 1, й найдется такая вершина у я УСь что ху ш ЕС. Глава ГХ Планарность э 36. Плоские и планарные графы Во многих случанх пе имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацшо. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они не должны пересекаться.
Аналогичная задача возникает прп проектировании железнодорожных и других путей, где нежелательны переезды. Таким образом возникает понятие плоского графа. Плоским графом назовем граф, вершины которого являются точками плоскости, а ребра — непрерывными плоскими линиями без самопересечепий, соединяющими соответствующие вершины так, что никакие два ребра не Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
