|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Предметом статьи являются некоторые старые и новые следствия наглядно очевидного утверждения: всякая замкнутая кривая без самопересечений на плоскости разбивает ее на две области: внутреннюю и внешнюю. Изложение вполне элементарно.
ПЛОСКИЕ ГРАФЫА. Ю. ОЛЬШАНСКИЙ
Московский государственный университет
им. М.В. Ломоносова
ВВЕДЕНИЕ
Электросхемы и схемы транспортных коммуникаций, чертежи и географические карты, структурные формулы молекул и генеалогические деревья доставляют многочисленные примеры графов, в которых выделенные точки соединены линиями, призванными сообщить о важных связях или другой полезной информации. В настоящей статье, ориентированной в основном на старшеклассников, проявляющих интерес к математике, речь идет о свойствах плоских графов, не меняющихся при непрерывных преобразованиях, иначе говоря, об их топологических свойствах.
Относящиеся к XVIII и XIX векам основные факты плоской топологии, такие, как теоремы Эйлера и Жордана, весьма наглядны. Тем неожиданнее оказываются новые интересные наблюдения, и среди них красивая теорема Ан.А. Клячко [1] и простая, но изящная лемма Дж. Столлингса [2] (см. ниже разделы 6 и 7), которые были опубликованы соответственно в 1993 и 1987 годах в связи с проблемами комбинаторной теории групп.
C инженерной точки зрения представляет интерес вопрос о возможности плоского соединения микросхем. Такая задача возникает в радиоэлектронике при проектировании печатных плат. Можно ли, к примеру, попарно соединить пять точек плоскости линиями без взаимных пересечений? Так, на рис. 1, а все пары точек, кроме одной, соединены зелеными линиями, а одна пара - красной. Она, к сожалению, пересекается с одной зеленой линией. А можно ли было избежать пересечений при ином способе плоского соединения? Имеет ли решение старинная задача о трех колодцах: проложить от "дворов" 1, 2, 3 (хозяева которых не ладят между собой) по три тропинки к каждому из "колодцев" 4, 5, 6 (рис. 1, б ), которые бы нигде не пересекались между собой?
Для ответа на эти и другие вопросы уточним сначала, какими свойствами обладает плоская линия.
1. ПЛОСКАЯ ЛИНИЯ
Окружность, граница квадрата или путь 1 - 4 - 2 - 6 - 3 - 5 - 1 на рис. 1, б отвечают нашему представлению о простой замкнутой кривой на плоскости как о линии, которую можно нарисовать, не отрывая карандаша от бумаги, без самопересечений и с возвращением в исходную точку. Если же конечная точка не совпадает с начальной, то полученную линию назовем дугой.
По существу, такого представления о замкнутой кривой и дуге достаточно для понимания дальнейшего изложения. Но для читателя, не удовлетворенного наглядным пояснением, мы приводим в этом разделе формальное определение. Оно обобщает простое наблюдение: граница квадрата может быть получена из описанной окружности непрерывным преобразованием (например, проецированием каждой ее точки на ближайшую сторону квадрата).
В общем случае рассматривается произвольное отображение f окружности O единичного радиуса на некоторое подмножество C плоскости со свойствами:
1) f взаимно однозначно, то есть у каждой точки X окружности O имеется один образ Y = f (X ) в C и, наоборот, у каждой точки Y k C имеется ровно один прообраз X k O ;
2) отображение f (равномерно) непрерывно. Это значит, что для любого, сколь угодно малого положительного числа e можно подобрать число d > 0 такое, что для любых точек X1 , X2 k O, находящихся на расстоянии менее d, расстояние между их образами Y1 = f (X1) и Y2 = f (X2) меньше e.
Если отображение f : O C со свойствами 1) и 2) существует, то C называется простой замкнутой кривой. Когда переменная точка X обходит окружность O, соответствующая точка Y = f (X ) обходит кривую C.
Определение (плоской) дуги d отличается от приведенного только тем, что вместо окружности O выбирается стандартный отрезок [0; 1]. При изменении точки X k [0; 1] от 0 до 1 ее образ Y = f (X ) "проходит" дугу d. Образы чисел 0 и 1 являются концами дуги d.
2. ТЕОРЕМА ЖОРДАНА
Стандартная единичная окружность разбивает евклидову плоскость на две компоненты: внутреннюю, с условием x 2 + y 2 < 1 для лежащих в ней точек (x, y) и внешнюю, с условием x 2 + y 2 > 1. Понятно, что точку (x1 , y1) из внутренней компоненты нельзя соединить дугой с точкой (x2 , y2) из внешней компоненты, не пересекая окружности O, поскольку непрерывная функция расстояния переменной точки дуги (x, y) от начала координат, принимая значения < 1 и > 1, должна принять в какой-то промежуточной точке (x, y) значение = 1.
Теорема Жордана утверждает, что это свойство окружности распространяется на любую плоскую простую замкнутую кривую C. А именно: множество всех точек плоскости, не лежащих на C, разбивается на две области: внутреннюю (или ограниченную) E1 и внешнюю (неограниченную) E2 , так что любые две точки из одной области можно соединить между собой дугой, целиком лежащей в этой же области, но никакую точку из E1 нельзя соединить дугой с точкой из E2 , не пересекая кривую C.
Эта теорема дополняется теоремой Шенфлиса: всякая точка Z k E1 (Z k E2) может быть соединена со всякой точкой Y k C c помощью некоторой дуги, все точки которой, кроме Y, лежат в E1 (соответственно в E2).
Строгое доказательство теорем Жордана и Шенфлиса оказывается неожиданно трудным и часто не приводится во вводных топологических курсах. Точно так же поступим сейчас и мы. Отсутствие доказательств частично оправдывается наглядностью утверждений теорем. Кроме того, для наших целей вполне достаточно было бы рассматривать не произвольные кривые, а только ломаные линии, составленные из конечного числа звеньев-отрезков (но даже для них теорема Жордана нетривиальна!).
3. ГРАФЫ НА ПЛОСКОСТИ И СФЕРЕ
Оговоримся сразу, что все графы далее будут конечными. Под графом G на плоскости понимается некоторое конечное множество вершин V = {u1 , _, uk} (выделенных точек плоскости) вместе с некоторым конечным множеством E = {e1 , _, el} соединяющих их ребер. При этом ребро, соединяющее различные вершины, - это дуга, а ребро с началом и концом в одной вершине (называемое также петлей) - это простая замкнутая кривая. Требуется, чтобы каждое ребро не имело общих точек, отличных от его начала или конца, с другими ребрами.
Граф на рис. 2, а не является связным, потому что связным называется граф G, в котором любые две вершины можно соединить непрерывным путем, составленным из нескольких ребер графа G. Граф 2, а распадается на два связных графа G1 и G2 . Под плоским графом мы понимаем в дальнейшем связный граф на плоскости, имеющий хотя бы одно ребро.
Простая замкнутая кривая (или ломаная) линия, составленная из ребер плоского графа G, разбивает плоскость в соответствии с теоремой Жордана на две области, а весь граф G разбивает ее на несколько областей или граней графа G. "Красный" граф на рис. 2, б состоит из пяти внутренних граней (розового цвета) и одной внешней (неограниченной) области плоскости с "внутренней" границей 1 - 2 - 3 - 4 - 1.
Теоремы Жордана и Шенфлиса позволяют для каждого плоского графа G построить двойственный ему плоский граф G0 следующим образом. Выберем внутри каждой грани графа G по одной точке - вершине графа G0 (a, b, c, x, y, z на рис. 2, б ). Если e - смежное ребро двух каких-либо граней F1 , F2 графа G с выделенными внутри них вершинами o1 , o2 , то выберем на е одну неконцевую точку o и проведем внутри граней F1 , F2 дуги o1 - o и o2 - o соответственно. (На рис. 2, в представлен фрагмент графа 2, б, в котором такое построение показано только для двух граней F1 и F2 с вершинами o1 = a и o2 = b внутри их.) Дуга o1 - o - o2 , пересекающая ребро е, объявляется ребром e0 графа G0, соединяющим вершины o1 и o2 в G0.
На рис. 2, б двойственный граф G0 для красного графа G нарисован синим цветом. По определению, число вершин в графе G0 равно числу граней в Г, число ребер в G0 такое же, как и в графе G (почему?), а число граней графа G0 равно числу вершин графа G.
Легко представить, как плоский граф может быть уложен на сфере. Наоборот, каждый граф G на сфере имеет плоскую реализацию: нужно объявить северным полюсом точку o внутри некоторой грани и спроецировать сферический граф G из o на плоскость, касающуюся южного полюса. В частности, если сначала "раздуть" грани куба до сферы (это можно сделать, спроецировав из центра куба все его ребра на описанную сферу), а потом построить для полученного сферического графа описанную выше стереографическую проекцию, то в результате возникнет красный граф на рис. 2, б. Одной из граней куба (над которой находится северный полюс) соответствует неограниченная грань плоского графа 2, б. Аналогично вершины, ребра и грани любого выпуклого многогранника превращаются в вершины, ребра и грани некоторого плоского графа. (Проверьте, что при такой укладке на плоскости октаэдр двойствен кубу.)
4. ФОРМУЛА ЭЙЛЕРА
Обозначим Nв , Nр и Nг соответственно числа вершин, ребер и граней некоторого многогранника P. Например, для куба (Nв , Nр , Nг) = (8, 12, 6), для октаэдра эта тройка равна (6, 12, 8), для тетраэдра (4, 6, 4), для додекаэдра (рис. 3, а) (20, 30, 12), для n-угольной пирамиды (n + 1, 2n, n + 1), а для n-угольной призмы (2n, 3n, n + 2). Каждый раз
Nв - Nр + Nг = 2.
Что это: любопытное совпадение или проявление общей закономерности?
Оказывается, формула Эйлера (1) справедлива для произвольного плоского графа G, а поэтому верна и для многогранников ввиду возможности их укладки на плоскости с превращением одной из граней в неограниченную область. Доказательство формулы Эйлера легко проводится с помощью индукции по числу ребер Nр плоского графа G. В случае Nр = 1 есть две возможности: единственное ребро является петлей или простой дугой. В первом случае имеется одна вершина и по теореме Жордана две грани, а во втором случае (Nв , Nр , Nг) = (2, 1, 1). В обоих случаях соотношение (1), очевидно, верно.
При Nр > 1 опять-таки рассмотрим два случая.
1. В графе G имеется вершина o степени 1, то есть принадлежащая только одному ребру e, которое к тому же не является петлей (как вершина в графе G на рис. 2, а). В таком случае граф G', полученный удалением из G ребра e вместе с одной его вершиной o, является связным, причем для него
Поскольку , можно считать формулу Эйлера уже доказанной для G': . Подстановка равенств (2) в это соотношение дает формулу Эйлера (1) для G.
2. Пройдя любое ребро e = e1 , можно непрерывно продолжить движение по какому-то ребру e2 . Тогда неизбежно повторение ранее пройденных ребер после достаточно большого числа таких продолжений ввиду конечности числа ребер в G. Понятно, что в этом случае можно составить простой замкнутый путь из нескольких последовательных ребер e1 , e2 , _, ek графа G (возможно, k = 1). Из теорем Жордана и Шенфлиса следует - и этот факт наглядно очевиден, - что удаление из G ребра e (без удаления его начальной и конечной вершин) уменьшает число граней на 1, то есть в полученном графе G'
Теперь индуктивное рассуждение завершается, как и в первом случае.
5. ПЛАНАРНЫЕ ГРАФЫ
Применим формулу Эйлера к сферическим или плоским графам, у которых при обходе каждой грани (в том числе и внешней в плоском случае) проходится не менее n ребер для данного n > 2. Считая тогда при обходе всех граней общее число ребер, получим величину, не меньшую nNг . Ввиду двойного учета каждого ребра при таком счете получаем неравенство
2Nр $ nNг .
Прибавим теперь к обеим его частям соответственно левую и правую части равенства (1), умноженные предварительно на n. Получим
Неравенство (3) полезно для решения вопроса о возможности укладки на плоскости или сфере "абстрактных" графов. (Под произвольным графом понимается любая схема соединения конечного множества вершин посредством ребер, имеющих общие точки только в вершинах, которая необязательно располагается на плоскости.)
Легко объяснить, например, что граф K5 (рис. 1, а) нельзя уложить на плоскости без самопересечений. В самом деле, в нем нет петель и кратных ребер (то есть двух разных ребер с одинаковыми концами), а значит, каждая грань этого графа, расположенного на плоскости, имела бы не менее трех граничных ребер. Но формула (3) при n = 3 не выполнена для графа K5 , так как он имеет 5 вершин и 10 ребер.
Принимая, что граф K3, 3 (рис. 1, б ) допускает плоскую реализацию, можно применить формулу (3) при n = 4, так как в этом графе нет и замкнутых путей с тремя ребрами. (К примеру, выйдя с какого-либо "двора" и пройдя три "тропинки", мы непременно окажемся у какого-то "колодца".) Опять получаем противоречие с (3), ибо в этом случае Nв = 6, a Nр = 9.
Непланарен (то есть не укладывается на плоскости), очевидно, и граф, содержащий в себе меньший граф (подграф), который непланарен. Непланарны, конечно, графы, гомеоморфные графам K5 и K3, 3 , то есть такие, которые получаются из них при разбиении каждого ребра e на несколько ребер посредством расположения на e нескольких дополнительных вершин. Знаменитая теорема Понтрягина - Куратовского утверждает, что других препятствий для планарности нет:
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графу K5 или графу K3, 3 .
Выше была доказана необходимость условия этой теоремы. Доказательство достаточности значительно труднее (см. [3]).
Еще одно применение формула (3) находит при n = 6. Как известно, пчелы конструируют свои соты так, что каждая их ячейка (внутренняя грань) является шестиугольной. А могут ли они, не нарушая этого правила, уложить соты на сфере? Формула (3) привела бы тогда к неравенству
К тому же из каждой вершины выходит не менее трех ребер. Отсюда 3Nв # 2Nр (коэффициент 2 в правой части нужно поставить ввиду двойного учета каждого ребра при просмотре всех вершин). Полученное противоречие с (4) означает невозможность сотовой конструкции, покрывающей всю сферу.
Это рассуждение заодно доказывает, что не существует выпуклых многогранников, у которых каждая грань имеет не менее шести сторон. По этой же причине футбольный мяч сшивается из шести- и пятиугольных лоскутов.
Читателю предлагается самостоятельно вывести неравенства для чисел вершин и ребер мяча, сшитого из k пятиугольных и l шестиугольных лоскутов, и доказать, что k $ 12. (Указание: число ребер равно , а число вершин не превосходит .) Из 12 пятиугольных лоскутов мяч можно было бы сшить так же, как додекаэдр составлен из 12 пятиугольников (рис. 3, а), но такой мяч был бы недостаточно круглым. Настоящий футбольный мяч сшит из 12 пятиугольных и 20 шестиугольных лоскутов вдоль 90 ребер (рис. 3, б). Найдите, пожалуйста, число его вершин по формуле Эйлера!
6. УЛИЦЫ С ОДНОСТОРОННИМ ДВИЖЕНИЕМ
Лемма Столлингса утверждает, что если в некотором городе по каждой улице между двумя соседними перекрестками разрешается двигаться только в одном направлении, то обязательно найдется квартал, вокруг которого можно объехать.
Математическая формализация задачи такова. Пусть G - плоский граф, который ориентирован, то есть каждому ребру приписано определенное направление, что наглядно изображается стрелкой (и мы не будем здесь вдаваться по этому поводу в дальнейшие формальности). Назовем такой граф правильным, если в нем нет вершин, из которых все ребра только выходят, - "источников" и нет вершин, в которые все ребра только входят, - "стоков". (Понятно, что при разумной организации движения граф дорог G должен быть правильным, иначе водители вынуждены будут нарушать предписания дорожных знаков.)
Докажем вслед за Столлингсом (хотя и иначе, чем в [2]), что в G найдется внутренняя грань (квартал), которую можно обойти, двигаясь все время в соответствии с ориентацией ее ребер. (На рис. 4 такая грань окрашена в розовый цвет.)
Сначала заметим, что, начав движение по G вдоль произвольного ребра e = e1 , можно его продолжить вдоль некоторого ребра e2 , так как конец ребра e не может быть по условию стоком. Ввиду конечности числа ребер в G в ряду e1 , e2 , _ неизбежно наступят повторения, то есть в графе G имеется некоторый ориентированный замкнутый путь p. Можно считать, что путь р выбран простым (без самопересечений), иначе можно путь р заменить его частью (красный путь на рис. 4).
По лемме Жордана путь р разбивает плоскость на две области. Внутренняя область О содержит несколько граней F1 , _, Fk (k = 5 на рис. 4) графа G. Будем считать, что простой путь р уже выбран так, что число граней в О минимально возможное. Для доказательства леммы Столлингса достаточно установить, что k = 1, то есть что путь р обходит ровно одну грань.
Допустив, что k > 1, приходим к выводу, что внутри области О должны быть некоторые ребра графа G. Ввиду связности графа G одно из таких ребер f должно иметь какую-то общую вершину о с границей р области О (рис. 4). Рассмотрим ниже только случай, когда ориентированное ребро f выходит из о, ибо второй случай, когда f входит в о, сводится к первому при помощи замены ориентации каждого ребра графа G на противоположную.
Поскольку конец o1 ребра f = f1 не является стоком, найдется ребро f2 , выходящее из o1 . Продолжая так построение пути q из ребер f1 , f2 , _ (синий путь на рис. 4) внутри области О, мы не получим самопересечений в q, как видно из условия минимальности при выборе пути р. Поэтому ориентированный путь q неизбежно еще раз выйдет на границу р области О в какой-то вершине o'. Путь q разобьет замкнутый путь р на две части p1 и p2 . Вместе с той из них, которая выходит из o' и входит в о, q образует простой замкнутый ориентированный путь, который ограничивает область с числом клеток, меньшим, чем k.
Полученное противоречие с выбором пути р и числа k показывает, что сделанное выше допущение неверно, то есть k = 1.
7. СТОЛКНОВЕНИЯ НЕИЗБЕЖНЫ
В теореме Клячко нам уже придется иметь дело не только с правилами дорожного движения, но и с динамическими моделями самого движения по поверхности сферы. Плоскую интерпретацию теоремы читатель может дать самостоятельно.
В дальнейшем G - связный неориентированный граф на сфере, вокруг каждой грани которого будут по часовой стрелке двигаться (возможно, с различными переменными скоростями) точки. В отличие от неподвижных точек графа назовем их автомобилями. Каждую грань объезжает вдоль границы ровно один автомобиль. После некоторого уточнения постановки задачи будет доказано, что столкновение автомобилей неизбежно.
В это утверждение легко поверить для графа, в котором всего одна вершина и одно ребро е (петля). Например, если е - экватор, разделяющий сферу S на северное и южное полушария (рис. 5, а), то один автомобиль должен объезжать по экватору северное полушарие по часовой стреле (для воображаемого наблюдателя, стоящего на северном полюсе), а другой - объезжать южное полушарие по часовой стрелке (но c точки зрения наблюдателя, стоящего на южном полюсе).
Для графа с двумя вершинами, разрезающего сферу на дольки вдоль нескольких меридианов (рис. 5, б ), неизбежность столкновений уже не столь очевидна, и читатель может попробовать (увы, безуспешно) организовать движение без столкновений. Еще менее очевидно утверждение для графов с большим число вершин граней и ребер.
Сделаем теперь следующие необходимые уточнения в формулировке задачи. Во-первых, граф G считается не имеющим вершин степени 1 (иначе можно было бы избегать столкновений, "прячась" на время на единственном ребре, входящем в такую вершину). Во-вторых, каждое ребро проходится любым автомобилем за ограниченное (какой-то общей константой T > 0) время, иначе при бесконечно затухающем движении автомобилей они могут никогда не столкнуться и даже не уйти далеко от своих произвольно заданных стартовых позиций. В-третьих, попадая в вершину, автомобиль не может задержаться в ней, а должен немедленно продолжить движение по следующему ребру. (Это требование можно ослабить, запретив лишь неограниченно долгие задержки в вершинах.) Наконец, каждый автомобиль объезжает свою грань всегда по часовой стрелке, возвратного движения не допускается. ("По часовой стрелке" наглядно означает, что грань, которую предписано обходить данному автомобилю, в каждый момент находится справа от направления движения. От более формальных объяснений этого понятия мы воздержимся.)
Движение автомобилей вокруг граней сферического графа G со сделанными выше оговорками назовем регулярным.
Теорема Клячко. Независимо от начального расположения автомобилей регулярное движение без столкновений не может быть вечным, иначе говоря, по прошествии некоторого времени неизбежно столкновение какой-то пары автомобилей.
Методом от противного проведем доказательство этого утверждения (сформулированного в чуть менее сильной форме, чем в [1]) в несколько шагов.
1. Удобно считать, что в каждый момент времени t > 0 не более одного автомобиля может находиться в вершинах графа G. Этого всегда можно добиться с помощью очень малого локального изменения графика движения автомобилей, которое не добавит новых столкновений.
2. Можно далее считать, что в любой момент времени t > T ни на одном ребре не находится двух автомобилей сразу в точках, отличных от вершин ребра. Действительно, поскольку каждый из них обходит свою грань по часовой стрелке, по общему ребру двух граней они могут двигаться только в противоположные стороны. Но это означает, что они должны вскоре встретиться или уже разъезжаются после встречи в некоторый предыдущий момент времени t ' > t - T > 0.
3. Введем в рассмотрение двойственный граф G0. Если в момент времени t > T какой-то i-й автомобиль, объезжающий грань Fi графа G (черный граф на рис. 5, в), находится на ребре е этой грани (но не в вершине), то выделим ребро e0 графа G, пересекающее ребро е. Ориентируем ребро e0 так, чтобы оно пересекало ребро е справа налево, если смотреть в направлении движения i-го автомобиля. В соответствии с п. 2 при выборе ориентации ребра e0 не может возникнуть недоразумения.
Итак, для каждого неособого момента времени t > T, то есть когда ни один автомобиль не находится в какой-либо вершине, построен ориентированный граф Dt (на рис. 5, в его ребра красные), составленный из всех вершин графа G0 и всех его выделенных в момент t ребер e0 с определенной выше их ориентацией. (Число ребер в Dt = число автомобилей = = число граней в G = число вершин в G0 = число вершин в Dt .)
4. Из каждой вершины графа Dt выходит одно (и только одно) его ребро e0, поскольку, по определению, эта вершина находится внутри некоторой грани Fi графа G, а на некотором ребре е этой грани в момент времени t находится i-й автомобиль, обходящий грань Fi по часовой стрелке.
Как и в разделе 6, из некоторых ребер e = e1 , e2 , _ графа Dt можно составить ориентированный простой замкнутый путь р (сплошной красный путь на рис. 5, в). Обозначим буквой О ту область сферы с границей p, которую этот путь р обходит по часовой стрелке.
5. Что произойдет, когда некоторый i-й автомобиль, находившийся ранее на ребре е графа G, пройдет через очередную вершину? Очевидно, ребро e0 графа Dt исчезнет, а в новом графе (если его можно однозначно определить) появится вместо e0 новое ориентированное ребро f 0 (рис. 5, г). При этом ребро f 0 не выходит из области О, поскольку движение автомобиля вокруг Fi происходит по часовой стрелке. Ориентированный путь в , начатый ребром f 0, можно продолжить, пока не получится некоторый простой замкнутый путь p' в графе , который ограничивает область O ', содержащую меньшее число вершин из G (или граней графа G 0), чем область О (сплошной красный путь на рис. 5, г).
6. Уменьшение со временем числа вершин графа G, охватываемых строящимися так последовательно путями p, p', p", _, не может продолжаться бесконечно. Следовательно, в некоторый момент времени t0 > T соответствующий граф уже нельзя будет однозначно определить. Это может случиться, только если на одном ребре графа G оказалось одновременно два автомобиля. Но такая конфигурация сразу приводит к цели (см. п. 2 доказательства теоремы).
ЛИТЕРАТУРА
1. Кlyachko An.A. // Commun. in Algebra. 1993. V. 21. ╧ 21. P. 2555-2575.
2. Stallings J.R. In: Combinatorial Group Theory and Topology / Ed. S.M. Gersten, J.R. Stallings. Princeton (N. J.): Princeton Univ. Press, 1987. 552 p.
3. Харари Ф. Теория графов. М.: Мир, 1973. 302 с.
* * *
Александр Юрьевич Ольшанский, доктор физико-математических наук, профессор кафедры высшей алгебры механико-математического факультета Московского государственного университета им. М.В. Ломоносова. Член редколлегий ряда международных математических журналов. Область научных интересов: теория групп. Автор более 50 научных работ.
