графы
Статьи EssayAI по теме «графы»: разборы, методы и примеры.
Алгоритм Прима - как построить остовное дерево по шагам
Разбираем, как алгоритм Прима шаг за шагом строит минимальное остовное дерево графа: идея жадного выбора, лемма о разрезе и трассировка на конкретном примере.
Хроматический полином графа: как считать и применять
Что такое хроматический полином графа, как его вычислить через теорему об удалении и стягивании ребра, свойства коэффициентов и связь с хроматическим числом. Формулы и пошаговый пример.
Максимальное независимое множество в графе: разбор
Независимое множество вершин графа: чем различаются максимальное и наибольшее множество, как связаны число независимости и вершинное покрытие, как искать ответ алгоритмами.
Задача о k-центрах в графе: постановка и алгоритмы
Что такое задача о k-центрах в графе: постановка как минимаксная задача размещения, NP-трудность, жадный 2-приближённый алгоритм Гонзалеса и связь с радиусом графа.
Эксцентриситет вершины графа: определение и расчёт
Что такое эксцентриситет вершины графа: определение через расстояние, формула, пошаговый расчёт по матрице кратчайших путей, свойства и связь с радиусом, диаметром, центром.
Метод ветвей и границ: задача коммивояжёра по шагам
Метод ветвей и границ для задачи коммивояжёра: матрица расстояний, приведение строк и столбцов, нижняя граница, дерево ветвления и отсечение бесперспективных маршрутов.
Радиус и диаметр графа: как считать эксцентриситет
Что такое радиус и диаметр графа и как через эксцентриситет вершин найти центр и периферию графа. Формулы, пошаговый пример и связь с расстояниями между вершинами.
Алгоритм Эдмондса-Карпа: поиск максимального потока
Алгоритм Эдмондса-Карпа находит максимальный поток в сети: BFS ищет дополняющий путь, что даёт полиномиальную сложность. Разбираем идею, реализацию и оценку.
Алгоритм Куна: как найти максимальное паросочетание
Алгоритм Куна шаг за шагом: ищем увеличивающие цепи обычным DFS и находим максимальное паросочетание в двудольном графе за O(V·E), с разбором идеи и сложности.
Алгоритм Тарьяна: поиск компонент связности орграфа
Алгоритм Тарьяна находит сильно связные компоненты орграфа за один проход DFS. Разбираем идею с disc и low, псевдокод и пример, чтобы вы научились раскладывать граф на SCC.
Алгоритм Дейкстры: как найти кратчайший путь в графе
Разбираем алгоритм Дейкстры на взвешенном графе по шагам: как он находит кратчайшие пути от стартовой вершины и почему ломается на ребрах с отрицательными весами.
Алгоритм Беллмана-Форда: пути с отрицательными весами
Разбираем алгоритм Беллмана-Форда: как искать кратчайшие пути в графе с отрицательными рёбрами, ловить отрицательные циклы и чем он отличается от Дейкстры.