2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Группа путей
Сообщение31.03.2010, 13:31 
Аватара пользователя
Дан многоугольник на плоскости, разбитый на $N$ меньших многоугольников так, что никакая вершина одного многоугольника не лежит внутри стороны другого многоугольника. Фиксирована вершина $A$. Рассматриваются пути по сторонам многоугольников, начинающиеся и заканчивающиеся в $A$. Два таких пути считаются одинаковыми, если один можно получить из другого добавлением в любое место и удалением из любого места ходов "туда-обратно". Имеется операция умножения путей - приписывание второго пути в конец первого.

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

Интуитивно мне кажется, что нужно $2N$ образующих: обходящих каждый многоугольник разбиения по и против часовой стрелки. Но как строго доказать, что любой путь через них выражается?
(Хочется это доказывать индукцией по длине пути, но как сделать шаг? Да и база не ясна..)

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 13:44 
Аватара пользователя
Вы рассматриваете пути с началом и концом в А. Тогда операция умножения образует "лепестки"? Опять же одинаковость путей тоже сформулирована не очень естественно. Если мы пройдём по некоторым рёбрам вперёд, а потом строго по ним вернёмся назад, то получается, что мы можем выкинуть любое ребро. Как мы сможем обойти по часовой стрелке многоугольник, не содержащий А?
-----
дошло.

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 13:49 
Аватара пользователя
Дойти от A до него, обойти в нужную сторону, вернуться назад как шли.

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 14:15 
Аватара пользователя
gris в сообщении #304900 писал(а):
Опять же одинаковость путей тоже сформулирована не очень естественно. Если мы пройдём по некоторым рёбрам вперёд, а потом строго по ним вернёмся назад, то получается, что мы можем выкинуть любое ребро.

Имеется в виду, что удалять ходы "туда-обратно" можно только рядом стоящие в этом пути.

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 14:54 
Аватара пользователя
Наверное, не только рядом стоящие. Путь "стоять на месте в точке А" будет единицей, а путь, пройденный задом наперёд обратным элементом. Произведение пути на обратный должно равняться единице, но для этого нам придётся удалять просто рёбра, по которым прошли туда-сюда. Но это не важно.

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 15:24 
Аватара пользователя
Возьмите в графе $\Gamma$, образованном сторонами и вершинами данных многоугольников, максимальное дерево и стяните это дерево в точку

останется граф $\Gamma'$ с одной вершиной и $N$ петлями в этой вершине

постройте взаимнооднозначное соответствие "уважающее умножение" между классами эквивалентных путей в графах $\Gamma$ и $\Gamma'$

Ответ: $2N$

-- Ср мар 31, 2010 15:28:05 --

2 $N$ образующих у полугруппы классов эквивалентностей путей и $N$ у соответствующей (свободной) группы

 
 
 
 Re: Группа путей
Сообщение31.03.2010, 19:16 
Аватара пользователя
paha
Да! Максимальное поддерево - это то, что доктор прописал в данной ситуации. Теперь все ясно, спасибо.

 
 
 
 Re: Группа путей
Сообщение01.04.2010, 04:43 
Аватара пользователя
Имеется в виду фундаментальная группа?

 
 
 
 Re: Группа путей
Сообщение01.04.2010, 11:43 
Аватара пользователя

(Оффтоп)

Профессор Снэйп в сообщении #305182 писал(а):
Имеется в виду фундаментальная группа?



Доброе утро)))

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group