Дан двудольный граф с вершинами a, b, c, d в доле X и 1,2,3,4 в доле Y, а также ребрами a1, a3, b2, b3, c3, c4, d1, d2. Выбрано максимальное паросочетание, включающее ребра d1, c3, b2, и в результате одной итерации алгоритма построения наибольшего паросочетания в двудольном графе найдено новое паросочетание. Укажите вершины смежные вершинам a, b, c, d, в найденном паросочетании.
Мы имеем двудольный граф с долями X = {a, b, c, d} и Y = {1, 2, 3, 4} и набором рёбер
a1, a3, b2, b3, c3, c4, d1, d2.
Исходное (максимальное, но не совершеное) паросочетание выбрано так, что в нём содержатся рёбра d1, c3, b2.
В нём вершина a остаётся не затронутой (то есть свободной).
Алгоритм поиска наибольшего (максимального) паросочетания в двудольном графе начинает с поиска увеличивающего пути, начиная с не затронутой вершины левой доли.
Рассмотрим шаги подробно:
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?