В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU), страница 4

Тогда если нсе кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа С. Теорема 3.1. Каждый конечный граф' С можно реалазоваьпь в трехмерном евклидовом пространстве ~без пересечения ребер). Доказательство. Возьмем в пространстве любую прямую 1 и разместим на ней все вершины графа С. Пусть в С имеется о ребер.

Проведем о полуплоскостей через 7 так, чтобы прямая 7 была их общим ребром (типа тетрадки). После этого каждое ребро графа С можно изобразить линией в своей полуплоскости и они, очевидно, не будут пересекаться. Определение. Граф называется планарным, если существует его иланарная реализация, то есть геометрическая реализация на плоскости (без пересечения ребер). Если имеется планарная реализация графа на плоскости и мы разрежем плоскость по всем линиям этой планарной реализации, то плоскость распадется на части, которые называются гранями этой иланарной реализации (одна из граней бесконечна, она называется внешней гранью). Теорема 3.2 (формула Эйлера.) Для любой планарной реализации связного планарного графа С = (1',.Е) с р вершинами, д ребрами и г гранями выполняется равенство: р — д+ г = 2. Доказательство.

При фиксированном р индукцией по а. Так как С связный граф, то ор — 1 ио следствию из леммы 1А. а) Базис индукции: д = р — 1. Так как С связный и о = р — 1, то по теореме 2.3 С дерево, то есть в С нет циклов. Тогда г = 1. Отсюда р — д + г = р — (р — 1) + 1 = 2. б) Пусть для р — 1д < оо теорема справедлива.

Докажем, что для д = оо она тоже справедлива. Пусть б' связный граф с р вершинами и оо ребрами и пусть в его нланарной реализации к граней. Так как до > р — 1, то 6 — не дерево. Следовагельно, в 6 есть цикл. Пусть ребро е входит в цикл. Тогда к нему с двух сторон примыкают разные грани. удалим ребро е из С. Тогда две грани сольются в одну, а полученный граф С~ но лемме 1.3 останется связным. При этом получится нланарная реализация графа С1 с р вершинами, до — 1 ребрами и г — 1 гранями. Так как до — 1 ( оо, то, но предположению индукции., для С1 справедлива формула Эйлера, то есть р — (до — 1) + (г — 1) = 2, откуда р — до + г = 2. Что и требовалось доказать.

Следствие 1. Формула Эйлера справедлива и для геометпрической реилпзаиии связных графов ни сфере. Доказатпельскпво. Пусть связный граф С с р вершинами и о ребрами реализован на сфере Я так, что число граней равно г. Пусть точка А на сфере не лежит на линиях этой геометрической реализации. Пусть Р некоторая плоскость. Поставим сферу Я на. Р так, чтобы точка А была самой удаленной от плоскости.

Спроектируем 5 на Р центральным проектированием с центром в А. Тогда на плоскости Р мы получим геометрическую реализацикэ связного графа с р вершинами и д ребрами, причем число граней оудет равно г (грань на сфере, содержащая А, отображается во внешнюю грань на плоскости). По теореме 3.2 получаем р — о + к = 2. Следствие 2. Для любого выпуклого многогранники справедливо равенство р — а+ с = 2, где р --- тело веригин, д ---- число ребер, г--- число гриней. Доказап~ельство.

Пусть выпуклый многогранник ЛХ имеет р вершин, д ребер и г граней. Пусть О ----- внутренняя точка многогранника М. Рассмотрим сферу Я с ценгром н О настолько большого радиуса, чтобы ЛХ целиком лежал внутри Я. Рассмотрим центральное проектирование с центром в точке О, и спроектируем вершины и ребра ЛХ на Я. Тогда на Я мы получим геометрическую реализацию некоторого связного графа с р вершинами, д ребрами и г гранями. Отсюда р †у+с.

Формула Эйлера позволяет доказать неиланарность некоторых графов. Определение. Графом К; назынается граф с 5 вершинами, в котором каждая пара вершин соединена ребром (см. рис. 3.1). Теорема 3.3. Гриф К,-, не плинирен. 17 Доказательсп)ао. Допустим, чт() для графа Х).3 существует»ланарная реализация. Так как граф Х),3 снязен, то для этой планарной реализсгции снраведлиВа форму)»а Зй'(ера )) — !1 + ! = 2. Поскольку в графе К-, имеем )) = 5 и () = 10, то число всех Граней должно ранняаься г = 2 — р+ (! = !. Пу(.ть грани занумерованы 1„2,..., г и пусть нри обходе (-ой грани но периметру «но ее краи)) проходится д; ребер.

Так кнк нри этом каждое ребро проходится дважды «оно явля(тся сторОной д;!я двух Граней)„то 2,". (1! — — 2ч = 20. Но В каждой грагни не менее 3 сторон. Поэтому ();3 для в( ех ). Оп:к)да ~,' ! (Х;Зг = 21. ПО.;(ус(с)еы 2021 — нро)иноречие. Знсчс(ит,Чля Гра(~)сч Лн не ( у(цесгнует нланарной реализации. Рис. 3.1. Определение. Графом Ь;»,» называется граф с 6 вершинами а»,аа,ав, 6»,63,63„н котором каждая не1ннина а; соединена ребром с каждой вершиной 6. и нет других реоер «см. рис. 3.1). С !'РафОМ Х13 3 свЯзана слеДУК)щая изве('тная заДс(чс! О тР('.х ДОмах и трех колодцах. Есть 3 дома и 3 колодца, но хозяева домов в боль- шОЙ Вражде.

