4551
правка
Маршрутизация: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Существует алгоритм с полиномиальным временем выполнения, который для любой сети G (ориентированной или неориентированной) находит оптимальный коэффициент эффективности маршрутизации в отсутствие информации и соответствующий маршрут r. | '''Теорема 1. Существует алгоритм с полиномиальным временем выполнения, который для любой сети G (ориентированной или неориентированной) находит оптимальный коэффициент эффективности маршрутизации в отсутствие информации и соответствующий маршрут r.''' | ||
Теорема 2. Существует ориентированный граф G с n вершинами, такой, что opt(G) оказывается не менее | '''Теорема 2. Существует ориентированный граф G с n вершинами, такой, что opt(G) оказывается не менее <math>\Omega(\sqrt{n})</math>.''' | ||
== Применение == | == Применение == | ||