WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
PLANAR GRAPHS ПЛОСКИЕ ГРАФЫ A. Yu. OL’SHANSKII..

‚ „‰‡‚ ‚ The paper is compiled... ‚‡ from several old and new corollaries of the visually indubitable statement: A Электросхемы и схемы транспортных коммуниclosed curve without selfкаций, чертежи и географические карты, структурintersections, which is ные формулы молекул и генеалогические деревья доставляют многочисленные примеры графов, в коsituated on the plane, торых выделенные точки соединены линиями, приsplits it on two domains званными сообщить о важных связях или другой (interior domain and exteполезной информации. В настоящей статье, ориентированной в основном на старшеклассников, rior one). The exposition проявляющих интерес к математике, речь идет о is fully elementary.

свойствах плоских графов, не меняющихся при непрерывных преобразованиях, иначе говоря, об их топологических свойствах.

‰ ‡ fl‚flОтносящиеся к XVIII и XIX векам основные fl ‡ факты плоской топологии, такие, как теоремы Эйле ‚ ‰‚fl ‡ра и Жордана, весьма наглядны. Тем неожиданнее оказываются новые интересные наблюдения, и сре„fl‰ ‚‰„ ди них красивая теорема Ан.А. Клячко [1] и прfl: ‚fl‡fl ‡стая, но изящная лемма Дж. Столлингса [2] (см. ни‡fl ‚‡fl · ‡же разделы 6 и 7), которые были опубликованы соответственно в 1993 и 1987 годах в связи с ‡ проблемами комбинаторной теории групп.

‡·‚‡ ‡ ‰‚ C инженерной точки зрения представляет инте·‡: ‚ рес вопрос о возможности плоского соединения ‚.

микросхем. Такая задача возникает в радиоэлектронике при проектировании печатных плат. Можно ‚ ‡.

ли, к примеру, попарно соединить пять точек плоскости линиями без взаимных пересечений Так, на рис. 1, а все пары точек, кроме одной, соединены зелеными линиями, а одна пара – красной. Она, к сожалению, пересекается с одной зеленой линией.

А можно ли было избежать пересечений при ином способе плоского соединения Имеет ли решение старинная задача о трех колодцах: проложить от “дворов” 1, 2, 3 (хозяева которых не ладят между собой) по три тропинки к каждому из “колодцев” 4, 5, 6 (рис. 1, б), которые бы нигде не пересекались между собой Для ответа на эти и другие вопросы уточним сначала, какими свойствами обладает плоская линия.

аб 1 K5 K3, Рис. 1.

..

© ‡.., 1. Теорема Жордана утверждает, что это свойство окружности распространяется на любую плоскую Окружность, граница квадрата или путь 1 – 4 – простую замкнутую кривую C. А именно: множест2 – 6 – 3 – 5 – 1 на рис. 1, б отвечают нашему предво всех точек плоскости, не лежащих на C, разбиваставлению о простой замкнутой кривой на плоскоется на две области: внутреннюю (или ограниченную) сти как о линии, которую можно нарисовать, не отE1 и внешнюю (неограниченную) E2, так что любые рывая карандаша от бумаги, без самопересечений и две точки из одной области можно соединить между с возвращением в исходную точку. Если же конечсобой дугой, целиком лежащей в этой же области, но ная точка не совпадает с начальной, то полученную никакую точку из E1 нельзя соединить дугой с точкой линию назовем дугой.

из E2, не пересекая кривую C.

По существу, такого представления о замкнутой Эта теорема дополняется теоремой Шенфлиса:

кривой и дуге достаточно для понимания дальнейвсякая точка Z E1 (Z E2) может быть соединена шего изложения. Но для читателя, не удовлетворенсо всякой точкой Y C c помощью некоторой дуги, все ного наглядным пояснением, мы приводим в этом точки которой, кроме Y, лежат в E1 (соответственразделе формальное определение. Оно обобщает но в E2).

простое наблюдение: граница квадрата может быть Строгое доказательство теорем Жордана и Шенполучена из описанной окружности непрерывным флиса оказывается неожиданно трудным и часто не преобразованием (например, проецированием кажприводится во вводных топологических курсах.

дой ее точки на ближайшую сторону квадрата).

Точно так же поступим сейчас и мы. Отсутствие доВ общем случае рассматривается произвольное казательств частично оправдывается наглядностью отображение f окружности O единичного радиуса утверждений теорем. Кроме того, для наших целей на некоторое подмножество C плоскости со свойвполне достаточно было бы рассматривать не проствами:

