Графы и маршруты — страница 2

Выбирать представление графа, обход и алгоритм пути по требованиям к рёбрам и весам.

Объяснения и разобранные примеры

Проверить на своих данных

Откройте подходящий инструмент и попробуйте свои данные.

Кратчайший путь поиском в ширину

Путь с минимальным числом рёбер в заданном невзвешенном графе, включая недостижимые вершины.

Открыть инструмент

Порядок зависимостей и поиск цикла

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

Открыть инструмент

Максимальный поток и сертификат минимального разреза

По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.

Открыть инструмент

Критический путь: ранние и поздние сроки работ

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

Открыть инструмент

Компоненты сильной связности и граф конденсации

Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.

Открыть инструмент

Число полных двудольных назначений: перманент по Райзеру

Посчитать все допустимые взаимно однозначные назначения по квадратной матрице совместимости 0/1, используя включения и исключения по подмножествам столбцов.

Открыть инструмент

Эйлеров маршрут: каждое ребро ровно один раз

Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.

Открыть инструмент

Транзитивная редукция зависимостей DAG

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

Открыть инструмент

Реализовать степени простого графа методом Хавела — Хакими

Проверить графичность последовательности степеней и при успехе построить один простой граф с точным сохранением номеров вершин.

Открыть инструмент

Точное хроматическое число малого графа

Найти минимальное число цветов для простого графа до 8 вершин и предъявить допустимую раскраску, перебирая ограниченное число состояний.

Открыть инструмент

Число остовных деревьев по теореме Кирхгофа

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

Открыть инструмент

Частые вопросы

Как работать с темой «Графы и маршруты»?

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

Можно ли вернуться к более простой теме?

Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.

Продолжить изучение