Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 23
Текст из файла (страница 23)
Следовательно, максимальное удаление от вершины оз максимального типа в дереве рав. но ее типу й или й — 1. Остается показать, что если вершина в имеет немакснмальный тип, она является началом более длинной цепи. Построим сначала цепь Т.(в, ов), связывающую эту вершину с вершиной максимального типа й, Если о, — единственная вершина типа й, она связана по крайней мере с двумя вершинами типа й — 1, так как в графе 6м и не является концевой.
Следовательно, можно построить цепь Т.(ом о') длины й — 1, не проходящую через последнее ребро цепи Т.(о,оз) и не имеющую с этой цепью общих 8 — 750 113 вершин (иначе в дереве 6 был бы цикл). Цепь Т.=Е(п, эо) () ~(по, э') имеет длину большую, чем й — 1, Если в дереве 6 есть две вершины о, и о, максимального типа Й, то тоже можно построить связывающую о с по цепь Т.(в,еа), В случае, когда эта цепь проходит через другую вершину ш максимального типа А, ее длина не меньше двух. Тогда вершина и, является началом цепи Е(ц, и') длиной А — 1 с первым ребром (и,, с"), ведущим в вершину э" типа А — 1, Эта цепь не имеет с первоначально построенной цепью Е(п, эо) общих вершин, иначе в дереве 6 был бы цикл.
Следовательно„ !.=.(.(э, сэ) 0 ~(эо, и') — цепь длиной, не меньшей й+1, с началом в рассматриваемой вершине о. Наконец, если цепь Ь(с, ээ) не проходит через другую вершину ш максимального типа, длину Й+! или больше имеет начинающаяся в вершине и цепь Е=Е(с, аэ) 0 () (п„и,) () Е(п„э"), где цепь Ь(оь и') длиной й — 1 строится так же, как в предыдущем случае цепь 1.(па, и'). Итак, для любой вершины немаксимального типа ее максимальное удаление больше А. С! Из теоремы непосредственно следует, что дерево имеет либо один, либо два центра.
Диаметральные цепи в деревьях проходят через его центр оа или через оба центра са и вп если их два. В первом случае длина диаметральной цепи равна 2А — 2, а во втором 2Й вЂ” 1, где А — максимальный тип вершин дерева 6 (подразумевается, что оно конечное). Такая цепь строится из двух радиальных цепей А(пм и') и Е(по, и") или Ь(пэ о') н Е(пь и") длиной й — 1, не имеющих общих вершин и существующих, как это показано ранее. Когда в дереве 6 два центра — пэ и эь эти цепи соединяются ребром (по,~~) и получается цепь длиной 21 †. Докажем, что более длинных цепей в дереве О нет.
Пусть Š— какая-либо цепь, пэ, эь ..., пь — последовательность ее вершин, Ао, Аь ..., Аь — их типы. Вначале типы вершин могут расти, Пусть йа<й~<...<Аз (д<Й), Число вершин в этом участке последовательности вершин не превосходит максимального типа А, а число соединяющих их ребер пути Т. не больше й — 1. Соседних вершин одинакового ранга не больше двух, это центры дерева 6, если их два. В последнем случае к участку возрастания типа вершин вдол~ цепи Е может добавиться одно ребро неубывания типа. Если цепь А длиннее, возрастание типа вершин вдоль нее должно смениться убыванием.
Пусть сз — первая вершина цепи Е, тип которой меньше типа предыдущей: йх ~>йх. Тогда тип следующей вершины еще меньше, и далее вдоль пути типы вершин убывают: Аз ~ >Ах >... ...>йм Действительно, у вершины оз только одна соседняя вершина имеет больший тип — это вершина пх ~, а все остальные соседние вершины, в том числе н вершина пз ч ь имеют тип меньший, чем йа . Точно так же у вершины ох +~ больший тнп имеет только вершина сх, а типы осталь ных соседей меньше Аз+~ н т.д. Таким образом, последовательность пм пь..., оь можно разбить на участки возрастания типа оа, оь ..., сж его убывания од, па+~, ..., сь (д'=д или и+1) и, когда цепь проходит через две вершины ох и ох максимального типа, участок постоянства типа.
Длина участка убывания типа также не превосходит А — 1, а общая длина цепи Е не больше 2Й вЂ” 2 или 2Й вЂ” 1 в случае, когда эта цепь проходит через два центра дерева 6. Остается доказать, что цепь Е, не содержащая центра, имеет меньшую длину и не является диаметральной.
Пусть й'<й — максимальный ранг вершины с', через которую проходит эта цепь. Тогда до этой вершины типы растут, а после нее падают. Следовательно, длина участков этой цепи до и после вершины о' не превышает А' — 1, а общая длина цепи Е ие больше 2А' — 2<2й — 2, Если в дереве 6 два центра — по и ои а цепь Е проходит только через один из них, ее длина не больше 2й — 2 и она также не является диаметральной, Цикломатическое число графа.
Пусть 6 — конечный не- ориентированный граф. Его цихломатическим числом называется у(6) = ч, + т,— ч„, где ч,— число связных компонент графа; ч,— число его ребер, а ч, — число вершин. Цикломатическое число дерева равно нулю, цикломатическоечислолеса — сумме цикломатическнх чисел своих связных компонент-деревьев, т. е. также равно нулю.
Цикломатические числа остальных конечных графов положительны. Так как цикломатическое число несвязного графа равно сумме цикломатических чисел связных компонент, 'достаточно рассмотреть связный граф 6. Если этот граф — дерево, его цикломатическое число равно нулю. В противном случае в графе 6 есть цикл Е (ан ем..., еь). Можно выбросить любое ребро этого $% 115 цикла, и граф останется связным. Дейстнительно, пусть М(е,', е.,',...., е, ) — маршрут, связываюший вершины и' и о"ен6 и содержащий выброшенное ребро е цикла Е (если маршрут не содержит такого ребра, он связывает вершины и' и о" и в новом графе 6').
Это ребро можно заменить маршрутом М'(еь е„~ь ..., е„еь ..., еч ~), состоящим из остальных ребер цикла Л и имеющим те же концы, что и само ребро. Если в 6' еще имеются циклы, можно выбросить следующее ребро, не нарушая связности, и т.д. В конце концов получится неориентированный связной граф 6т -без циклов, т.е. дерево (так как число вершин всех конструируемых графов 6', 6"... 6' не меняется, если оно больше единицы, то все ребра выбросить нельзя), Число оставшихся ребер на единицу меньше числа вершин графа 6т, а значит, и исходного графа 6, но в последнем на у ребер больше.
Следовательно, у(6) =т,(6т) +т,(6т) — т„(6')+ +у=у~О. Максимальные графы исключения. Пусть дано семейство (РД~ частей (называемых запрещенными) некоторого графа 6', Часть Н этого графа называется графом исключения, если она не содержит ни одной части из этого семейства, и максимальным графом исключения, если она не вложена в другой граф исключения. Обычно считается, что пустой граф Я не принадлежитсемействузапрещенных частей (РД(, иначе графов исключения нет.
Если графы исключения существуют, то существуют и максимальные графы исключения. Когда рассматриваемый граф конечный, цепочка графов исключения, в которой каждый следуюший содержит все предыдущие, должна оборваться, так как переход к следующему графу исключения в этой цепочке связан с добавлением новых элементов графа 6, а их количество конечно. Следовательно, цепочка должна оборваться, и последний входящий в нее граф — это максимальный граф исключения.
Отсюда следует, например, что любой граф 6 содержит максимальные части без циклов (семейство (У;) состоит из всех циклов графа 6). Можно также ограничить степени рн(и) вершин оен6 в рассматриваемых графах исключения заданными значениями й(о). Для этого семейство (г';) запрещенных частей должно включать все звездные графы з(о) графа 6 с (й(о) +1) ребрами. Максимальные паросочетания и устойчивые множества вершин в графе. Пусть для всех вершин о графа 6 А(о) =1. Тогда графы исключения Н~6 состоят из изолированных вершин и пар вершин о', о"ен6, связанных одним ребром ,(о', о")еп6.
Части Н, содержащие только такие пары, называются паросочатаниями в графе 6. Однако в отличие от приведенной ранее терминологии максимальным паросочетанием в конечном графе 6 называется ие просто паросочетание, которое не вложено ни в какое другое„ а содержащее максимально возможно число ребер. Пусть теперь запрещенным множеством частей графа 6 является множество пар вершин о', о"~6, инцидентных какому-либо ребру этого графа, Тогда любой граф исключения Н состоит из изолированных вершин, не являющихся соседними в графе 6.
Такие множества вершин графа 6 называются устойчивыми. Как и паросочетание, устойчивое множество называется макспмальяьсм, если оно содержит максимально возможное число вершин. Две теоремы о максимальных графах исключения. Теорема 4.4 Если никакая конечная запрещенная часть Р; не имеет концевых ребер, то максимальный граф Н по крывает все вершины графа 6. Действительно, если некоторын граф исключения Н' не содержит ребер, инцидентных некоторой вершине оеп6, эту вершину вместе с любым инцидентным этой вершине ребром можно добавить в часть Н'. В полученной части Н" вершина у является концевой а любая часть Н" либо ие содержит о и тогда является частью Н, т.е. не принадлежит семейству (Р;), либо содержит вершину о, являющуюся в этой части концевой (изолированные вершины тоже считаются концевыми), и не принадлежит семейству (()), состоящему из частей без концевых вершин. Таким образом, часть Н' не максимальна.
(~ Теорема 4.5. Пусть 6 — связный граф и (Гч)',— семейство его частей, каждая из которых по ребрам двусвязна. Тогда максимальные графы исключения связны и покрывают все вершины графа 6. Граф 6 называется двусвязным по ребрам, если после удаления любого его ребра он остается связным. В двусвязном графе нет концевых вершин. Действительно, после удаления концевого ребра, единственного инцидентного такой вершине, она становится изолированной, а соответствующая часть 6' графа 6 — несвязной, Следовательно, максимальный граф исключения Н для семейства двусвяз- 117 ных конечных 'частей (Р;)( покрывает все вершины графа 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
