Игра. Распутываем нитки

[masterok]

Вот такая игра, я скажу честно - застрял на третьем уровне, а люди вроде бы до 14 нормально доходят ! Рассказываю что тут надо делать:

Comments

[res_man]

Изоморфия графов)) Нужно сделать граф планарным)) бли, или они уже есть планарные (не помню точное определение))

[biglebowsky]

Вы полностью правы.

Графы уже планарные: "Планарный граф - граф, который может быть изображен на плоскости без пересечения ребер."
Осталось их только "распутать", т.е., сделать геометрическими:
"Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим."

http://ru.wikipedia.org/wiki/Планарный_граф

[res_man]

Вот я не помнил, есть ли в определении слово "может"))

[biglebowsky]

Я как-то раз обсуждал это на http://ban_topology.livejournal.com/ и у себя в журнале.

Пояснения по теме (via ivan_gandhi): http://ru.wikipedia.org/wiki/Планарный_граф
+ уточнение от zogmeister: Гамма алгоритм - алгоритм плоской укладки графа и проверки его на планарность. http://ru.wikipedia.org/wiki/Гамма-алгоритм.

[nemez_06]

Вся эта научно обоснованая хрень сложена в группы. Смотрите кучу в группе и ничего тут сложного нет. просто возьмите попорядку парочку шариков и потаскав определите центральный блок группы. Блок блок и парочка в окружности всех групп.

[biglebowsky]

Я очень тупой, нифига не разбираюсь в топологии etc.

Помянутый мной гамма-алгоритм выглядит, нарпимер, так (результат гугления по теме):
Иринёв Антон, Каширин Виктор "Алгоритм плоской укладки графов" http://rain.ifmo.ru/cat/data/theory/graph-coloring-layout/layout-2006/article.pdf

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

[nemez_06]

Всё гениальное просто. Берём обыкновеную логику. Как вообще рисуются эти головоломки? Берутся несколько точек соединяются линиями, точки перетягиваются на приглянувшеся место. Чтобы усложнить головоломку берутся несколько готовых групп точек и соединяются между собой. Потом точно так же растягиваются на приглянувшееся место. Для решения нужно найти группы и их место.

трассировка плат

[izyumcity]

теория графов.Принцип простой: для каждой точки вычисляем коэфициент (количество соединений)
Точку с максимальмым количеством соединений ставим в центр к нему подтягиваем ближайшие. Цель: минимальная длинна линий.
Далее по кругу методом проб и ошибок. Это теория. Так работает трассировка плат на компьютере.
На самом деле на практике фигня а не трассировка получается - потом ее доводят вручную.
Ручками подобное упражнение лучшее получается примерно так:
- примерно, выбираем точку с максимальным количеством линий - не важно если ошибешся, тут единственно - правильного варианта нет.
- подтягиваем к ней ближайшие
- стараемся разбить на группы с минимальным соединением между группами.
Ну и так далее, истины тут нет - вариантов бесконечное множество.
На самом деле задача довольно сложная: Результат подобного инженеринга - десятки тысяч долларов:
Двухстороняя плата стоит в 2 раза дешевле трех слойной. То есть если инженер сумел убрать пересечения -каждый телефон получается на 10-20$ дешевле.

[vitos_ip]

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

[gibajd]

дошел до 6-го. надоело :)

Когда-то заходил дальше - на 1-2 уровня.. :) - помню, точек было совсем много..