# рассмотрение метода

рассмотрение метода построения максимального потока в сети завершено. 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; • направление на ребрах исходного графа

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа