?

Log in

No account? Create an account

Вопрос на теоретико-графическую интуицию - Общество дровосеков Бердичева по изучению Мишны

Aug. 5th, 2013

07:02 pm - Вопрос на теоретико-графическую интуицию

Previous Entry Share Next Entry

В стране есть города, соединенные дорогами. Дороги могут разветвляться. В каждый город может входить любое количество дорог, а выходит ровно одна.

У вас есть схема дорог, по которой можно для каждого города узнать список городов, в которые можно напрямую попасть по ведущей из него дороге, и список городов, из которых можно напрямую попасть в данный. Предложите критерий оценки сложности ("запутанности") дорожной сети согласно вашему пониманию сложности/запутанности. Как из данной схемы получить число: чем сложнее схема - тем больше число?

У этого вопроса нет "правильного" ответа. Мне просто интересно, что будет предложено.

Comments:

[User Picture]
From:yatur
Date:August 6th, 2013 02:48 am (UTC)
(Link)
Сеть становится запутанной (трудной для понимания), если граф нельзя расположить на плоскости без самопересечений. Чем больше самопересечений, тем запутаннее.

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

Edited at 2013-08-06 02:48 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 04:05 am (UTC)
(Link)
Подсчет минимального необходимого количества самопересечений - NP-сложная задача. Критерий правильный (если к нему как-нибудь добавить тай-брейкер - собственно размер графа), но уж очень непрактичный.
(Reply) (Parent) (Thread)
[User Picture]
From:artirm
Date:August 6th, 2013 04:40 am (UTC)
(Link)
При таком ограничении интуитивно остается только считать насколько сильно ветвятся исходящие дороги. Например, число городов в которые можно попасть из одного города, усреденное по всем городам и отнесенное к общему числу городов.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 05:04 am (UTC)
(Link)
Непосредственно попасть или вообще попасть?
(Reply) (Parent) (Thread)
[User Picture]
From:artirm
Date:August 6th, 2013 03:10 pm (UTC)
(Link)
Непосредственно. Мне моя интуиция так подсказывает :-)
А вообще, я думал что городов типа Норильск нету, и вообще попасть можно из любого в любой.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 03:27 pm (UTC)
(Link)
Да, среднее (или, ради учета и размера схемы тоже, суммарное) ветвление - одно из первых, что приходит в голову.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:August 6th, 2013 11:03 am (UTC)
(Link)
> Подсчет минимального необходимого количества самопересечений - NP-сложная задача.

А у них в графах всегда так. Все стоящие задачи - NP-полные. За редким исключением.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 6th, 2013 03:48 am (UTC)
(Link)
Очевидно, что одну выходящую дорогу, разветвляющуюся потом на N дорог, можно рассматривать как N выходящих дорог. После чего можно небось найти какие-нибудь готовые критерии сложности графов. Скажем, цикличность. Или там поделить число дорог на число городов.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 04:07 am (UTC)
(Link)
Гуглить я умею; интересны именно интуитивные ответы.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 6th, 2013 05:55 pm (UTC)
(Link)
А я именно интуитивно и написал.

Ну, кстати, а с визуальной точки зрения наверное важным фактором будет структурность. Чтоб были кучки городов с тесными связями в кучке, и более редкие - между кучками.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:August 6th, 2013 07:14 am (UTC)
(Link)
Да, я тоже хотел сказать, что условие о разветвлении странно. Эквивалентная формулировка состоит в том, что есть просто ориентированный граф, описываемый «схемой».
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 02:54 pm (UTC)
(Link)
Я таким образом хотел подчеркнуть отсутствие кратных ребер, не пользуясь этим термином.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:August 6th, 2013 04:15 am (UTC)
(Link)
Наибольшее собственное число матрицы смежности.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 04:30 am (UTC)
(Link)
Красиво, но дорого.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:August 6th, 2013 06:55 am (UTC)
(Link)
Выписать все простые ориентированные пути (для облегчения жизни -- не слишком длинные) и их отсортированный список скормить рекордному алгоритму сжатия. В качестве ответа взять размер сжатого файла.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 03:00 pm (UTC)
(Link)
Это оценит не столько сложность, сколько регулярность графа. "Полный граф из 1000 узлов" рекордный (Колмогоровский) алгоритм опишет именно так.
(Reply) (Parent) (Thread)
From:in200
Date:August 6th, 2013 06:31 am (UTC)
(Link)
не совсем понятно с перекрестками
если ветвящиеся дороги, имеют пересечения и часть дороги СВ совпадает с СВ то рискну предположить, что (к-во перекрестков)/(к-во городов)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 06:37 am (UTC)
(Link)
Мы не знаем реального расположения городов, нам доступна только абстрактная схема. Так, например, при 4 городах, соединенных каждый с каждым, на схеме пересечений можно избежать, а будут ли они нужны ради минимизации длины дорог, неизвестно.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:August 6th, 2013 07:07 am (UTC)
(Link)
В твоей модели нельзя избежать пересечений даже для трех городов: из каждого города сперва-то "выходит ровно одна" дорога, а только потом она раздваивается. Итого имеем три города A, B, C и три соответствующих перекрестка A', B', C'; "элементарные" дороги ведут A->A', B->B', C->C', A'->B, A'->C, B'->A, B'->C, C'->A, C'->B. Убирая ориентацию, получаем классическую картинку с тремя деревнями и тремя колодцами, т. е. K(3,3).
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 02:54 pm (UTC)
(Link)
Ну да, но ведь это не беда.
(Reply) (Parent) (Thread)
[User Picture]
From:anatbel
Date:August 6th, 2013 07:49 am (UTC)
(Link)
Леня, у тебя, что, дороги с односторонним движением?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 02:57 pm (UTC)
(Link)
Формально - да, но ничто не мешает оценивать сложность схемы, игнорируя разницу между "входящими" и "выходящими" дорогами.
(Reply) (Parent) (Thread)
[User Picture]
From:anatbel
Date:August 6th, 2013 03:14 pm (UTC)
(Link)
Я всё же много лет занимался оптимизационными задачами на графах, так что не могу не отметить, что орграфы и просто графы - две очень большие разницы. Алгоритмы и подходы могут быть совершенно различны.
(Reply) (Parent) (Thread)
[User Picture]
From:maksa
Date:August 6th, 2013 08:12 am (UTC)
(Link)
Сложность схемы нужно оценивать визуальную или транзакционную?

