Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 24
Текст из файла (страница 24)
Пусть Н вЂ” несвязный граф исключения, Н1 — его связная компонента. Последняя не покрывает всех вершин графа 6. Значит, в любом маршруте М(о', о"), соединяющем вершины о'~Н1 и о"~6',Нь найдется ребро (оь оэ) с концами о,~Н~ и азфНь Это ребро соединяет компоненту связности Н1~Н с некоторой другой компонентой связности Нас Н (так как Н покрывает все вершины графа 6, отанН). Добавим ребро (оь от) к части Н и получим объемлющую часть Н'.
Любая часть Н"г:.Н либо не содержит ребра (оь оз), т.е. принадлежит графу исключения Н и не является частью из семейства (Р,)(, либо содержит это ребро и не является графом, двусвязным по ребрам. Действительно, после удаления этого ребра Н" становится несвязным графом, так как вершины о1 и пз связаны только им. Значит, Н"ф(Р;)и т.е. Н' — тоже граф исключения и Н вЂ” не максимален.
Д Максимальные деревья. Пусть 6 — связный граф, (Я;)— семейство всех его циклов. Тогда максимальный гРаф исключения Т не содержит циклов. Он покрывает все вершины графа 6, так как циклы А не имеют концевых вершин, и связен, так как любой цикл двусвязен по ребрам. Следовательно, Т вЂ” дерево.
Будем называть его максимальным деревом в графе 6. Максимальное дерево в конечном связном графе 6 уже было раньше построено при определении цикломатического числа у(6) графа 6. При этом было удалено у(6) ребер. Легко видеть, что все максимальные деревья Т графа 6 имеют одно и то же число вершин, равное числу т, вершин графа 6, и число ребер, равное т — 1. Следовательно, при построении этих деревьев нужно удалить одинаковое число ребер, равное цнкломатическому числу у(6) графа 6. Пусть в графе 6 удалено у(6) ребер.
Если остался связный граф Н, его цикломатическое число уменьшилось на у(6) и стало равно нулю. Таким образом, при удалении произвольных у(6) ребер из конечного связного графа 6 получаем либо максимальное дерево, либо несвязный граф. Задача о минимальном соединении. Пусть каждому ребру е конечного неориентированного связного графа 6 приписано некоторое действительное число ц(е) — вес этого ребра. Минимальным соединением называется максималь- ыа ное дерево Тс:.6 с минимальным общим весом 1х(Т) = = ~ р(е), е~т Задача о минимальном соединении внешне похожа на значительно более сложную задачу о коммивояжере, в которой требуется найти в полном неориентированном конечном графе К„гамильтонов цикл У минимального общего веса 1х(Я) ='~р(е).
г~а В отличие от этой задачи минимальное соединение легко найти. Его построение начинается с выбора ребра е~ минимального веса ц(е~). На каждом следующем шаге к уже построенной части Т;, добавляется ребро еь такое, что часть Т;=Т;, ()е; не имеет циклов и из всех ребер, обладающих этими свойствамн, е; имеет минимальный вес р(е~). Если имеется несколько таких ребер, то можно выбрать любое из них. Пусть лес Т~ ~ не покрывает всех вершин графа 6.
Тогда сушествует ребро е, ипцидентное вершине сф Т; ь Его добавление к Т;, не приводит к появлению цикла (е— концевое ребро), и часть Т~ ~ можно расширить. Если Т~ ~ покрывает все вершины 6, но несвязен, его тоже можно расширить. Действительно, в маршруте М (о', о"), соединяющем в графе 6 вершины о' и о" из различных компонент Т; ь найдется хотя бы одно ребро (оь оз) „концы которого принадлежат разным компонентам леса Т~ ь В графе Т;=Т; ~() (оь оз) это ребро является раздсляюи(им (т.е. после удаления граф Т~ становится несвязным), и через него не проходит никакой цикл. Нет в том графе и циклов, не проходящих через ребро (оь о,), они принадлежали бы лесу Тг и Следовательно, пока не возникает дерево Т ь покрываюшее все вершины графа 6 (и — их количество), процесс расширения части Т; продолжается.
Отметим, что все ребра дерева Т„~ можно занумеровать в порядке их включения в эту часть графа 6. Пусть Т вЂ” дерево минимального общего веса, покрывающее вершины графа 6. Оно существует, так как в конечном графе количество покрывающих деревьев конечно. Рассмотрим ребро е,енТ„',Т минимальным номером й Граф Т'=Т и ()е; имеет цикломатическое число 1, т.е. не является деревом. В нем имеется некоторый цикл Я и другого цикла 2' быть не может. Действительно, в последнем имелось бы реброе', не принадлежащее Я, и, выбросив его из Г, мы полу- чили бы связный граф Т" с цикломатическим числом О и циклом 2.
Наконец, цикл У проходит через ребро еи в дереве Т=Т", е циклов нет. В дереве Т ~ нет циклов, значит, Я содержит ребро е и"-Т„ь Тогда граф Т1 —— Т'" е'= Т ()е,'~,е' покрывают все вершины 6 и не имеет циклов, т.е. является максимальным деревом в графе 6. Так как дерево Т имеет минимальный общий вес, р(Т,) — р(Т) = ~~~~ ~л(е) — ~~~~~ р(е) = р(е;) — р(е') "О. е~т' чмт Однако неравенство весов р(е;) и р(е') невозможно, иначе при построении Т; вместо е; было бы выбрано ребро е'. Действительно, все ребра Т; 1 принадлежат дереву Т, принадлежит ему и ребро е'.
Значит, Т'= Т;,()е'с:Т и в этой части графа 6 нет циклов. Итак, р(е;) =р(е') и ~л(Т~) =р(Т), т. е. Т, — дерево минимального общего веса, максимальное в графе 6. В нем больше общих ребер с деревом Т, ь чем в дереве Т. Понторив при необходимости такую замену ребер, мы придем в конце концов к дереву Т„1 и докажем, что р(Т„1) = =р(Т), т. е. мы построилн максимальное в графе 6 дерево Т„, минимального общего веса. Двудольные графы. Граф 6 называется двудольным, если множество его вершин Р распадается иа два непересекающихся подмножества Р' и Р", таких, что каждое ребро графа 6 имеет один конец из Г, а другой — из г'". Двудольные графы рассматриваются во многих задачах дискретной математики.
Одна из них — задача о различных представителях подмножеств, Пусть дано множество Ю и семейство его подмножеств (У;), требуется в каждом множестве этого семейства выбрать некоторый элемент ьч — представитель этого множества — так, чтобы разным множествам У; и У; соответствовали бы различные представители и; и иь Множество ~" вершин двудольного графа 6, соответствующего этой задаче, — это множество всех элементов К; множество г'" состоит из элементов о',.', соответствующих подмножествам У; рассматриваемого семейства. Вершины вя77 и о",. анжел являются концами ребра (ш, о",.) в том и только том случае, когда венУь Требуется найти максимальное паросочетание (иерасширяемое множество ребер (ю, о,".), в котором все вершины ш и о,.' различны) и прове- 120 рить, каждая ли вершина о;е:-Р" является концом некоторого ребра из этого паросочетания.
Другой пример, Пусть заданы два произвольных множества Г и Р" элементов разной природы (тем самым эти множества не имеют общих элементов) и отношение о'Ро", являющееся истинным или ложным для всех пар (о', о")ен ен Р'Х Р". Тогда это отношение определяет двудольный граф 6: ребро (и', о") принадлежит 6, если отношение и')тп" истинно. Теорема 4.6. Граф 6 является двудольным тогда и только тогда, когда все его циклы имеют четную длину. Для цикла Я двудольного графа это условие выполняется: вершины, через которые этот цикл проходит, поочередно принадлежат множествам Г и Р". Пусть теперь все циклы графа 6 имеют четную длину. Выберем вершину и, в некоторой связной компоненте 6О графа 6. Множество вершин 6, распадается на множество Р вершин с четным расстоянием от о, и множество к" вершин с нечетным расстоянием от оа.
Если о~ен1~, о,я$', то кратчайшие простые цепи Ь|(о„о,) и Еэ(оэ, пэ) имеют четную длину. Предположим, что ребро (оь о.) существует. Пусть о' — последняя общая вершина для 1.~(оэ, о~) и Т.,(ою, оэ), т. е Ь(оо, п~) =~'(оа о')Ф" (и', о~) 1-э(оо, оз) =~'(оа, о )()~-"'(о' пэ) и начальные ребра Л" и ь'" различны. Тогда цепь Ь" (о', п~)0(пь оэ)())-'"(ом о'), где й"'(ом о') обозначает цепь Ь'"(и', о,), пройденную в обратном порядке, является циклом нечетной длины, что противоречит предположению.
Таким образом, никакие вершины из У не соединены ребром; аналогичное утверждение доказывается и для Г. Поэтому всякое ребро из 6э имеет один конец в У, а другой — в Г и 6, — двудольный граф. Поскольку это верно для любой связной компоненты графа 6, то и сам граф 6 — двудольный. П. Максимальные двудольиые части графа. Пусть запрещенное семейство частей неориентированного графа 6 состоит из простых циклов Я нечетной длины. Тогда графы исключения можно рассматривать как двудольные, а максимальные графы исключения — это максимальные двудольные части графа 6.
Циклы нечетной длины не имеют концевых вершин и являются двусвязными по ребрам. В силу соответствующих общих теорем из этого следует, что максимальные двудоль- 121 ные части графа 6 покрывают все его вершины и в каждой связной компоненте этого графа лежит одна связная компонента максимальной двудольной части. Для построения максимальной двудольной части графа 6 выберем в каждой его связной компоненте 6, вершину ом Для каждой вершины оеи6з можно определить ее ранг г(о, оз) относителыю вершины о„равный ее расстоянию от вершины о,.
Удалим из 6з все ребра (о', о"), связывающие вершины о' н о" рангов одинаковой четности. Так как все ребра кратчайшего пути Е(ом ..., и), соединяющего вершину оз с вершиной п~б„соединяют вершины соседних рангов 1 н 1+1, имеющих разную четность, онн не будут удалены. Значит, часть 6' графа 6м состоящая из вершин о~ба и неудаленных ребер, — связный граф. Легко видеть, что он двудольный: множество Г состоит из всех вершин четных рангов, множество У" — из вершин нечетных рангов, и каждое оставшееся ребро соединяет вершину из множества Г с вершиной из множества У". Значит, в нем нет циклов нечетной длины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
