Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=28 Дата изменения: Fri May 5 15:25:35 2006 Дата индексирования: Tue Oct 2 02:28:49 2012 Кодировка: koi8-r Поисковые слова: http www.mccme.ru

Критерии реализуемости ежей на плоскости и торе


Автор: Хураскин Алексей Сергеевич


Научный руководитель:Скопенков Аркадий Борисович


11 класс, СУНЦ МГУ


Москва


e-mail: khuraskin@hotmail.com


Обозначения

Ежом будем называть граф, состоящий из чётного количества отрезков с
общим началом и пронумерованными концами таким образом, что каждый номер
встречается ровно два раза. Отрезки в дальнейшем будем называть также
лучами или концами.
Реализуемыми будем называть ежи, такие, что, если соединить концы с
одинаковыми номерами, получится граф без самопересечений.


Принцип нахождения критерия реализуемости ежа


Мы будем выражать критерии с помощью запрещённых ежей: если в еже
содержится запрещённый подъеж, то ёж нереализуем.

Достаточное условие для запрещённого ежа: он должен быть нереализуем.
Действительно, если он нереализуем, то нереализуем и ёж, в котором он
содержится, т. к. для того, чтобы реализовать ёж, необходимо реализовать
любой его подъёж.


Плоскость


Теорема 1.1. Ёж на плоскости нереализуем ( он содержит следующий
запрещённый подъёж 1.1 (см. рис. 3.1).
Доказательство. 1. (() После соединения отрезков 1 плоскость разбивается
линией, гомеоморфной окружности, на две области, причем отрезки 2
принадлежат разным областям, следовательно, соединить их невозможно. 2. (()
Пусть ёж нереализуем. Тогда найдётся пара соответственных отрезков цвета 1,
таких, что их нельзя соединить линией, не пересекающей никакие другие уже
проведённые линии. А это возможно только в том случае, когда эти два
отрезка лежат в двух не связанных между собой областях, которые могли
образоваться только после соединения каких-то других отрезков цвета 2, как
на рис 1.2. Уберём линию, соединившую отрезки цвета 2, и получим тот же
подъёж, что и на рис. 3.1. ”

Итак, мы нашли всевозможные запрещённые ежи для ежа на плоскости.


Тор


Очевидно, что для тора нереализуемый ёж должен содержать Ж1.1, иначе он
был бы реализуем на плоскости, а, следовательно, и на торе. Соединим
соответственные вершины Ж1.1 единственным возможным на торе образом и
разрежем тор по параллели и меридиану. При этом тор станет поверхностью,
ограниченной четырьмя лучами выделенного нами подъежа (рис. 4.1).
[pic]


Таким образом, мы свели задачу к четырём ежам на ограниченной области
плоскости. Пронумеруем вершины ежей, как на рис. 4.1. Получившийся граф
будет нереализуем тогда и только тогда, когда после соединения некоторых
лучей цвета 3 окажется, что два луча некоторого цвета 4 окажутся в разных
областях, не связанных между собой. А это может случиться в следующих
случаях (см. рис. 4.2). На рисунке изображены всевозможные запрещённые ежи
и часть плоскости, получающаяся при разрезании по линиям 1 и 2. Очевидно,
что в получившейся области нельзя реализовать получившийся граф в том и
только в том случае, если при соединении некоторых лучей одного цвета и,
соответственно, делении фигуры на 2 несвязных области, найдутся два луча
одного цвета, лежащие в разных областях. По этому принципу мы поделили
запрещённые ежи по группам, лучи оказываются в разных областях при
соединении лучей, исходящих из 1) соседних вершин; 2) противоположных
вершин; 3) одной вершины (см. рис. 4.3).
Ежи, получающиеся путём замены одного цвета другим и с лучами, идущими в
обратном порядке, будем считать одинаковыми. Замену цвета будем обозначать
вектором (abcd) в соответствии со следующим правилом: цвет 1 заменяется на
[pic], 2 - на [pic], и т. д. Инвертирование ежа обозначим R. Если ёж X
получается из Y поворотом и заменой цветов в соответствии с вектором[pic],
то обозначим это так: Y>X : [pic]. А теперь удалим дублирующие ежи.
2.1 > 2.4:[pic]
2.3 > 3.3:[pic]
3.2 > 3.4:[pic]
1.4 > 3.2:[pic]
1.2 > 2.1:[pic]
1.3 > 2.3:[pic]
3.4 > 1.1:[pic], но 3.4 уже был исключён, т. к. дублирует 1.4, значит,
1.4 можно исключить.
1.2 > 1.3:[pic]

Итак, оставшиеся ежи: 1.1, 1.2, 2.2, 3.1.

Ответ: 1.1, 1.2, 2.2, 3.1.



[pic]






Направление дальнейших исследований

Воспользовавшись результатами данной работы, можно продолжить
исследования вывести результаты для всех поверхностей в общем случае.

Список литературы

B. Mohar, Obstruction to embeddings of graphs into surfaces, J. of
Combinatorial Theory, 1976.
J. L. Gross and T. W. Tucker, Topological graph theory, Wiley-
Interscience, New York, 1987.

-----------------------
Рис. 3.1

Рис. 4.2

Рис. 4.1

[pic]