извольные кривые, а только ломаные линии, со1) f взаимно однозначно, то есть у каждой точки ставленные из конечного числа звеньев-отрезков X окружности O имеется один образ Y = f(X) в C и, (но даже для них теорема Жордана нетривиальна!).

наоборот, у каждой точки Y C имеется ровно один прообраз X O;

3. 2) отображение f (равномерно) непрерывно. Это Оговоримся сразу, что все графы далее будут козначит, что для любого, сколь угодно малого полонечными. Под графом на плоскости понимается жительного числа можно подобрать число > 0 танекоторое конечное множество вершин V = {, …, кое, что для любых точек X1, X2 O, находящихся на } (выделенных точек плоскости) вместе с некотоk расстоянии менее, расстояние между их образами рым конечным множеством E = {e1, …, el} соединяY1 = f(X1) и Y2 = f(X2) меньше.

ющих их ребер. При этом ребро, соединяющее разЕсли отображение f: O C со свойствами 1) и личные вершины, – это дуга, а ребро с началом и 2) существует, то C называется простой замкнутой концом в одной вершине (называемое также петкривой. Когда переменная точка X обходит окруж- лей) – это простая замкнутая кривая. Требуется, ность O, соответствующая точка Y = f(X) обходит чтобы каждое ребро не имело общих точек, отличкривую C. ных от его начала или конца, с другими ребрами.

Определение (плоской) дуги d отличается от Граф на рис. 2, а не является связным, потому приведенного только тем, что вместо окружности O что связным называется граф, в котором любые две выбирается стандартный отрезок [0; 1]. При изме- вершины можно соединить непрерывным путем, нении точки X [0; 1] от 0 до 1 ее образ Y = f(X) составленным из нескольких ребер графа. Граф 2, а “проходит” дугу d. Образы чисел 0 и 1 являются распадается на два связных графа и. Под плос1 концами дуги d. ким графом мы понимаем в дальнейшем связный граф на плоскости, имеющий хотя бы одно ребро.



2.

Простая замкнутая кривая (или ломаная) линия, составленная из ребер плоского графа, разбивает Стандартная единичная окружность разбивает евклидову плоскость на две компоненты: внутрен- плоскость в соответствии с теоремой Жордана на две области, а весь граф разбивает ее на несколько обнюю, с условием x2 + y2 < 1 для лежащих в ней точек ластей или граней графа. “Красный” граф на рис. 2, б (x, y) и внешнюю, с условием x2 + y2 > 1. Понятно, состоит из пяти внутренних граней (розового цвета) что точку (x1, y1) из внутренней компоненты нельзя и одной внешней (неограниченной) области плоскосоединить дугой с точкой (x2, y2) из внешней компости с “внутренней” границей 1 – 2 – 3 – 4 – 1.

ненты, не пересекая окружности O, поскольку непрерывная функция расстояния переменной точки Теоремы Жордана и Шенфлиса позволяют для дуги (x, y) от начала координат, принимая значения каждого плоского графа построить двойственный ему плоский граф следующим образом. Выберем x2 + y2 < 1 и x2 + y2 > 1, должна принять в какой1 1 2 внутри каждой грани графа по одной точке – верто промежуточной точке (x, y) значение x2 + y2 = 1. шине графа (a, b, c, x, y, z на рис. 2, б). Если e –, ‹11, аб в Оказывается, формула Эйлера (1) справедлива для произвольного плоского графа, а поэтому верe 2 F1 на и для многогранников ввиду возможности их укea o1 = a o ладки на плоскости с превращением одной из граO b z Г1 ней в неограниченную область. Доказательство x y Г Fформулы Эйлера легко проводится с помощью инc 1 дукции по числу ребер Nр плоского графа. В слуo2 = b Гчае Nр = 1 есть две возможности: единственное ребро является петлей или простой дугой. В первом случае имеется одна вершина и по теореме Жордана Рис. 2.

две грани, а во втором случае (Nв, Nр, Nг) = (2, 1, 1).

В обоих случаях соотношение (1), очевидно, верно.

смежное ребро двух каких-либо граней F1, F2 графа с выделенными внутри них вершинами o1, o2, то При Nр > 1 опять-таки рассмотрим два случая.

