рассмотрение метода
рассмотрение метода построения максимального потока в сети завершено.
3.9.3. Наибольшее паросочетание в двудольном графе
Паросочетанием в неориентированном графе G=(V,E) называется произвольное множество ребер M?E, такое, что никакие два ребра из M не инцидентны одной вершине. Вершины в G, не принадлежащие ни одному ребру паросочетания, называют свободными. Граф G называют двудольным, если его множество вершин можно разбить на непересекающиеся множества - V=X?Y, X?Y=?, причем каждое ребро e?E имеет вид e=(x,y), где x?X, y?Y. Двудольный граф будем обозначать G=(X,Y,E).
Задача нахождения наибольшего паросочетания в двудольном графе сводится к построению максимального потока в некоторой сети. Рассмотрим схему сведения. На рисунке показан исходный двудольный граф G. Построим сеть S(G) с источником s и стоком t следующим образом:
• источник s соединим дугами с вершинами из множества X;
• вершины из множества Y соединим дугами со стоком t;
• направление на ребрах исходного графа
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
