Дан двудольный граф с вершинами 1,2,3 в первой доле, вершинами a, b, c во второй доле и ребрами 1a, 1c, 2a, 2b, 3b, 3c. На графе задано паросочетание {1a, 3b}. Сколько на графе имеется увеличивающих данное паросочетание цепей, ведущих из первой доли во

6 ноября 2025
Теория вероятностей

Условие:

Дан двудольный граф с вершинами 1,2,3 в первой доле, вершинами a, b, c во второй доле и ребрами 1a, 1c, 2a, 2b, 3b, 3c. На графе задано паросочетание {1a, 3b}. Сколько на графе имеется увеличивающих данное паросочетание цепей, ведущих из первой доли во вторую?

Решение:

Рассмотрим граф с первой долей {1, 2, 3} и второй долей {a, b, c}. Задано паросочетание M = {1a, 3b}. Напомним, что увеличивающий путь (цепь) – это путь, который начинается с вершины, не покрытой паросочетанием, и заканчивается вершиной, не покрытой паросочетанием, и в котором дуги попеременно не принадлежат и принадлежат M. Шаг 1. Определим, какие вершины покрыты, а какие – нет. • В первой доле: 1 и 3 покрыты (так как 1a и 3b входят в M), незакрыта вершина 2. • Во второй доле: a и b покрыты (1a и 3b), незакрыта вершина c. Таким образом, увеличивающий путь должен начинаться из вершины 2 (пе...