В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 33
Текст из файла (страница 33)
Лемма 41.2. Нели результатолс некоторого шага алгоритма 7 является частичная укладка С планарного графа С такая, что ~Г(Я) ~ > 2 для всякого сегмента Я относительно С, то Я(С) — двудольный граф. с Доказательство проведем от противного. Пусть граф Я(С) не двудольный, Тогда на основании теоремы Кенпга в Я(С) есть т-цикл нечетной длины. Этому циклу соответствует последовательность Р сегментов Ян Яз, ... ..., Я„Я1 относительно Сь в которой каждые соседние сегменты конфликтующие.
Поэтому на основании леммы 41 1 Г(Я;) = (Гь Гг) (1= 1, т). Поскольку С вЂ” частичная укладка графа С, то все сегменты Яь Яг, ..., Я, могут быть уложены, а так как соседние сегменты последовательности Р конфликтуют, то опи должны быть уложены в различные грани (Г1 и Гг).
Но это невозможно в силу нечетпостн числа сегментов т. З Т е о р е м а 41.3. Если С вЂ” планарный граф, то результатолг калгдого ~иова алгоритма 7 является частичная укладка С графа С. с' Доказательство проведем индукцией по числу шагов. 179 Полученный па начальном этапе работы алгоритма ( граф 6 является простым циклом, который присутствует в любой укладке графа С. Следовательно, 6 — частишая укладка.
Пусть граф С, построенный на предыдущем пзаге работы алгоритма т, является частичной укладкой. Покажем, что граф С 0 Л, полученный па очередном шаге присоединением к 6 к-цепи Л, так~не является частичной укладкон. Прежде всего заметим, что пе существует сегмента 5 относительно С, для которого Г(Б)=О. Действительно, если бы такой сегмент Б существовал, то существовала бы и а-цепь этого сегмента, обе контактные вершины которой не принадлехсат одной грани.
Поэтому укладка такой цепи (и тем более сегмента 5) невозможна. Итак, могут представиться лишь следующие два случая. С л у ч а й 1. Для некоторого сегмента Я относительно С существует еднпствоппая допустимая грань Г. Пусть С' — укладка графа С, из которой путем удаления вершин и ребер можно получить граф 6. Б этой укладке сегмент Я находится в грани Г, так как только этой грани принадлежат все его контактные вершины. Это значит, что, помещая любую а-цепь Л ~н Б в грань Г, снова получим частичную укладку графа С. С л у ч а й 2.
~Г(Я) ~ ~ 2 для всякого сегмента Я относительно 6. Рассмотрим связную компоненту Н двудольпого (по лемме 41.2) графа Я(С), содерязащую пе монсе двух вершин. Эта компонента также является двудольпым графом, и в силу леммы 41.1 Г(Я)=(Гп Гг) для всякого Б ~н Н. Пусть С вЂ” укладка графа С, из которой путем удаления вершин и ребер можно получить граф 6. Так как все контактные вершины кшкдого сегмента принадлежат только граням Г~ и Гм то каждый из сегментов относительно 6 находится в одной из этих граней.
При этом сегменты, соответствующие вершинам каждой доли графа Я(С), пе конфликтуют. Поэтому в графе С' сегменты, соответствующие одзюй доле, находятся в грани Гп а сегменты, соответствующие вершинам другой доли,— в грани Гь Если теперь сегменты, находящиеся в Гп поменять местами с сегмептамн, находящимися в Гм то получим граф С", который также является укладкой графа 6. Это значит, что всякая сс-цепь любого сегмента Я ~я Н в любой плоской укладке графа С может быть рас- 180 положена и в Гс, и в Гз. Ипыми словами, помещая а-цепь Ьы Я в любую грань, допустимуго для сегмента Я, получаем частичную укладку графа 6. Если для некоторого соглгепта Я пет конфликтующих сегментов, т.
е. вершина ЯснЬ(С) является изолированной, то наше утверждение очевидно. '1 Замечание. Если граф 6 пе является циклом, то в процессе раооты алгоритма 7 встретится случай, когда Ркс. 41.3 ~Г(Я)! ~ 2, и поэтому существуют различные укладки графа С. На рис. 41.3 показаны две возможные укладки графа 6, изображенного па рис. 41.1.
Следствие 41.4. Если граф С плассарный, то алгоритм 7 строит его плоскую укладку. Следствие 41.5. Если в процессе работы алгоритма 7 встретится сегмент Я, для которого ссет допустимой грани, то граф С неп.саперный. Проиллюстрируем работу алгоритма 7 па примерах. Пример 1. Пусть граф С изображен па рис.
41.4. Уложим сначала цикл С=(1, 2, 3, 4, 1), который разбивает плоскость па две грани Гг и Гз. На рис. 41.5 изображены граф С = С и сегменты Яс, Яз, Яз относительно С с контактным вершинами, обведенными кружками. Так как Г(Яс)=(Гс, Гз) (с=1, 2, 3), то любую а-цепь произвольного сегмента можно укладывать в любую допустимую для пего грань. Поместим, например, и-цепь Ь = =(2, 5, 4) в Гг. Возникает аовьш граф С и его сегменты (рнс. 41 6). Прн етом Г(ог) = (1 з), 1 (Яз) = (Гс, 1 з), Г(Яз)=(Гг, Гз, Гз). Укладьгвасм цепь Е=(1, 5) в Гз (рис, 4!.7).
Тогда Г(Яс)=(Гс, Гз), Г(Яг)= (Гг, Гз). Далее, улолснм а-копь 1 =(2, 6, 4) сегмонта Яс в Гс (рис. 41.8). В результате имеем Г(Яс) = (Гз), Г(Яз) = = (Гг„Гз, Гз). Наконец, уложив ребро (6, 3) в Гз, а ребро 181 (2, 4) — например, в Гь получаем укладку графа С па плоскости (рис. 41.9).
Пример 2. Пусть 6 =Кзз (рис. 4110). Цикл б и согмонты относительно этого цикла изображепы на рис. 41.11. 11ри этом Г (5,) = (1" ь Гг) (1 = 1, 2, 3) . г л б 5 4 Рас. 41.9 Рис. 41.10 1 б б .. 1 Г1 Гг б зг ~. 5, Рис. 41.11 5 5, Рис. 41 12 Помеп1аем Я~ в грань Гг. Тогда Яг необходимо поместить в грань Г~ (рис. 41.12). Поскольку Г(Я~)= В, то Кзз— непланарпый граф. 5 42.
Характеристики непланарпых графов Приводимые ниже характеристики графов представляют ту илн иную меру пеялапарпости. Род графа. Мы уже знаом, что пленарные графы и только опи укладываются как па плоскости, так н па сфе- 133 ре. Возникает вопрос: можно лп уложить пеплапариый граф па какой-либо другой поверх«юстир Утвердптельпьш ответ па этот вопрос получаем сразу же, если нарисуем граф на плоскости и для каждого пе- ресечении двух робор, добавив к плоскости ручку, прове- дем одно ребро по ручке, а другое — под пей. На рис. 42.1 изображена укладка графа Кз па плоскости, к которой добавлена одна ручка, т.
е. построен «мост». Тем самым очевидно, что граф Кз (и Кзг) можно уложить па торе, т. е. па сферо с одной ручкои (рис. 42.2). Графы, которые нельзя уложить па плоскости, по моншо уложить на торе, называются тороидальными. На рис. 42.3 изобрая«епа укладка графа Кз,з на торе. Укладку тороидального графа на торе удобно изобра- зить с помощью прямоугольника, в котором отождествле- ны обе пары противоположных сторон. На рис. 42.4 — 42.7 изображены такио укладки торопдальпых графов Хм Кз,з, Ку, К4«соответственно. Определим теперь род 7(6) графа С как наименьшее число ручек, которые необходимо добавить к сфере, что- бы можно было граф 6 уложить на полученной таким образом поверхности.
Тем самым, поскольку графы Кг, Кг,з, Кп К4,«пепла- парпы, то 7 (Кз) = 7 (Кз,з) = 7 (Кр) = 7 (К««) = 1. Очевидно, что 1) 7(6)=0 тогда и только тогда, когда граф 6 пла- парпый; 2) 7(6) =1 тогда и только тогда, когда граф С тороидальный. Приведем без доказательств некоторые известные ре- зультаты о роде графа (см., например, [7], [28] ): 7(6)~] (т — Зя)/6+1[, п>3, если 6 — связный (и, т)-граф (здесь и далее ]х[ — наи- меньшее целое число » ~ х); если Вн Вз, ..., В, — система всех блоков графа 6, то 7(6) = Х у(В«)' 7(К„)=] (и — 3) (п — 4)/12[, и ~ 3; у(Кр ч) = ](р — 2) (д — 2)(4(, 7(0.)=1+ (и — 4)2" ', где (» — и-зрорпый куб. Число скрещиваний.
Числом скрея»иваиий сг(6) графа С называется наименьшее число перосеченпй, 184 Рис. 42,1 Рис. 42.3 / 2 и, иг Рис. 42.6 5 г Рис. 42.4 Рис. 42.2 и, и и„ и. иг и„ Рис. 42.5 иг из Рис. 42.1 получаемых при изображении графа на плоскости (понятие пересечения относится к поресечспию ровно двух ребер). Очевидно, что сг(С) = О тогда и только тогда, когда С вЂ” планарныи граф. Приведем здесь следующие известные оценки для числа скрещивании: сг (К„) ( — [ — ~ [ — ~ [ — ~ [ — 1, -' -Н[ — П-П вЂ” 3 причем при р ~ б и любом д сг(Кр ч) — [ — ~ [ — ~ [ — ~ [ — ~. 'Толщина графа.
При изготовлении печатных схем соединительные провода наносятся на одну сторону пепроводящей пластинки, Поскольку печатные проводники не изолированы, то они не должны пересекаться. Поэтому важно знать, является ли планарным граф, в котором роль вершин играют приборы, а ребрами являются соединения. Если такой граф неплапарный, то возникает вопрос: какое наименьшее число пластинок необходимо для комплектования всей схемы (сети) 7 Таким образом, мы приходим к понятию толщины графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
