Кратчайшие пути в графах

Vlad128

Как вывести хорошую оценку максимального возможного числа кратчайших путей между двумя вершинами в графе со строго положительными весами ребер (с нулями понятно http://oeis.org/A007526 ~V! )
Рассматриваем, например, случай недопустимости кратных ребер. Можно представить ромб, например, он дает два пути, а потом соединить много таких ромбов подряд, это даст 2^V-1)/3) ~ 2^V, где V — число вершин. А может быть, можно еще больше сделать?

Vlad128

Что-то вот подсказывает, что больше не выйдет, потому что нужно большое число независимых участков, а в случае с ромбами оно как раз максимизируется. Ну или можно искать максимум k^(N/k) по всевозможным k (если в ромбе проводить «диагонали»)

Vlad128

С другой стороны, я тут подумал, практического интереса в отыскании точной оценки больше нет, потому что 2^N уже достаточно, чтобы умереть (хотя бы по памяти поэтому остается чисто теоретический интерес.

Vlad128

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

Xephon

Пусть дан граф G с n вершинами, и выделенной вершиной W.
Докажем индукцией по количеству вершин в графе, что кратчайших путей из любой вершины V в вершину W не более, чем 2^n.
Определим на каждой вершине V графа функцию f(V равную длине кратчайшего пути от V до W.
Упорядочим вершины по убыванию функции f, занумеровав их V_1,V_2,...,V_n. Вершиной V_n будет, конечно, W.
Ясно, что если f(V)>=f(U то кратчайшие пути из вершины V в W не проходят через U, и поэтому кратчайшие пути из вершины V_i в вершину W проходят только по подграфу на вершинах V_i,...,V_n.
Тогда для вершин V_2,...,V_n доказываемое утверждение следует из предположения индукции. Даже точнее: T(V_i)<=2^{n-i+1}, где через T(V_i) обозначено количество путей из вершины V_i в вершину W.
Осталось доказать его для вершины V_1. Разобьём пути из вершины V_1 на подмножества — по тому, какая вершина идёт следом за V_1.
Тогда получим неравенство T(V_1)<=(сумма по всем j>1) T(V_j). Используя указанные выше неравенства T(V_i)<=2^{n-i+1}, получим как следствие, что T(V_1)<=2^n.
Оставить комментарий
Имя или ник:
Комментарий: