?

Log in

No account? Create an account
Planarity - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Planarity [1 August 2005|17:02]
Oleg Eterevsky
[Tags|]
[Current Music |Bregovič]

www.planarity.net

Забавная flash-игрушка: нужно подвигать вершины планарного графа так, чтобы избавиться от пересечений рёбер. Я только что прошёл 10-й уровень.

Upd. Остановился на 13-м, когда у меня перегрузился компьютер. Забавно, что на 11-й и 12-й уровни потратил где-то по полчаса, в то время как на 10-й -- больше часа. :)
LinkReply

Comments:
[User Picture]From: c_mcd
2005-08-01 05:59 pm (UTC)
Да, хорошая вещь. Я вот до двенадцатого дошел, посмотрел на тринадцатый, - интересно, какой там предел по количеству узлов, учитывая то, что площадь экрана ограничена...
(Reply) (Thread)
[User Picture]From: eterevsky
2005-08-01 06:29 pm (UTC)
Я тоже на тринадцатом пока остановился. Если бы можно было бы перетаскивать сразу группу точек, было бы проще.
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2005-08-02 02:19 am (UTC)
Рулез. Остановился на седьмом, потом пришла пора идти домой. Сегодня продолжу.
(Reply) (Thread)
[User Picture]From: maren_nareiel
2005-08-02 06:00 am (UTC)
Аналогично :)
(Reply) (Parent) (Thread)
[User Picture]From: marinka239
2005-08-02 02:59 pm (UTC)
А чего его сегодня нет?
(Reply) (Thread)
[User Picture]From: eterevsky
2005-08-02 08:21 pm (UTC)
Чего нет?
(Reply) (Parent) (Thread)
[User Picture]From: marinka239
2005-08-03 04:33 am (UTC)
Игрушки этой. Только я хотела вечером развлечься...
(Reply) (Parent) (Thread)
[User Picture]From: marinka239
2005-08-03 04:36 am (UTC)
Ух ты ж, а сегодня снова есть
(Reply) (Parent) (Thread)
[User Picture]From: halif
2005-08-03 11:51 am (UTC)

А вопрос к математикам.

Есть ли алгоритм для такой задачи? До 10 уровня я доходил 3 раза, дальше уже слишком тесно...
Но чего я никак не могу понять - как я это делаю... Это явно некая визуальная стратегия, охватывающая сразу кучу точек. Явно используется пространственное мышление - представляю в трехмере разворот группы узлов - потом мышой затаскиваю...

Итак, вопрос математикам - есть ли алгоритм решения такой задачи?
Порылся по книжкам - нашел необходимое и достаточное условие планарности без доказательства - наличие подграфа К5 или К3,3...
(Reply) (Thread)
[User Picture]From: eterevsky
2005-08-03 12:16 pm (UTC)

Re: А вопрос к математикам.

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

Алгоритм, видимо, есть и достаточно эффективный. Докидываем вершины по одной, постоянно сохраняя непересекаемость рёбер между уже выбранными вершинами. Каждая новая вершина соединена с несколькими уже имеющимися. Если вершины, с которыми соединена данная лежат в углах одной стороны, тогда всё ok. Иначе этого можно добиться несколькими "выворачиваниями на изнанку" кусков графа. Найти нужные выворачивания с вычислительной точки зрения непросто, но, я думаю, возможно. Наконец, последняя проблема: страна, в которую нужно поместить новую вершину невыпукла. Но это достаточно возможно исправить.
(Reply) (Parent) (Thread)