Обход графа с поиком его "внешних" точек.

[Utkin]

Сообщение от vedro-compota

хм. разве структура данных для графа определена однозначно? ))

О чем я Вам и говорю, о каких внешних точках может идти речь? О графа нет структуры, есть только отношения между вершинами.

ЗЫ, Только что увидел ответ для первого графа 0-3-13-2-1-5 . Мой ответ короче, а главное тоже правильный....

[vedro-compota]

Так же не ясно, что делать в таких случаях:

да не ясно )) такого по условию быть не может ))

ЗЫ, Только что увидел ответ для первого графа 0-3-13-2-1-5 .

Utkin.что за 1-ый граф?

вот здесь что-то типа ))
-------------------------------------------------------------------------
цитирую Википедию -

Пусть p0 — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений
2) Пусть <p_1, p_2,\ldots,p_m> — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,

кто знает- что такое полярный угол ? ( а то я не знаю)

Не, ребяты, Алгоритм Грехэма - это не то. ((
Смысл такой .
Ещё раз сформулирую задачу -

1) Пользователь задаёт количество точек.
2)Пользователь задаёт координаты этих точек на форме.
3) Пользователь показывает между какими точками имеются рёбра (например, с помощью матрицы смежности)
4) Любой такой граф можно обойти " по кругу" ( или обойти все его между собой не связанные "куски)

вот собственно, и всё. ))
Алгоритм Грехэма работает с точками не взирая на рёбра, а вся сложность задачи- как раз в возможном отсутствии этих рёбер у графа))

[Utkin]

Лыко да мочало начинай сначала. Точки графа не имеют координат. Решение задачи невозможно.

[vedro-compota]

Имеют ! КАк без координат его представить на плоскости?

[Utkin]

Сообщение от vedro-compota

Имеют ! КАк без координат его представить на плоскости?

Никак . Он и не должен представляться на плоскости. Как Вы себе на плоскости, к примеру, представляете обычное паскалевское множество? Как на плоскости представить аромат сирени? Как на плоскости представить свет утренного Солнца? Как на плоскости представить двоякое чувство, когда получаешь зарплату? Как на плоскости представить рост дерева? Как на плоскости представить развитие галактики?

Вот два абсолютно одинаковых графа. Ну и как определить, какие точки внешние?

[vedro-compota]

Хм. Ладно. ТОгда так -
схема, которую я выложил в первом сообщении - это граф, так как сосотоит из обозначеннных вершин и рёбер ( можно поспорить?) . Так как эта схема сумела "расположиться на плоскости", то и граф представить на плоскости можно ( неоднозначно, но можно), а чтобы его представить однозначно - и сущечтвуют координаты точек.

[Utkin]

Сообщение от vedro-compota

это граф, так как сосотоит из обозначеннных вершин и рёбер ( можно поспорить?) .

Да, можно поспорить. Граф состоит только из вершин и только из ребер. Все остальное графом не является . Вот так вот оккупационную войну в Ираке и назвали освободительным движением и борьбой с терроризмом, угрожающим ядерным оружием.

а чтобы его представить однозначно - и сущечтвуют координаты точек.

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

[Virtson]

Что же вы спорите ...

Введем дополнительное условие :
ребра не могут пересекаться без образования вершины, иными словами любое пересечение считается вершиной графа (координаты её известны по 4м точкам).
Более того, внуренние вершины все равно НЕ идут в ответ, они только для однозначной постановки задачи.

Тогда графы, которые привел Utkin, будут разными. И с графом pu4koff все становится понятно.

Можно относиться к объекту и по другому, как множество точек на плоскости, соединенных отрезками в треугольники (триангуляция) и фигуры с большим числов вершин, в общем случае.
Для случая с треугольниками (любые две смежные вершины имеют хотя бы 1 общую смежную) могу предложить достаточно простой алгоритм решения задачи.

[vedro-compota]

Тогда графы, которые привел Utkin, будут разными. И с графом pu4koff все становится понятно.

Virtson, вы правы ))
А вот Уткин вместо того , чтобы придираться мог бы и сказать - что это это за полярный угол в алгоритме Грэхэма )))

Для случая с треугольниками (любые две смежные вершины имеют хотя бы 1 общую смежную) могу предложить достаточно простой алгоритм решения задачи.

Это хорошо )) Предложите , пожалуйста ! ))

[Utkin]

http://bse.sci-lib.com/article091336.html