Группа путей

[Ираклий]

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

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

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

[gris]

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

[ИСН]

Дойти от A до него, обойти в нужную сторону, вернуться назад как шли.

[Ираклий]

gris в сообщении #304900 писал(а):

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

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

[gris]

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

[paha]

Возьмите в графе $\Gamma$, образованном сторонами и вершинами данных многоугольников, максимальное дерево и стяните это дерево в точку

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

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

Ответ: $2N$

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

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

[Ираклий]

paha
Да! Максимальное поддерево - это то, что доктор прописал в данной ситуации. Теперь все ясно, спасибо.

[Профессор Снэйп]

Имеется в виду фундаментальная группа?

[paha]

(Оффтоп)

Профессор Снэйп в сообщении #305182 писал(а):

Имеется в виду фундаментальная группа?

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