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

Это сообщение отредактировал(а) mntek - 16.6.2005, 22:10

Их же столько: кол-во связаных вершин. Если вопрос точен то Перебором и только.

нет, там другое

Код

+  4                                 /   \                               /       \                             2 +-------+ 3                               \       /                                    \   /                                  + 1

и надо пройти минимальным путем многоугольники, в данном случае - треугольники 1 и 2 так, чтобы на выходе была строка, вида 123 и 234...

Это сообщение отредактировал(а) mntek - 17.6.2005, 00:35

Если это евклидов граф, т.е. вершины являются точками на плоскости, а ребра - отрезками, то это получается алгоритм построения минимальных полигонов.
Примерно так: начинаем с крайне-левой (например) вершины, в каждом узле выбираем ближайшее (по или против часовой стрелки) ребро, пока не замкнем цикл. Переходим к следущей вершине. И т.д. Ребра по дороге помечаем - каждое ребро можно пройти не более чем дважды.
Однако, это для ненаправленного графа. Для направленного тоже, наверно, как то можно приспособить, но не знаю, как получить все полигоны.

Цитата(Earnest @ 18.6.2005, 09:25)

Если это евклидов граф, т.е. вершины являются точками на плоскости, а ребра - отрезками, то это получается алгоритм построения минимальных полигонов. Примерно так: начинаем с крайне-левой (например) вершины, в каждом узле выбираем ближайшее (по или против часовой стрелки) ребро, пока не замкнем цикл. Переходим к следущей вершине. И т.д. Ребра по дороге помечаем - каждое ребро можно пройти не более чем дважды. Однако, это для ненаправленного графа. Для направленного тоже, наверно, как то можно приспособить, но не знаю, как получить все полигоны.

да, именно так. только мне нужна реализация этого алгоритма на паскале_)

Цитата(mntek @ 18.6.2005, 20:50)

только мне нужна реализация этого алгоритма на паскале

Если трудности с языком, который называется Паскаль, то - в соответствующий раздел.

как раз там это и было размещено. но модератор переместил топик в эту тему)

mntek
Я не понял проблемы... на основе своего графа построй вторичный граф, где узлы - центры треугольников... и получится элементарный поиск пути в графе...

Akina
Вообще-то, чтобы построить вторичный граф по центрам треугольников, их сначала нужно найти. И там, наверное, не только треугольники.

Mntek
К сожалением, с паскалем помочь не могу...

Цитата(Earnest @ 20.6.2005, 09:49)

чтобы построить вторичный граф по центрам треугольников, их сначала нужно найти

во проблема...

Цитата(Earnest @ 20.6.2005, 09:49)

там, наверное, не только треугольники.

Цитата(mntek @ 16.6.2005, 13:35)

элементарные площади - многоугольники без диагоналей

Ну я не так выразился... нужно пронумеровать эти "элементарные площади" - в обасалютно отфонарном порядке - и построить граф смежности этих площадей. Остальное более чем элементарно - из груды рабочих кодов в Инете выбрать самый понятно откомментированный.

PS. Какая площадь, ограниченная отрезками (кроме треугольника), не имеет диагоналей?

Цитата

Элементарные площади - многоугольники без диагоналей

Как я понимаю, речь идет о полигонах, не содержащих других ребер графа.

А насчет

Цитата

во проблема ...

может, просветите? Как найти все минимальные циклы в планарном графе? Опишите, пож., алгоритм в общих чертах или дайте ссылку...

Это сообщение отредактировал(а) Earnest - 20.6.2005, 15:50

реши задачу сравнением, есть формула длины отрезка через координаты,вот и запускай цикл!

mntek
Обычно за изменение исходного поста, полностью меняющего вопрос, лепят минус в репу... что вполне обосновано.

Цитата(Earnest @ 20.6.2005, 16:48)

Как найти все минимальные циклы в планарном графе?

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

Извините, Akina, это был не вопрос а, так сказать, сарказм - в ответ на ваше "во проблема". Человек спрашивал, как найти минимальные многоугольники, а вы ему предлагаете построить вторичный граф по центрам этих самых многоугольников, которые он найти не может.
Автору же темы, как я теперь понимаю, нужен был не принцип алгоритма, а готовая реализация, на Паскале. Так что наша дискуссия ему неинтересна...

Earnest
В изначальной редакции вопроса было указано, что они УЖЕ построены, и требуется только найти путь.