Главная
Библиотека
Высшая математика
Дан двудольный граф с вершинами 1, 2, 3, 4 в доле X и вершинами a, b, c, d в доле Y. Матрица весов графа: ``` 0 2 3 2 0 2...

Дан двудольный граф с вершинами 1, 2, 3, 4 в доле X и вершинами a, b, c, d в доле Y. Матрица весов графа: ``` 0 2 3 2 0 2 4 4 2 0 0 0 0 3 2 5 ``` Построен остовный подграф этого графа, содержащий только ребра нулевого веса. В нем выбрано максимальное

«Дан двудольный граф с вершинами 1, 2, 3, 4 в доле X и вершинами a, b, c, d в доле Y. Матрица весов графа: ``` 0 2 3 2 0 2 4 4 2 0 0 0 0 3 2 5 ``` Построен остовный подграф этого графа, содержащий только ребра нулевого веса. В нем выбрано максимальное»

6 ноября 2025
Высшая математика

Условие:

Дан двудольный граф с вершинами 1,2,3,4 в доле \( X \), вершинами \( a \), b, c, d в доле \( Y \) и матрицей весов
\begin{tabular}{llll}
0 & 2 & 3 & 2 \\
0 & 2 & 4 & 4 \\
2 & 0 & 0 & 0 \\
0 & 3 & 2 & 5
\end{tabular}

Построен остовный подграф этого графа, содержащий только ребра нулевого веса, в нем выбрано максимальное паросочетание \( \{4 a, 3 c\} \) и проведена одна итерация алгоритма построения совершенного паросочетания. В результате получено новое весовое отображение графа. Чему равна сумма элементов, стоящих в новой матрице весов на главной диагонали?

Решение:

Рассмотрим подробно шаги решения задачи. ────────────────────────────── 1. Исходные данные – Два множества вершин: доля X: {1, 2, 3, 4} и доля Y: {a, b, c, d}. – Исходная матрица весов (строки – вершины X, столбцы – вершины Y): a b c d 1: 0 2 3 2 2: 0 2 4 4 3: 2 0 0 0 4: 0 3 2 5 ────────────────────────────── 2. Построение остовного подграфа (только ребра с нулевым весом) В матрице выбираем те ребра, у которых вес = 0. – Для вершины 1: лишь ребро 1–a (0). – Для вершины 2: ребро 2–a (0). – Для вершины 3: ребра 3–b, 3–c, 3–d (все 0). – Для вершины 4: ребро 4...