МОжнО ли так нро.:(ежи)ь дОрожки От каждО)О ДОма к каждому кОЛОД»»у, чТООЫ ОНИ НИГДЕ нв Н('.ресЕКа)»исЬ.' О'"!'ВЕ'Г На Э'!'О'!' !»ОПРО(. 'ДНЕ'!' С)»ЕДУК)»псчя 1()ОР(.'Ма. Теорема 3.4. Х"Х)аф К» 3 не планарен. Донона)т)ег)ьска((о. Допус! Им, ч го дз!.)! Г1)афа Х).3 3 суще(Ггнует нланарная реализация. Так как граф Х)с3,» связен, то для этой нланарной РЕНЛИЗНЦИИ СНРссанЕДЛ))всч фОРК(У)»а Эй)»ЕРсз Х) — (Х + ) = 2. П(Х.КО,'!ЬКУ В графе .Е» 3 имеем р = б и о = 9, то *нигло всех граней должно равняться г = 2 — р+ () = 5. Так же„как в доказательстве предыдущей теоремы„ получаем, ((О Я' ! ()! = 2(х = 18. где д; — число сторон в (-ой )рани. Но в графе Х~3.» нет циклов длины 3.

Поэтому в каждой грани не менее 4 сторон. С!(едовагез»ы(о, о.;4 для всех !. Отсгода Я' ! (!.;4г = 20. Получаем 1820 — нро:! ИВО1гечи(". Значит дз»я ! р')~)а Х13 3 не с)г(цес'!'Вует нланарной реализации. Граница л)ОбОЙ Грани яв!яе1ся нутом в Гра(1)е„"Гак. Нги)ример, границей внъ")ренней Грани на рис. 3.2 является нгггь «указаны голько вершины): 1.2,4„5,4„6,4,2,3,1. Пусть длина границы (-ой грани «число »3 ребер) равна»!.; ~для грани на рис. 3.2»! = 9). 2 Рис. 3.2. Лемма 3.1.

Для любой геомегприиеской реализаци!! на плоскости связного плаиарного графа с»! ребрами выполняе)Г)ся равенство: Х;в =2Ч, где суммирование ведется по всем граням ~«1клн)ч»)я виси«июю грань). ДоказупъельсРпво. Раве1к"ГВО сг1еду«ГГ из ТОГО, что у каждО1'О р»"- бра две стороны и прн суммировании»!1 каждое ребро учитывается дважды: лино Оно в)«»)ди1 В 1ран11н11 !1ву)«соседник Гран«)Й, либо оно дяаждЫ уч)ггыва»ГГ»„'я В ОднОЙ Грани. Теорема 3.5. Если в связном планариом граф»; б = ~Ъ', Е) с р вери)инами и !! ребрами иет циклов длины меньи)е !1: фЗ,), то г — ~(р— ь Дока гаГГ!ельсгй»!о.

Так как ИО ус-:1ОВию !»!Й для Всея ~~ „"1'О из леммы 3.1 получаем 2дЬ и ! ~~. Из формулы Эйлера х = 2 — р +»!. Отсюда 2 — р+ дф. Далее ф — 2)ф~р — 2) и д~~-,;~р — 2). Следствие 1. Для любого связного планарного графа С = (1'„Е) без пегпель и краг»!иьин: ребер с р вери«инами и о ребрами справедливо неравенсп)во; ЧМР— 2). Указ»!Иие. Б те01)еме 3.5 можно Взять й = 3. Следствие 2. Для любо~о плаиариого графа С = ~1:,Е) без петель и кратных ребер с р»!ер!ш1)нами, »! ребрами и !ц связиь»ми комп»)и»гиг»!»)ми справедливо иеравеист»1в»)1 Яр — 2гп).

Доказагпельс)пво. Пус Гь в 1-ой связной 1, 2„..., т) р„вершин и»1; р«;бер. Тогда в ней по следствию 1 д,З~р; — 2). Суммируя все чти неравенства„получаем 1~3~р — 21»1). Следствие 3. 8 любом плаиориом графа С = ~1, Е) без петель и крап)ных ребер есгпь веригина степени ие более,7. Доказательство. Пусть С вЂ” планарный граф с р вершинами и »! ребрами. То)да дЗ~р — 2) < Зр. Пм«:ть 4„„.)! — минимальная степень вершин В С. То)да»1 учетом теоремы 1.1 почучаем бр > 2!1 = ~', »1е~ г»1к1 1=! 19 Отсюда д„„.„( б, то есть 4,„;„5. Если ребро графа изображено в виде линии, то можно на ней поставить точку и считнгь ее новой вершиной степени 2. Формально эта операция определяется следующим образом.

Определение. Пусть С любой граф и (а,о) его ребро. Операцией подразделенил ребра (а,6) называется удаление из графа С ребра (а,6), добавление новой вершины с и добавление двух новых ребер (а,с) и (с,6). Определение. Граф С» называется подразделением графа С, если С» может быть получен из С несколькими подразделениями ребер. Определение. Графы С» и С2 называются гомеоморфньсми, если существуют их подразделения, которые изоморфны. Су»цествует следующий критерий планарности. Теорема 3.6 (Понтрягина-Куратовского). Для того, нтобсы граф С был планарнсым, необходимо и достаточно, чтобы, он не содержал ни одного подгрофа, гомеоморфного графам К;, или Кв в.

До»сазательство. 1) Необходимость. Пусгь С планарный. Допустим, что он содержит подграф С~, гомеоморфный графу К; или Кзв. Рассмотрим планарную реализа»»ию графа С. Удалив лишние вершины и ребра, мы получим планарную реализацию подграфа С». Но С» геометрически --- это граф Х~.;, или Х~з з с точками на ребрах. Если проигнорировать эти точки. то мы получим планарную реализацию графа Кв или К~ з. Но это невозможно по теоремам 3.3 и 3.4. 2) Достаточность доказывается тяжело, и здесь мы это доказательство опустим.