Алгоритм оптимальной отрисовки графа

Цитата JoeUser @ 14.01.16, 17:05

В сообщении №9 (о непересечении).

Там всё чётко и правильно написано. Всё же непонятно в чём сомнение. Сформулируйте сами или мы с вами в чём-то запутались.

Добавлено 14.01.16, 17:12

Цитата JoeUser @ 14.01.16, 17:10

И ты умудрился его "обрезать"

Нет, я написал всё абсолютно чётко. Приведите мою цитату, кою считаете обрезаной, там и разберём подробнее.

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

Цитата JoeUser @ 14.01.16, 17:14

Славян, ты издеваешься?

Нет.

Цитата JoeUser @ 14.01.16, 17:14

В первом случае - речь идет о возможности отрисовки любого плоского графа без пересечений.

Утверждение amk - истинно.

Цитата JoeUser @ 14.01.16, 17:14

В втором случае - я специально выделил красным цветом "обрезанное".

Всё же приведите мою фразу, кою считаете неточной, ибо все они истинны и не обрезаны!

Добавлено 14.01.16, 17:22
Вот моё полное утверждение:

Цитата Славян @ 14.01.16, 16:24

П.С. полный граф на K вершинах становится непланарным уже при K>4.

Оно истинно без каких-либо добавок!

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

А как же "полный граф на K>4"?
Ну и вдогоночку ... Если утверждаешь, что истинно, нарисуй полный планарный граф с 7-ю вершинами. Линии могут быть кривыми. У меня чет не получилось.

Цитата Славян @ 14.01.16, 17:19

Оно истинно без каких-либо добавок!

Да, термин "полный", я упустил. Оно истинно без каких-либо добавок!

Цитата JoeUser @ 14.01.16, 17:32

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

А как же "полный граф на K>4"?

Эх... Вот, что он утверждал: "если граф плоский и можно рисовать рёбра кривыми, то этот плоский граф можно будет нарисовать без пересечений, даже если вершины располагать не в каких-то особых местах, а где угодно".

Цитата Славян @ 14.01.16, 17:43

Эх... Вот, что он утверждал: "если граф плоский и можно рисовать рёбра кривыми, то этот плоский граф можно будет нарисовать без пересечений, даже если вершины располагать не в каких-то особых местах, а где угодно".

Цитата JoeUser @ 14.01.16, 17:32

нарисуй полный планарный граф с 7-ю вершинами

Осилишь кривыми?

Цитата JoeUser @ 14.01.16, 18:01

Осилишь кривыми?

Опять за рыбу деньги. Написано же:

Цитата Славян @ 14.01.16, 16:24

П.С. полный граф на K вершинах становится непланарным уже при K>4.

Т.е. не существует 'полных планарных графов с 7-ю вершинами'.

Цитата Славян @ 14.01.16, 18:07

Т.е. не существует 'полных планарных графов с 7-ю вершинами'.

Цитата Славян @ 14.01.16, 17:19

Утверждение amk - истинно.

Так а что же утверждал amk? Ну то, что ты написал - истинным?

Читаем:

Цитата amk @ 01.01.16, 09:55

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

Ограничений нет, Значит любой. В том числе и ... планарный граф с 7-ю вершинами.

Цитата JoeUser @ 14.01.16, 18:21

Ограничений нет, Значит любой.

Ограничение есть - читайте внимательно - 'плоский граф'!!!

Цитата JoeUser @ 14.01.16, 18:21

В том числе и ... планарный граф с 7-ю вершинами.

Вы, наверное, хотели написать "полный планарный с 7-ю ве..."?, так вот полных плоских=планарных с 7-ю ве. не существует.

Ты меня уморил. Попытаюсь последний раз:

Цитата amk @ 01.01.16, 09:55

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

Разбираем утверждение:

1) используем кривые
2) вершины располагаем где угодно на плоскости (плоский граф)
3) граф любой, как полный так и не полный, т.к. написано только "плоский граф"

Ты утверждаешь, что это истинно. Я тебе предлагаю на плоскости нарисовать полный граф из 7 вершин, используя п.1-3 без пересечений (планарный).

Цитата JoeUser @ 14.01.16, 18:50

Ты меня уморил. Попытаюсь последний раз:

Грустно. Ну если у меня не получится, то оставлю ваши непонимания самому автору - amk, он сможет проянить, уверен!
Поехали:

Цитата JoeUser @ 14.01.16, 18:50

Ты утверждаешь, что это истинно.

Да.

Цитата JoeUser @ 14.01.16, 18:50

Я тебе предлагаю на плоскости нарисовать полный граф из 7 вершин, используя п.1-3 без пересечений (планарный).

Итак, согласно п.3 можно нарисовать и полный и не полный (это вы верно подметили). Однако условие планарности накладывает ограничение на многообразие таких полных, коих не много остаётся в этом классе, а именно только с 1..4 вершинами туда входят. Когда же вершин более 4-х, то граф перестаёт быть плоским, а значит происходит нарушение п.3 и мы вываливаемся из области действия трёх условий. Уф... как-то так.

Цитата Славян @ 14.01.16, 19:00

Итак, согласно п.3 можно нарисовать и полный и не полный (это вы верно подметили). Однако условие планарности накладывает ограничение на многообразие таких полных, коих не много остаётся в этом классе, а именно только с 1..4 вершинами туда входят. Когда же вершин более 4-х, то граф перестаёт быть плоским, а значит происходит нарушение п.3 и мы вываливаемся из области действия трёх условий. Уф... как-то так.

Просьба была не выкручиваться, приплетая измышления и домыслы, и дополнительные ограничения, которых нет в утверждении фактически. А нарисовать. Вобщем. Сколько волка не корми, а утро вечера мудренее. Забили.

Цитата JoeUser @ 14.01.16, 18:50

2) вершины располагаем где угодно на плоскости (плоский граф)

Нет термина "плоский граф", но достаточно очевидно, что в данном случае под плоским понимался планарный.

JoeUser, вместо того, чтобы выяснить, что подразумевалось под словами "плоский граф", ты затеял тут непонятно что. Как заметил OpenGL, такого термина не существует, но слово-то написано, значит какие-то ограничения под ним подразумеваются.
Я не сверяю каждое написанное слово со справочниками. Я не математик, занимающийся изучением графов. Я даже по работе с графами как таковыми сталкиваюсь не часто. А если они попадаются, мне как-то не удаётся на эту тему с кем-то пообщаться (я не уверен даже, что у меня на работе кто-то помнит, что такое планарный граф). У меня память пока неплохая, но обычно я запоминаю не конкретные слова а только их смысл, а слово "планарный" означает что-то вроде "размещаемый на плоскости". Плюс слово планарный имеет кучу однокоренных с совсем другими значениями. Вот и ошибся.
Планарный граф это граф, который можно разместить на плоскости без пересечения рёбер. И утверждение моё было всего лишь о том, что перемещение вершин не вызывает появления пересечений. Всегда можно найти непрерывное отображение плоскости, переводящее одно расположение вершин в другое. Соответственно оно преобразует и рёбра, но пересечений при этом не возникнет.

Цитата OpenGL @ 15.01.16, 13:36

Нет термина "плоский граф", но достаточно очевидно, что в данном случае под плоским понимался планарный.

Да.

Цитата amk @ 16.01.16, 06:18

Вот и ошибся.

Дружище! Ошибаются все! Мне важно было выявить, что ошибка была, и где была. В деталях. И как можно было бы тоже самое сделать/выразить без ошибки. Ну и вершиной всего - решение вопросов первого сообщения. Все норм, не парься! И спасибо за участие!