выберем на е одну неконцевую точку o и проведем 1. В графе имеется вершина o степени 1, то есть внутри граней F1, F2 дуги o1 – o и o2 – o соответстпринадлежащая только одному ребру e, которое к венно. (На рис. 2, в представлен фрагмент графа 2, б, тому же не является петлей (как вершина в графе в котором такое построение показано только для на рис. 2, а). В таком случае граф ', полученный двух граней F1 и F2 с вершинами o1 = a и o2 = b внутри удалением из ребра e вместе с одной его вершиной их.) Дуга o1 – o – o2, пересекающая ребро е, объявo, является связным, причем для него ляется ребром e0 графа, соединяющим вершины o1 и o2 в.

N' = Nв – 1, N' = Nр – 1, N' = Nг. (2) в р г На рис. 2, б двойственный граф для красного графа нарисован синим цветом. По определению, Поскольку N' = Nр – 1, можно считать формулу р число вершин в графе равно числу граней в Г, Эйлера уже доказанной для ': N' – N' + N' = 2.

в р г число ребер в такое же, как и в графе ( почему), Подстановка равенств (2) в это соотношение дает а число граней графа равно числу вершин графа.

формулу Эйлера (1) для.

Легко представить, как плоский граф может 2. Пройдя любое ребро e = e1, можно непрерывбыть уложен на сфере. Наоборот, каждый граф на но продолжить движение по какому-то ребру e2.

сфере имеет плоскую реализацию: нужно объявить Тогда неизбежно повторение ранее пройденных ресеверным полюсом точку o внутри некоторой грани бер после достаточно большого числа таких продоли спроецировать сферический граф из o на плосжений ввиду конечности числа ребер в. Понятно, кость, касающуюся южного полюса. В частности, что в этом случае можно составить простой замкнуесли сначала “раздуть” грани куба до сферы (это тый путь из нескольких последовательных ребер e1, можно сделать, спроецировав из центра куба все его e2, …, ek графа (возможно, k = 1). Из теорем Жорребра на описанную сферу), а потом построить для дана и Шенфлиса следует – и этот факт наглядно полученного сферического графа описанную выше очевиден, – что удаление из ребра e (без удаления стереографическую проекцию, то в результате возего начальной и конечной вершин) уменьшает чисникнет красный граф на рис. 2, б. Одной из граней ло граней на 1, то есть в полученном графе ' куба (над которой находится северный полюс) соответствует неограниченная грань плоского графа 2, б.

N' = Nв, N' = Nр – 1, N' = Nг – 1.

Аналогично вершины, ребра и грани любого выпук- в р г лого многогранника превращаются в вершины, реТеперь индуктивное рассуждение завершается, бра и грани некоторого плоского графа. (Проверькак и в первом случае.

те, что при такой укладке на плоскости октаэдр двойствен кубу.) 5.

4.

Применим формулу Эйлера к сферическим или плоским графам, у которых при обходе каждой грани Обозначим Nв, Nр и Nг соответственно числа (в том числе и внешней в плоском случае) проходитвершин, ребер и граней некоторого многогранника ся не менее n ребер для данного n > 2. Считая тогда P. Например, для куба (Nв, Nр, Nг) = (8, 12, 6), для при обходе всех граней общее число ребер, получим октаэдра эта тройка равна (6, 12, 8), для тетраэдра величину, не меньшую nNг. Ввиду двойного учета (4, 6, 4), для додекаэдра (рис. 3, а) (20, 30, 12), для каждого ребра при таком счете получаем неравенство n-угольной пирамиды (n + 1, 2n, n + 1), а для n-угольной призмы (2n, 3n, n + 2). Каждый раз 2Nр nNг.





Nв - Nр + Nг = 2. (1) Прибавим теперь к обеим его частям соответственЧто это: любопытное совпадение или проявление но левую и правую части равенства (1), умноженные общей закономерности предварительно на n. Получим..

n(Nв – 2) Это рассуждение заодно доказывает, что не суNр -----------------------. (3) ществует выпуклых многогранников, у которых n – каждая грань имеет не менее шести сторон. По этой Неравенство (3) полезно для решения вопроса о же причине футбольный мяч сшивается из шести- и возможности укладки на плоскости или сфере “абпятиугольных лоскутов.

страктных” графов. (Под произвольным графом Читателю предлагается самостоятельно вывести понимается любая схема соединения конечного неравенства для чисел вершин и ребер мяча, сшитомножества вершин посредством ребер, имеющих го из k пятиугольных и l шестиугольных лоскутов, и общие точки только в вершинах, которая необязадоказать, что k 12. (Указание: число ребер равно тельно располагается на плоскости.) --(5k + 6l), а число вершин не превосходит Легко объяснить, например, что граф K5 (рис. 1, а) нельзя уложить на плоскости без самопересечений.

В самом деле, в нем нет петель и кратных ребер (то --(5k + 6l).) Из 12 пятиугольных лоскутов мяч можесть двух разных ребер с одинаковыми концами), а но было бы сшить так же, как додекаэдр составлен значит, каждая грань этого графа, расположенного из 12 пятиугольников (рис. 3, а), но такой мяч был на плоскости, имела бы не менее трех граничных бы недостаточно круглым. Настоящий футбольный ребер. Но формула (3) при n = 3 не выполнена для мяч сшит из 12 пятиугольных и 20 шестиугольных графа K5, так как он имеет 5 вершин и 10 ребер.

лоскутов вдоль 90 ребер (рис. 3, б). Найдите, пожаПринимая, что граф K3, 3 (рис. 1, б) допускает луйста, число его вершин по формуле Эйлера! плоскую реализацию, можно применить формулу аб (3) при n = 4, так как в этом графе нет и замкнутых путей с тремя ребрами. (К примеру, выйдя с какоголибо “двора” и пройдя три “тропинки”, мы непременно окажемся у какого-то “колодца”.) Опять получаем противоречие с (3), ибо в этом случае Nв = 6, a Nр = 9.

Непланарен (то есть не укладывается на плоскости), очевидно, и граф, содержащий в себе меньший граф (подграф), который непланарен. НеплаРис. 3.

нарны, конечно, графы, гомеоморфные графам K5 и K3, 3, то есть такие, которые получаются из них при 6. разбиении каждого ребра e на несколько ребер поЛемма Столлингса утверждает, что если в некосредством расположения на e нескольких дополнитором городе по каждой улице между двумя соседтельных вершин. Знаменитая теорема Понтрягина – ними перекрестками разрешается двигаться только Куратовского утверждает, что других препятствий в одном направлении, то обязательно найдется для планарности нет:

квартал, вокруг которого можно объехать.

Граф планарен тогда и только тогда, когда он не Математическая формализация задачи такова.

содержит подграфов, гомеоморфных графу K5 или граПусть – плоский граф, который ориентирован, то фу K3, 3.

есть каждому ребру приписано определенное наВыше была доказана необходимость условия правление, что наглядно изображается стрелкой (и этой теоремы. Доказательство достаточности знамы не будем здесь вдаваться по этому поводу в дальчительно труднее (см. [3]).

нейшие формальности). Назовем такой граф праЕще одно применение формула (3) находит при вильным, если в нем нет вершин, из которых все ребn = 6. Как известно, пчелы конструируют свои соты ра только выходят, – “источников” и нет вершин, в так, что каждая их ячейка (внутренняя грань) явля- которые все ребра только входят, – “стоков”. (Поется шестиугольной. А могут ли они, не нарушая нятно, что при разумной организации движения этого правила, уложить соты на сфере Формула (3) граф дорог должен быть правильным, иначе водипривела бы тогда к неравенству тели вынуждены будут нарушать предписания дорожных знаков.) -Nр < 3Nв. (4) Докажем вслед за Столлингсом (хотя и иначе, чем в [2]), что в найдется внутренняя грань (квартал), которую можно обойти, двигаясь все время в К тому же из каждой вершины выходит не менее соответствии с ориентацией ее ребер. (На рис. 4 татрех ребер. Отсюда 3Nв 2Nр (коэффициент 2 в пракая грань окрашена в розовый цвет.) вой части нужно поставить ввиду двойного учета каждого ребра при просмотре всех вершин). Полу- Сначала заметим, что, начав движение по ченное противоречие с (4) означает невозможность вдоль произвольного ребра e = e1, можно его просотовой конструкции, покрывающей всю сферу. должить вдоль некоторого ребра e2, так как конец, ‹11, ребра e не может быть по условию стоком. Ввиду ко- верхности сферы. Плоскую интерпретацию теоренечности числа ребер в в ряду e1, e2, … неизбежно мы читатель может дать самостоятельно.

наступят повторения, то есть в графе имеется неВ дальнейшем – связный неориентированный который ориентированный замкнутый путь p. Можграф на сфере, вокруг каждой грани которого будут но считать, что путь р выбран простым (без самопепо часовой стрелке двигаться (возможно, с различресечений), иначе можно путь р заменить его частью ными переменными скоростями) точки. В отличие (красный путь на рис. 4).

от неподвижных точек графа назовем их автомобилями. Каждую грань объезжает вдоль границы ровно один автомобиль. После некоторого уточнения постановки задачи будет доказано, что столкновение автомобилей неизбежно.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.