В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 28
Текст из файла (страница 28)
363 имеют общих точек, кроме инцидептной им обоим вершины. Приморы плоских графов даны на рис. 36.1. Любой граф, нзоморфный плоскому графу, будем называть плапарнылс Граф Ко изображенный на рнс. 36.2, является планарным, так как о* изоморфен графам на 150 рис. 36.1, б, в. На том же основании граф на рис. 36.3,а планарен, поскольку графы, представленные на рис.
36.3, а, б, изоморфны. Очевидны следующие утверждения; 1) всякий подграф планарного графа планарен; 2) граф планарен тогда и только тогда, когда каждая его связная компонента — планарный граф. О планарных графах говорят, что они укладываются на плоскости (имеют плоскую укладку). В дальнейшем будут рассматриваться укладки графов не только па Рис.
36.3 Рис. 36.2 плоскости, но и на других поверхностях н в пространстве. Поэтому дадим определение укладки графа в произвольное пространство. Прежде всего введем понятие жордановой кривой, под которой будем понимать непрерывную спрямляемую линию, не имеющую самопересечений. Будем говорить, что граф С укладывается в пространство б, если существует такое отображение вершин н ребер графа С соответственно в точки н и.ордановы кривые этого пространства, что различным вершинам соответствуют различные точки, а кривые, соответствующие различнь|м ребрам, пересекаются только в ппцпдептных этим ребрам вершинах. Изображенньш таким образом граф называется укладкой графа С в пространство 1. Теорема 36.1. Каждый граф укладывается в трехмерное пространство Ег. с- Все вершины графа С помещаем в различные точки оси ОХ.
Из пучка плоскостей, проходящих через эту ось, выоерем )ЕС) различных плоскостей. Далее, каждое ребро ио ~ ЕС изображаем в соответствующой плоскости полуокружностью, проходящей через вер;пины и и о. Понятно, что в результате получаем укладку графа С в Е', так кзк все ребра лежат в разных плоскостях и потому не пересекаются во внутренних точках.
< Теор ем а 36.2. Граф укладывается на сфере тогда и только тогда, когда он планарен. 151 С для доказательства этой теоремы достаточно рассмотреть стереографическую проекцию (рис. 36.4). Пусть граф С уложен на сфере. Проведем плоскость Ч, касательную к сфере, так, чтобы северный полюс Л' (точка, диаметрально противоположная точке касания) не лежал на ребре и не совпадал с вершиной графа С. Теперь рассмотрим граф С, полученный стереографической проекцией графа С из точки Л на плоскость (з.
Поскольку существует биективное соответствие между точками сферы, отличными от Л', и их стереографнческимн проекциямн, то граф С' плоский и изоморфен графу С. Следовательно, С вЂ” планарный граф. Обратное утверждение доказывается аналогично с учетом установленной биекции. 0 Определения плоского и планарного графов, так же как н теоремы 36Л, 36.2 и многие другие утверждения Ркс. 36.5 Гяз. 36.4 этой главы, сохраняются и применительно к мульти- и псевдографам. Следующая классическая головоломка наводит на мысль, что существуют не только планарные графы.
Задача о трех домах и трех колодцах. Имеются три дома 1, 2, 3 и трп колодца 4, 5, 6 (рис. 36.5). Каждый хозяин пользуется любыъз из трех колодцев. В некоторый момент обитатели домов решили проложить дорожки до колодцев так, чтобы исключить встречи на дорожках, т. е. чтобы дорожки не пересекались. Возникает вопрос: возмоясно ли зто, т. е. возможно ли построить плоскую укладку графа Кз,з? Все попытки нарисовать девять непересекающихся дорожек, соединяющих дома с колодцами, заканчиваются неудачей. При этом легко нарисовать восемь непересекающихся дорожек, но девятая обязательно пересечет хотя бы одну из этих восьми. Оказывается, что неудачи не случайны. Ниже будет доказано, что граф Кзз не укладывается на плоскости, т. е.
не является планарным. 152 На самом деле не только существуют непланарные графы, но верно утверждение, приводимое нил~е без доказательства (см. [21[). Утверждение 36.3. Почти все графы не являются планарными. 3 37. Грани плоского графа. Формула Эйлера Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара которых может быть соединена жордановой кривой, ке пересекающей ребра графа. Тем самым калгдая точка плоскости принадлежит хотя бы одной грани плоского графа. Граниией грани будем считать множество вершин и ребер, принадлежащих этой грани.
На рис. 37.1 изображен граф с четырьмя гранями. Отметим, что всякий плоский граф имеет одну, и притом единственную, неограниченную Рве. 37.1 грань (на рис. 37.1 грань 4). Такая грань называется внетиней, а остальные грани— внутренними, Легко видеть, что всякую внутреншою грань плоското графа С можно преобразовать во внешнюю с помощью стереографической проекции. Для этого, воспользовавшись теоремой 36.1, уложим граф 6 на сфере так, чтобы северный полюс оказался внутри выбранной грани.
Далее рассмотрим стереотрафическую проекцию 6' графа 6 на плоскость, касающуюся сферы в южном полюсе, т. е. в точке, диаметрально противоположной северному полгосу. Очевидно, что выбранная грань графа 6 станет при этом внешней в 6', а внешняя грань графа 6 — внутренней гранью графа 6', который изоморфен графу 6. На рпс. 37.2 представлен граф, получающийся нз графа, изображенного на рис. 37.1, путем такого преобразования. При этом внутренняя грань 1 стала внешнеп. Понятие грани естественным образом распространяется на псевдо- и мультиграфы (рис. 37.3). Сформулируем несколько очевидных свойств плоских укладок графа, которые в дальнейшем будем неоднократно использовать, порой и не ссылаясь на них. 153 С в о й с т в о 1.
Всякий планарный граф допускает такую плоскую укладку, в которой любая выбранная вершина (ребро) графа будет принадлежать внешней грани Свойство 2. Пусть граф С состоит из двух связных компонент С~ и Сг, являющихся плоскими графами, г 3 Рис. 37.2 Рис. 37.3 и произвольным образом выбраны вершины о~ «и т'С1 и ог ан УС», Тогда граф С, полученный из С слиянием вершин о1 и ог в вершину и, имеет плоскую укладку. При этом вершина и является точкой сочленения графа С (рис. 37.4). Аналогично можно «склеивать» два плоских графа и по ребру. Свойство 3.
Всякие две вершины, принадлежащие границе некоторой грани плоского графа, можно соеди- в, Рис. 37.4 нить простой цепью произвольной длины так, что выбранная грань разобьется на две грани. Отметим, что зто свойство является следствием известной теоремы Жордана о кривой. Свойство 4. Для любого плоского графа каждая точка плоскости, не лежащая на ребре, входит только в одну грань, а каждая точка ребра, не являющаяся вершиной, входит только в одну грань, если это ребро является мостом, и точно в две грани, если оно не мост. Далее будем пользоваться следующими обозначения- 154 ми: и, т, 7 — соответственно число вершин, ребер и граней плоского графа. Теорема Эйлера (1758 г.). Для всякого связного плоского графа верно равенство и — т+ 7' 2. Равенство (1) называется формулой Эйлера. »> Пусть 6 — связный плоский и-вершинный граф.
Рассмотрим некоторый остов Т этого графа. Очевидно, что дерево Т имеет одну грань (внешнюю) и и вершин. В то же время известно (см. теорему 13.1), что число ребер дерева Т равно и — 1. Поэтому для графа Т формула (1) верна. Теперь будем поочередно добавлять к Т недостающие ребра графа 6.
При этом на каждом шаге число вершин, естественно, не меняется, а число ребер и число граней увеличивается на единицу на основании свойства 3. Следовательно, формула (1) будет верна для всякого графа, получающегося в результате таких операций (шагов), а поэтому она верна и для графа 6, которым заканчивается вся эта процедура. < Из теоремы Эйлера вытекает ряд интересных следствий. Прежде всего, рассмотрим в трехмерном пространстве выпуклый многогранник с и вершинами, т ребрами и 1 гранями. Очевидно, что спроектирован этот многогранник на описанную около него сферу, далее уложив его так, чтобы северный полюс находился внутри одной из граней, и произведя затем стереографическую проекцию, получим связный плоский граф.
Поэтому справедливо Следствие 37. 1. У всякого выпуклого многогранника сумма числа вершин и и числа граней / бег числа ребер т равна двум: и+ ~ — т = 2. Доказательство именно этой формулы и было впервые опубликовано Л. Эйлером в 1758 г. в «Записках Петербургской академии наук». Следствие 37,2. Число граней любой плоской укладки связного планарного (и, тп)-графа постоянно и равно т — и+ 2. Другими словами, число 1 является инвариантом планарного (и, т)-графа, т. е.
не зависит от способа укладки этого графа на плоскости. Следствие 37 3. Для связного планарпого (и, т)- графа т < Зп — 6 при и ~ 3. < Не теряя общности, будем считать, что 6— плоский граф. Прежде всего заметим, что всякое ребро 155 плоского графа либо разделяет две различные грани, либо является мостом (см. свойство 4). Поскольку С вЂ” граф без петель п кратных ребер, то всякая грань ограничена по крайней мере тремя ребрами (исключенпе составляет лишь случай, когда С вЂ” дерево с тремя вершинами, но для такого графа неравенство 3п — 6 ~ т справедливо). Поэтому число 3/ является оценкой снизу удвоеяного числа ребер графа С, т.
е. 37~ 2т. Отсюда, учитывая, что по формуле Эйлера 1 = т — и+ 2, приходим к требуемому неравенству. Э Из этого следствия сразу же получаем Утвержденпе 37.4. Граф Кэ нс планарсн, Э Действительно, для графа Кз п=5, т= 10. Поэтому неравенство 3п — 6 > т превращается в неверное: 9 ~ 10, т. е. граф Кз пе может быть планарным. < Утверждение 37.5.
Граф Кгг нс планарен. > Для рассматриваемого графа и = 6, т = 9. Поэтому, если бы он был планарпым, то для любой его плоской укладки выполнялось бы 1' 5 согласно следствию 37.2. В то же время всякая грань двудольного графа Кг,з должна быть ограничена по меньшей мере четырьмя ребрами. Следовательно, 2т =- 47, т. е. 18 ~ 20. Полученное противоречие доказывает утверягдекне 37.5. О Мы особо останавливаемся на графах Кз и Кз 3 поскольку, как мы увидим в з 39, эти графы являются милпмальпымя пеплапарпыми графами и играют важнузо роль во многих критериях планарпости. Из теоретнл Эйлера вытекает также Следствие 37 6. Если в связном плоском (и, т)- графе граница каждой грани является т-циклом, т ~ 3, то т (т — 2) = т(п — 2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
