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

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

Обозначения

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

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

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

Идея решения

Найден запрещённый ёж для плоскости. Затем, воспользовавшись фактом, что,
если граф реализуем на плоскости, то он реализуем и на торе, мы разрезали
тор по соответственно соединённым рёбрам ежа, в результате чего получили
плоскую картинку, реализуемость которой надо выяснить. С помощью перебора
вариантов было найдено решение - 4 запрещённых ежа.

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

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

Литература

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