Графы и маршруты
Выбирать представление графа, обход и алгоритм пути по требованиям к рёбрам и весам.
Объяснения и разобранные примеры
Почему поиск в ширину находит кратчайший путь в невзвешенном графе
Почему поиск в ширину находит кратчайший путь в невзвешенном графе. BFS обходит достижимые вершины слоями с помощью FIFO-очереди.
Как состояние вершины помогает обнаружить цикл ориентированного графа
состояние вершины помогает обнаружить цикл ориентированного графа. В DFS ориентированного графа полезны состояния: не посещена, активна в текущей ветви, обработана.
Почему алгоритму Дейкстры нужны неотрицательные веса
Почему алгоритму Дейкстры нужны неотрицательные веса. Алгоритм Дейкстры последовательно фиксирует вершину с минимальной текущей оценкой расстояния и улучшает оценки соседей.
Когда список смежности выгоднее матрицы
Когда список смежности выгоднее матрицы. Списки смежности хранят существующие соседства и обычно требуют O(V+E) памяти.
Почему предел целого зависит от языка и представления
Почему предел целого зависит от языка и представления. Предел целого зависит от типа и языка.
Как ослабление рёбер работает с отрицательными весами
ослабление рёбер работает с отрицательными весами. Ослабить ребро u→v — значит проверить, не короче ли путь через u, и при необходимости уменьшить расстояние до v.
Почему нечётный цикл мешает раскрасить граф в два цвета
Почему нечётный цикл мешает раскрасить граф в два цвета. В двудольном неориентированном графе вершины разделяются на две группы, а каждое ребро соединяет разные группы.
Как степени вершин и связность проверяют обход каждого ребра
степени вершин и связность проверяют обход каждого ребра. Эйлеров маршрут проходит каждое ребро ровно один раз; вершины при этом могут повторяться.
Как промежуточная вершина обновляет расстояния между всеми парами
промежуточная вершина обновляет расстояния между всеми парами. Алгоритм Флойда — Уоршелла ищет расстояния между всеми парами вершин.
Как границы графем помогают считать пользовательские символы
границы графем помогают считать пользовательские символы. Расширенный графемный кластер объединяет последовательность кодовых точек, которую обычно удобно обрабатывать как один видимый текстовый элемент.
Почему путь через все вершины не равен пути через все рёбра
Почему путь через все вершины не равен пути через все рёбра. Гамильтонов путь посещает каждую вершину ровно один раз.
Чем минимальное остовное дерево отличается от кратчайших путей
Чем минимальное остовное дерево отличается от кратчайших путей. Минимальное остовное дерево соединяет все вершины связного неориентированного взвешенного графа без циклов и имеет наименьшую сумму весов рёбер среди таких деревьев.
Как порядок без входящих рёбер решает зависимости в ациклическом графе
порядок без входящих рёбер решает зависимости в ациклическом графе. Для зависимостей «сначала А, затем Б» топологический порядок ставит А раньше Б.
Как система непересекающихся множеств поддерживает компоненты связности
система непересекающихся множеств поддерживает компоненты связности. Система непересекающихся множеств, или DSU, хранит разбиение объектов на группы.
Точка сочленения: когда удаление вершины разделяет граф
Точка сочленения: когда удаление вершины разделяет граф. Точка сочленения — вершина неориентированного графа, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности.
Паросочетание: как чередующийся путь увеличивает число пар
Паросочетание: как чередующийся путь увеличивает число пар. Паросочетание выбирает рёбра так, чтобы ни одна вершина не участвовала в двух выбранных парах.
Число путей в DAG: складываем способы, а не длины
Число путей в DAG: складываем способы, а не длины. Для подсчёта направленных путей из заданного старта в DAG его вершины обрабатывают в топологическом порядке.
Поток и разрез: как получить проверяемую верхнюю границу
Поток и разрез: как получить проверяемую верхнюю границу. Разрез делит вершины потоковой сети на две группы: источник находится в первой, сток — во второй.
Мост графа: удаление какого ребра разрывает связность
Мост графа: удаление какого ребра разрывает связность. Мост — ребро неориентированного графа, удаление которого увеличивает число компонент связности.
Длиннейший путь в DAG: когда работает топологический порядок
Длиннейший путь в DAG: когда работает топологический порядок. В ориентированном ациклическом графе максимальную сумму весов пути из заданного старта находят одним проходом по топологическому порядку.
Остаточная сеть: зачем потоку обратные рёбра
Остаточная сеть: зачем потоку обратные рёбра. Остаточная сеть показывает, как ещё можно изменить текущий поток.
Сильные компоненты: какие вершины взаимно достижимы
Сильные компоненты: какие вершины взаимно достижимы. В компоненте сильной связности любая вершина достижима из любой другой по направлению рёбер.
Как подтвердить максимальный поток минимальным разрезом
Найти поток увеличивающими путями, сохранить обратные остаточные дуги и проверить оптимальность равенством ёмкости разреза.
Как вычислить резервы работ двумя проходами по зависимостям
Определить ранние и поздние сроки работ ациклического проекта, общую длительность и резервы при неограниченной параллельности ресурсов.
Проверить на своих данных
Откройте подходящий инструмент и попробуйте свои данные.
Кратчайший путь поиском в ширину
Путь с минимальным числом рёбер в заданном невзвешенном графе, включая недостижимые вершины.
Открыть инструментПорядок зависимостей и поиск цикла
Топологический порядок ориентированного ациклического графа либо конкретный замкнутый путь, мешающий такому порядку.
Открыть инструментМаксимальный поток и сертификат минимального разреза
По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.
Открыть инструментКритический путь: ранние и поздние сроки работ
Рассчитать минимальную длительность проекта с зависимостями, резервы работ и все критические вершины в ациклической сети.
Открыть инструментКомпоненты сильной связности и граф конденсации
Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.
Открыть инструментЧисло полных двудольных назначений: перманент по Райзеру
Посчитать все допустимые взаимно однозначные назначения по квадратной матрице совместимости 0/1, используя включения и исключения по подмножествам столбцов.
Открыть инструментЭйлеров маршрут: каждое ребро ровно один раз
Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.
Открыть инструментТранзитивная редукция зависимостей DAG
Удалить из ориентированной ациклической сети лишь те прямые дуги, для которых уже существует обходной направленный путь.
Открыть инструментРеализовать степени простого графа методом Хавела — Хакими
Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.
Открыть инструментТочное хроматическое число малого графа
Найти минимальное число цветов для простого графа до 8 вершин и предъявить допустимую раскраску, перебирая ограниченное число состояний.
Открыть инструментЧисло остовных деревьев по теореме Кирхгофа
Посчитать все разные остовные деревья неориентированного графа точным определителем кофактора лапласиана.
Открыть инструментЧастые вопросы
Как работать с темой «Графы и маршруты»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.