Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec09/burman.pdf Дата изменения: Fri Dec 25 13:06:44 2009 Дата индексирования: Tue Oct 2 06:00:18 2012 Кодировка: koi8-r Поисковые слова: магнитосфера земли

РИСОВАНИЕ ГРАФОВ НА ПОВЕРХНОСТЯХ
Ю.М.БУРМАН

Рассмотрим граф из двух вершин, A и B , соединенных тремя ре брами, p, q и r. Изо бразим его на плоскости так, что бы ре бра не пересекались. Будем о бходить вокруг вершины A по часовой стрелке и записывать, какие ре бра нам встретились | например, p, затем q, затем r. Теперь проделаем ту же процедуру с вершиной B . Нетрудно видеть, что порядок ре бер в этом случае будет другим: если начали с ре бра p, то следом будет r, а потом q (см. рис. 1). Возникает вопрос, можно ли данный граф нарисовать по-другому, так чтобы при о бходе вокруг вершин A и B по часовой стрелке ре бра появлялись в одном и том же порядке? Кажется очевидным, что это невозможно, однако попро буем. Расположим граф как-нибудь в пространстве и возьмем резиновый круг | из него будем клеить то, на чем нарисован граф. Приклеим часть границы круга к ре бру p, двигаясь от вершины A к вершине B . Поскольку следующее при о бходе ре бро | q, следующую часть границы приклеим к q, двигаясь от B к A. Следующее ре бро | r, приклеим к нему; мы опять оказались в вершине B . После r опять идет p (о бход делается по циклу) | приклеим очередную часть границы круга к нему \с другой стороны", соединив ее с той частью границы круга, которая приклеивалась к ре бру p раньше. Затем | вторично ре бро q, вторично ре бро r, и процесс закончен. Теперь граф нарисован на резиновой пленке, и порядок ре бер при о бходе по часовой стрелке вокруг каждой из вершин одинаков | p, q, r. Однако в отличие от предыдущей картинки пленка представляет со бой не плоскость, а тор | поверхность бублика (см. рис. 2). Таким же о бразом можно было получить и картинку на рис. 2, в котором циклические порядки в вершинах A и B различные; при этом, правда, потребуется не один круг, а три. А именно, возьмем первый круг и приклеим часть его границы к ре бру p, двигаясь от A к B . В точке B следующее по часовой стрелке ре бро | r; приклеим следующий участок границы к нему, двигаясь к A. В точке A за ре бром r следует по часовой стрелке ре бро p | таким о бразом, процесс приклейки круга закончился. При этом в графе остались остались еще не заклеенные ре бра; возьмем второй круг и приклеим его, например, к ре бру q; тогда следующее ре бро (в точке B ) будет p (с о братной стороны), а потом
·

B r

p

q
·

A Рис. 1. Граф на плоскости
1


r A
·

p

·

B q

Рис. 2. Граф на торе опять q | круг приклеен. Третий круг заклеивает дырку между ре брами q и r; таким о бразом, три круга склеиваются в сферу. Подо бную процедуру склейки кругов можно применять к произвольному графу с любым циклическим порядком ре бер в каждой вершине; при склейке будут получаться различные поверхности. Можно показать, что эти поверхности всегда будут \сферами с ручками". Сфера с g ручками, для некоторого целого неотрицательного числа g, получается так: берется о бычная сфера, в ней проделывается g дырок и к каждой приклеивается \ручка" | тор с вырезанной дыркой. Как понять, какое именно количество ручек получится? Прежде всего, оно связано с количеством кругов, которое понадо бится склеить для получения поверхности (или, что то же самое, с количеством \граней" | кусков, на которые распадется поверхность, если ее разрезать по нарисованному графу):

Теорема 1. Пусть в графе V вершин и E ребер, а поверхность получена (описанным выше способом) склеиванием F кругов и представляет собой сферу с g ручками. Тогда V - E + F = 2 - 2g.
Во-вторых, количество ручек можно определить напрямую по графу и циклическому порядку вершин. Напомним, что перестановкой элементов конечного множества M = {1; 2; : : : ; n} называется правило (ото бражение) , сопоставляющее каждому элементу k M элемент (k) M так, что если элементы k и l различны, то элементы (k) и (l) тоже различны. Разделим каждое ре бро графа пополам на два полуре бра; каждое полуребро примыкает к одной вершине графа. Занумерум полуре бра: 1; 2; : : : ; 2E . Рассмотрим на множестве полуре бер две перестановки, и . Перестановка меняет местами полуре бра, принадлежащие одному ре бру исходного графа (для всех ре бер одновременно). Перестановка переводит каждое полуре бро x в полуре бро с концом в той же вершине, следующее за x в циклическом порядке. Сделаем теперь две перестановки | сначала , потом (это называется композицией перестановок и о бознчается ). Тогда получится (проверьте!) перестановка, переводящая каждое полуре бро x в полуре бро, лежащее на границе той же грани, что и x, и следующее за x при о бходе грани против часовой стрелки. Тем самым можно посчитать количество граней: нужно начать с произвольного полуре бра x1 ; перестановка переводит его в полуре бро x2 , его | в x3 , и так далее, пока не получим опять x1 . Это одна грань; теперь возьмем полуре бро y1 , которое мы еще не получили, и применим к нему тот же процесс; получим вторую грань, и т.д. Пусть теперь дан произвольный граф . Будем рассматривать всевозможные циклические порядки ре бер в его вершинах; каждому порядку сопоставим


описанным выше спосо бом поверхность. Обозначим Ng ( ) количество циклических порядков, при которых поверхность является сферой с g ручками. Вычисление чисел Ng ( ) | важная и интересная задача. Задача 1. Докажите, что если граф | дерево с n вершинами, то Ng ( ) = 0 при всяком g > 0 (т.е. из дерева всегда получается сфера). Задача 2. Докажите аналогичное утверждение для произвольного связного графа, из которого можно удалить одно ре бро так, что получится дерево. Задача 3. Найдите числа Ng ( ), где граф это а) граф с двумя вершинами и тремя ре брами, описанный в начале этого текста; б) граф с одной вершиной и двумя ре брами-петлями в ней; в) граф с двумя вершинами и тремя ре брами: по одной петле в каждой вершине и одно ре бро, соединяющее вершины; г) граф с одной вершиной и тремя ре брами-петлями в этой вершине; д) граф с одной вершиной и n ре брами-петлями в этой вершине. Задача 4. Попробуйте вычислить Ng ( ) еще для каких-нибудь графов . Если заметите какие-либо закономерности, докажите их. Задача 5. Как меняется Ng ( ), если в графе удалить ре бро? А если стянуть ре бро?
Независимый Московский Университет E-mail address : burman@mccme.ru