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

[spamsink]

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

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

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

Comments

[yatur.livejournal.com]

Сеть становится запутанной (трудной для понимания), если граф нельзя расположить на плоскости без самопересечений. Чем больше самопересечений, тем запутаннее.

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

[spamsink]

Подсчет минимального необходимого количества самопересечений - NP-сложная задача. Критерий правильный (если к нему как-нибудь добавить тай-брейкер - собственно размер графа), но уж очень непрактичный.

[artirm.livejournal.com]

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

[spamsink]

Непосредственно попасть или вообще попасть?

[artirm.livejournal.com]

Непосредственно. Мне моя интуиция так подсказывает :-)
А вообще, я думал что городов типа Норильск нету, и вообще попасть можно из любого в любой.

[spamsink]

Да, среднее (или, ради учета и размера схемы тоже, суммарное) ветвление - одно из первых, что приходит в голову.

[yatur.livejournal.com]

> Подсчет минимального необходимого количества самопересечений - NP-сложная задача.

А у них в графах всегда так. Все стоящие задачи - NP-полные. За редким исключением.

[sab123.livejournal.com]

Очевидно, что одну выходящую дорогу, разветвляющуюся потом на N дорог, можно рассматривать как N выходящих дорог. После чего можно небось найти какие-нибудь готовые критерии сложности графов. Скажем, цикличность. Или там поделить число дорог на число городов.

[spamsink]

Гуглить я умею; интересны именно интуитивные ответы.

[sab123.livejournal.com]

А я именно интуитивно и написал.

Ну, кстати, а с визуальной точки зрения наверное важным фактором будет структурность. Чтоб были кучки городов с тесными связями в кучке, и более редкие - между кучками.

[janatem.livejournal.com]

Да, я тоже хотел сказать, что условие о разветвлении странно. Эквивалентная формулировка состоит в том, что есть просто ориентированный граф, описываемый «схемой».

[spamsink]

Я таким образом хотел подчеркнуть отсутствие кратных ребер, не пользуясь этим термином.

[kcmamu.livejournal.com]

Наибольшее собственное число матрицы смежности.

[spamsink]

Красиво, но дорого.

[kcmamu.livejournal.com]

Выписать все простые ориентированные пути (для облегчения жизни -- не слишком длинные) и их отсортированный список скормить рекордному алгоритму сжатия. В качестве ответа взять размер сжатого файла.

[spamsink]

Это оценит не столько сложность, сколько регулярность графа. "Полный граф из 1000 узлов" рекордный (Колмогоровский) алгоритм опишет именно так.

[in200.livejournal.com]

не совсем понятно с перекрестками
если ветвящиеся дороги, имеют пересечения и часть дороги СВ совпадает с СВ то рискну предположить, что (к-во перекрестков)/(к-во городов)

[spamsink]

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

[kcmamu.livejournal.com]

В твоей модели нельзя избежать пересечений даже для трех городов: из каждого города сперва-то "выходит ровно одна" дорога, а только потом она раздваивается. Итого имеем три города 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).

[spamsink]

Ну да, но ведь это не беда.

[anatbel.livejournal.com]

Леня, у тебя, что, дороги с односторонним движением?

[spamsink]

Формально - да, но ничто не мешает оценивать сложность схемы, игнорируя разницу между "входящими" и "выходящими" дорогами.

[anatbel.livejournal.com]

Я всё же много лет занимался оптимизационными задачами на графах, так что не могу не отметить, что орграфы и просто графы - две очень большие разницы. Алгоритмы и подходы могут быть совершенно различны.

[maksa.livejournal.com]

Сложность схемы нужно оценивать визуальную или транзакционную?

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

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

[spamsink]

Скорее "визуальную". Сложность с точки зрения картографа.

[maksa.livejournal.com]

Тогда в первую очередь влияет число пересечений дорог. Которое напрямую из указанного в условиях числа не следует.

[spamsink]

Даже не столько число пересечений (если они регулярные, их и изображать можно регулярно), сколько оценка "общей запутанности". Поэтому я и прошу интуитивных оценок этого числа на базе условий. Такой оценкой может, например, быть, среднее число дорог, входящих в город, или количество всех входящих дорог ("количество ребер") минус число городов ("вершин") плюс 2 - получаем некоторое абстрактное число "граней" у графа, и т.п.

[maksa.livejournal.com]

Видимо, я не понял задачу. Потому что в моём представлении даже при постоянных упомянутых параметрах запутанность может сильно разниться. В одном крайнем случае все дороги ведут в города по соседству, и тогда схема простая, в другом все дороги ведут через полстраны, и ни одна — в город по соседству. В последнем случае и пересечений (визуально; я не имею в виду разветвления) намного больше будет, и путь сложнее прокладывать.

Хороший параметр — суммарная длина дорог, делённая на некую величину с размерностью длины, характеризующую линейные размеры области с городами. Будь то корень из площади области, среднеквадратичное расстояние от центра области до городов, среднее расстояние между городами и т. п.

[spamsink]

Когда мы начинаем говорить о соседстве не в смысле связанности дорогами, а в "физическом", о длине дорог и т.п., то это уже не "схема", а "карта".

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

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

[alex-vinokur.livejournal.com]

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

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

http://link.springer.com/article/10.1007%2FBF01070606

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

[spamsink]

Спасибо :)

[familom.livejournal.com]

Интуитивно цикломатическое число или какая-нибудь метрика по максимальным потоком из каждой вершины в каждую.

[spamsink]

Раз мы знаем не только про число вершин и дуг, но и собственно структуру, хотелось бы что-нибудь более детальное, чем цикломатическое число. Пока по соотношению детальности и легкости вычисления у нас лидирует число путей длины 2 (== сумма произведений кол-ва входящих дорог на разветвленность исходящей дороги).