Интересная гипотеза об асимптотике Куна

Revision ru3, by AndreyPavlov, 2023-01-11 21:39:13

Предистория

Недавно писал решение на свою задачу (ниже приложен мэшап, где она находится). Обычная задача на паросочетания, и в полученном графе очень быстро искалось максимальное паросочетание, что показалось мне странным (а также я не знаю как строго доказывать такую скорость) и поэтому я решил написать этот пост.

Краткая формулировка задачи

Дан ориентированный граф на $$$n$$$ вершинах и $$$m$$$ ребрах, нужно разбить граф на минимальное количество путей. Особенностью данного графа является то, что его диаметр $$$^\dagger$$$ можно оценить как $$$O(log(n))$$$.

$$$^\dagger$$$ Диаметром графа называется максимальное кратчайшее расстояние среди всех пар вершин.

Очевидно, что данная задача является учебной — нужно дублировать вершины и провести ребра графа в новом двудольном графе. Ответом будет $$$n - x$$$, где $$$x$$$ — максимальное паросочетание в получившемся двудольном графе.

Почему так быстро?

Казалось бы, при ограничениях $$$n = 10^5, m = 10^6$$$ Кун будет работать $$$O(n \cdot m)$$$, что очень долго. Но на реальном графе Кун работает ~$$$100$$$ мс.

Лично я не знаю, как доказывать такую асимптотику, но моя гипотеза, что у Куна есть ограничение на количество проделанных операций. И данное ограничение можно оценить как $$$O(n \cdot d)$$$, где $$$d$$$ — диаметр графа.

Вот ссылка на мэшап, где можно протестировать Куна.

Интересно услышать ваше мнение насчёт данной гипотезы.

Tags алгоритм куна, скорость, почему так?, асимптотика, паросочетания, быстродействие

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian AndreyPavlov 2023-01-12 10:22:24 845 Мелкая правка: 'n~~~~~\n\nОптимизаци' -> 'n~~~~~\n\n#### Оптимизаци'
ru4 Russian AndreyPavlov 2023-01-12 10:12:54 6 Мелкая правка: 'ть как $O(n \cdot d)$' -> 'ть как $O((n + m) \cdot d)$'
ru3 Russian AndreyPavlov 2023-01-11 21:39:13 2
ru2 Russian AndreyPavlov 2023-01-11 21:36:55 0 (опубликовано)
ru1 Russian AndreyPavlov 2023-01-11 21:36:00 1577 Первая редакция (сохранено в черновиках)