Графы и маршруты — страница 2
Выбирать представление графа, обход и алгоритм пути по требованиям к рёбрам и весам.
Объяснения и разобранные примеры
Матрица достижимости: как проверить сжатие ориентированного графа
Построить булево транзитивное замыкание матрицы смежности, проследить этапы по промежуточной вершине и проверить компоненты и прямые дуги конденсации
Сколько полных назначений разрешает совместимость: перманент без знаков перестановок
Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.
Как стек Хиерхольцера собирает маршрут из использованных рёбер
Построить эйлеров маршрут стеком Хиерхольцера и независимо проверить точное совпадение мультимножества пройденных и исходных рёбер.
Какая стрелка зависимости лишняя: сохранение всех достижимых пар
Построить транзитивную редукцию DAG и проверить, что удаление прямых избыточных дуг сохранило все направленные зависимости по путям.
Чётной суммы мало: как построить граф по заданным степеням
Проверить графичность списка степеней и построить одну помеченную реализацию простого графа методом Хавела — Хакими.
Минимум цветов требует двух доказательств: раскраски и отказа меньшего числа
Найти точное хроматическое число малого простого графа ограниченным полным поиском и предъявить проверяемую раскраску.
Сколько разных остовов соединяет граф: определитель вместо выбора одного дерева
Посчитать все остовные деревья заданного простого графа через кофактор лапласиана и отличить этот результат от поиска минимального остова.
Проверить на своих данных
Откройте подходящий инструмент и попробуйте свои данные.
Кратчайший путь поиском в ширину
Путь с минимальным числом рёбер в заданном невзвешенном графе, включая недостижимые вершины.
Открыть инструментПорядок зависимостей и поиск цикла
Топологический порядок ориентированного ациклического графа либо конкретный замкнутый путь, мешающий такому порядку.
Открыть инструментМаксимальный поток и сертификат минимального разреза
По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.
Открыть инструментКритический путь: ранние и поздние сроки работ
Рассчитать минимальную длительность проекта с зависимостями, резервы работ и все критические вершины в ациклической сети.
Открыть инструментКомпоненты сильной связности и граф конденсации
Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.
Открыть инструментЧисло полных двудольных назначений: перманент по Райзеру
Посчитать все допустимые взаимно однозначные назначения по квадратной матрице совместимости 0/1, используя включения и исключения по подмножествам столбцов.
Открыть инструментЭйлеров маршрут: каждое ребро ровно один раз
Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.
Открыть инструментТранзитивная редукция зависимостей DAG
Удалить из ориентированной ациклической сети лишь те прямые дуги, для которых уже существует обходной направленный путь.
Открыть инструментРеализовать степени простого графа методом Хавела — Хакими
Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.
Открыть инструментТочное хроматическое число малого графа
Найти минимальное число цветов для простого графа до 8 вершин и предъявить допустимую раскраску, перебирая ограниченное число состояний.
Открыть инструментЧисло остовных деревьев по теореме Кирхгофа
Посчитать все разные остовные деревья неориентированного графа точным определителем кофактора лапласиана.
Открыть инструментЧастые вопросы
Как работать с темой «Графы и маршруты»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.