Средняя длина st (простых) путей в ориентированном графе

11

Учитывая тот факт , что - путь перечисления является # Р-полной задачи, может ли быть эффективные методы , которые вычисляют (или , по меньшей мере , приблизительно) средняя длина - пути без перечисления их? Что если пути разрешены для пересмотра вершин?т с тsTsT

Соответствующие результаты на специальных графиках также могут быть полезны.

liuyu
источник
1
Если путям разрешено пересматривать вершины, то непростой путь подразумевает отсутствие средней длины, поскольку длина будет стремиться к бесконечности. s-T
Шаул
@ Шал, ты прав. Я думал о ударяя время случайного блуждания от до т . Но средняя длина имеет тенденцию к бесконечности , без дополнительных ограничений. sT
liuyu
это кажется очень продвинутым, рекомендую перейти на cstheory
vzn
Если я понимаю правильно, этот вопрос может представлять интерес для Вас на специальный график.
Юхо
1
кажется , что это может быть связано с максимальным потоком сети? Также обратите внимание на небольшие мировые график и различные других граф с некоторой симметрией, она будет иметь тенденцию к средней длине пути . довольно естественный алгоритм может быть случайным образом выборки кратчайших - т путей и посмотреть на стандартном отклонении результатов. sT
ВЗН

Ответы:

3

Вычисление / оценка / аппроксимация средней длины пути были изучены для некоторых моделей случайных графов, включая модель Эрдоса-Рени и масштабные свободные сети Барабаси-Альберта, а также графы малых миров Строгаца, которые могут быть подходящими в качестве приближений для ваших графов. [было бы лучше, если бы вы могли сузить / детализировать некоторые особенности / характеристики графиков, которые вы изучаете.]

ВЗН
источник
sTsTsT