?

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) (Expand)
[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) (Expand)
[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) (Expand)
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) (Expand)
[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) (Expand)
[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) (Expand)
[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)