Темы

Алгоритмы теории графов

Graph Theory Algorithms · 30 статей

  1. Минимальное остовное дерево графа

    Минимальное остовное дерево: алгоритм поиска кратчайших связей в графе. Применение в телекоммуникациях и других областях. Оптимизация веса сети.

    #9826 · 9 мин чтения

  2. Алгоритм Форда-Фалкерсона для вычисления максимального потока в сети

    Алгоритм Форда-Фалкерсона: вычисление максимального потока в сети и минимального разреза. Обзор метода, принцип работы и применение в графах.

    #12604 · 2 мин чтения

  3. Алгоритм поиска минимального остовного дерева

    Алгоритм Прима: поиск минимального остовного дерева в графе. Эффективный жадный алгоритм для оптимизации веса связей и построения дерева.

    #12606 · 3 мин чтения

  4. Теорема о максимальном потоке — минимальном разрезе

    Теорема о максимальном потоке — минимальном разрезе: ключевая концепция в теории оптимизации и компьютерных науках. Раскрывает связь между максимальным потоком и минимальным разрезом в сети.

    #17672 · 2 мин чтения

  5. Задача китайского почтальона и T-соединения в графах

    Задача китайского почтальона: поиск кратчайшего маршрута по всем ребрам графа. Решение, алгоритмы, эйлеров цикл и оптимизация маршрутов.

    #52473 · 4 мин чтения

  6. Алгоритм Борувки для поиска минимального остовного дерева

    Алгоритм Борůvки: нахождение минимального остовного дерева в графе. Эффективный метод, впервые предложенный в 1926 году для построения сетей.

    #57634 · 2 мин чтения

  7. Алгоритм Флойда-Уоршелла для поиска кратчайших путей

    Алгоритм Флойда-Уоршелла: поиск кратчайших путей во взвешенных графах с отриц. весами. Динамическое программирование, транзитивное замыкание.

    #63620 · 3 мин чтения

  8. Максимальный поток и задачи теории графов

    Максимальный поток в графах: определение, теорема о максимальном потоке и минимальном разрезе, алгоритм Форда-Фалкерсона. Оптимизация сетей!

    #92128 · 8 мин чтения

  9. Задача коммивояжёра об узком месте

    Задача коммивояжёра с "бутылочным горлышком": поиск оптимального гамильтонова цикла с минимальным весом самого тяжелого ребра. NP-трудная задача.

    #95490 · 2 мин чтения

  10. Остовное дерево графа

    Покрытие графа: что такое остовное дерево? Определение, свойства и применение в алгоритмах (Dijkstra, A*), сетях и телекоммуникациях.

    #101560 · 8 мин чтения

  11. Задача Штейнера о минимальном дереве на графах и сетях

    Задача Штейнера: поиск оптимального соединения объектов в графе с минимальным весом. Варианты: графы, евклидова геометрия, оптимизация сети.

    #108221 · 11 мин чтения

  12. Визуализация графов с помощью физического моделирования

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

    #136586 · 4 мин чтения

  13. Матрица расстояний: определение и применение.

    Матрица расстояний: определение, свойства и применение в математике, информатике и теории графов. N×N массив для вычисления расстояний между элементами.

    #148567 · 10 мин чтения

  14. Упорядочение вершин ориентированных ациклических графов

    Топологическая сортировка: упорядочение вершин ориентированного ациклического графа (DAG). Алгоритмы, применение в задачах планирования, проверка на циклы.

    #156856 · 5 мин чтения

  15. k-минимальное остовное дерево: сложность, приближения и геометрические варианты

    Поиск k-MST: нахождение минимального по стоимости дерева из k вершин в графе. NP-трудная задача, но поддается полиномиальной аппроксимации. Теория графов.

    #187475 · 2 мин чтения

  16. Алгоритм Джонсона для поиска кратчайших путей

    Алгоритм Джонсона: поиск кратчайших путей в графах с отрицательными весами. Использует Bellman-Ford и Dijkstra для эффективного решения задач маршрутизации.

    #202586 · 2 мин чтения

  17. Матрица Лапласа графа: представление, свойства и применение.

    Матрица Лапласа графа: определение, свойства и применение в теории графов. Расчет числа остовных деревьев, минимальные разрезы и неравенство Чигера.

    #218395 · 2 мин чтения

  18. Ребра, разрешающие все циклы в графе

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

    #258734 · 15 мин чтения

  19. Разделы графа и разрезы в теории графов

    Разделение графа на подмножества: определение разреза, ребер разреза и s-t разрезов в теории графов и потоковых сетях. Ключевые понятия и определения.

    #288082 · 3 мин чтения

  20. Поиск пути в компьютерных приложениях

    Поиск пути: алгоритмы прокладки маршрута компьютером. Основано на алгоритме Дейкстры, теории графов. Оптимизация кратчайшего пути между точками.

    #309976 · 6 мин чтения

  21. Связные доминирующие множества и максимальные остовные деревья с листьями: сложность, приближения и применимость.

    Связные доминирующие множества и остовные деревья с макс. числом листьев: NP-полные задачи теории графов. Сложность аппроксимации, алгоритмы и границы.

    #315667 · 2 мин чтения

  22. Алгоритм решения задачи назначения: от Якоби до Куна-Мункреса

    Алгоритм Куна-Мункреса (Венгерский метод) – эффективное решение задачи назначения за полиномиальное время. История, авторы (Якоби, Кёниг, Эгервари).

    #324870 · 6 мин чтения

  23. Алгоритм поиска двух непересекающихся кратчайших путей

    Алгоритм поиска двух непересекающихся кратчайших путей в графе: описание, применение в сетевой маршрутизации, алгоритмы Бхандари и Форда.

    #332985 · 4 мин чтения

  24. Достижимость вершин в графе

    Достижимость вершин в графе: определение, алгоритмы для ориентированных и неориентированных графов. Связные компоненты и проверка пути между вершинами.

    #341474 · 3 мин чтения

  25. Второе наименьшее собственное значение лапласиана графа

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

    #381755 · 2 мин чтения

  26. Минимизация разреза графа: алгоритмы и обобщения

    Минимальный разрез графа: определение, алгоритм Стоера-Вагнера для решения задачи на взвешенных графах с неотрицательными весами. Теория графов.

    #392237 · 2 мин чтения

  27. Приближённый алгоритм для задачи коммивояжёра: Алгоритм Христофидеса — Сердюкова

    Алгоритм Христофидеса для решения задачи коммивояжера: приближенное решение с гарантией 3/2 от оптимального. Подробное описание и примеры.

    #394009 · 1 мин чтения

  28. Алгоритм Дийкстры — Шольтена для обнаружения завершения в распределенных системах.

    Алгоритм Дийкстры — Шолтена: обнаружение завершения в распределенных системах. Предложен в 1980 году для древовидных структур вычислений.

    #420089 · 1 мин чтения

  29. Покрытие рёбрами графа: определение и свойства

    Покрытие рёбрами графа: определение, свойства и задача поиска минимального покрытия. Решение задачи оптимизации в теории графов и информатике.

    #450487 · 2 мин чтения

  30. Biconnected component

    #463372 · 3 мин чтения