Если мне ехать на машине и самому прокладывать путь — то смотреть придётся на карту, а не на список маршрутов. А если, допустим, покупать билет на самолёт (ок, ок, автобус), то, очевидно, чем больше число, тем больше вероятность долететь напрямую (доехать без пересадок), и тем проще схема для меня как для пассажира.

Ну и само число может ни о чём не говорить. Если каждый город соединяет дорога с пятью ближайшими городами, то схема предельно простая. Если с пятью городами, но находящимися чёрт знает где, то крайне сложная.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 02:58 pm (UTC)
(Link)
Скорее "визуальную". Сложность с точки зрения картографа.
(Reply) (Parent) (Thread)
[User Picture]
From:maksa
Date:August 6th, 2013 03:03 pm (UTC)
(Link)
Тогда в первую очередь влияет число пересечений дорог. Которое напрямую из указанного в условиях числа не следует.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 03:23 pm (UTC)
(Link)
Даже не столько число пересечений (если они регулярные, их и изображать можно регулярно), сколько оценка "общей запутанности". Поэтому я и прошу интуитивных оценок этого числа на базе условий. Такой оценкой может, например, быть, среднее число дорог, входящих в город, или количество всех входящих дорог ("количество ребер") минус число городов ("вершин") плюс 2 - получаем некоторое абстрактное число "граней" у графа, и т.п.
(Reply) (Parent) (Thread)
[User Picture]
From:maksa
Date:August 6th, 2013 06:01 pm (UTC)
(Link)
Видимо, я не понял задачу. Потому что в моём представлении даже при постоянных упомянутых параметрах запутанность может сильно разниться. В одном крайнем случае все дороги ведут в города по соседству, и тогда схема простая, в другом все дороги ведут через полстраны, и ни одна — в город по соседству. В последнем случае и пересечений (визуально; я не имею в виду разветвления) намного больше будет, и путь сложнее прокладывать.

Хороший параметр — суммарная длина дорог, делённая на некую величину с размерностью длины, характеризующую линейные размеры области с городами. Будь то корень из площади области, среднеквадратичное расстояние от центра области до городов, среднее расстояние между городами и т. п.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2013 07:07 pm (UTC)
(Link)
Когда мы начинаем говорить о соседстве не в смысле связанности дорогами, а в "физическом", о длине дорог и т.п., то это уже не "схема", а "карта".

Сложность карты - отдельный интересный вопрос; спасибо за предложенные варианты - пригодятся, пожалуй.

(Reply) (Parent) (Thread)
[User Picture]
From:alex_vinokur
Date:August 7th, 2013 05:04 pm (UTC)

A method of storage and search of shortest path information for graphs ...

(Link)
Много лет назад я занимался похожей задачей для сети железных дорог. Там, по-моему, есть и оценка сложности.

A method of storage and search of shortest path information for graphs with designated characteristics

http://link.springer.com/article/10.1007%2FBF01070606
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 7th, 2013 06:31 pm (UTC)

Re: A method of storage and search of shortest path information for graphs ...

(Link)
Спасибо :)
(Reply) (Parent) (Thread)
From:familom
Date:August 9th, 2013 09:11 pm (UTC)
(Link)
Интуитивно цикломатическое число или какая-нибудь метрика по максимальным потоком из каждой вершины в каждую.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 9th, 2013 09:27 pm (UTC)
(Link)
Раз мы знаем не только про число вершин и дуг, но и собственно структуру, хотелось бы что-нибудь более детальное, чем цикломатическое число. Пока по соотношению детальности и легкости вычисления у нас лидирует число путей длины 2 (== сумма произведений кол-ва входящих дорог на разветвленность исходящей дороги).
(Reply) (Parent) (Thread)