Паросочетания

Пусть Г (V,E) - граф и - некоторое множество ребер в нем.

Множество S называется паросочетанием, если любые два ребра из него не имеют общей вершины, т.е. не являются смежнымы.

Множество из одного ребра тоже будем называть паросочетанием, как всякое пустое множество.

Паросочетание называется максимальным, если к нему нельзя добавить ни одного ребра так, чтобы снова получилось паросочетание.

Паросочетание называется наибольшим, если оно состоит из наибольшего возможного количества ребер.

Каждое наибольшее паросочетание является максимальным; обратное неверно (см. рис.36).

а) б)

Рис. 36. Паросочетания: а – максимальное; б – наибольшее и максимальное

Поиск наибольшего паросочетания в графе представляет собой классическую алгоритмическую задачу. Существуют разные варианты задач, например:

- наибольшее паросочетание по количеству дуг;

- наибольшее паросочетание по сумме весов этих дуг;

- наибольшее паросочетание в двудольных графах;

- наибольшее паросочетание в произвольном или простом графе.

Рассмотрим ее решение не для общего случая, а для графов частного вида - графов двудольных.

Граф Г (V,E) называется двудольным, если его множество вершин A можно представить в виде объединения двух его непустых подмножеств без общих элементов так, что любое ребро из E будет иметь один конец в , а другой конец - в . Таким образом, нет ни одного ребра, которое соединяло бы вершины из или соединяло бы вершины из .

Если считать, что , то двудольный граф можно описать не только матрицей смежностей, но и матрицей двудольного графа: эта матрица – размером и, если обозначать ее общий элемент через , то полагают

Такая матрица описывает граф однозначно, хотя является намного меньшей по объему, чем матрица смежностей графа в этом случае.

Когда множество состоит из вершин, а множество состоит из вершин и в двудольном графе проведены все возможные ребра, то говорят, что двудольный граф является полным двудольным графом и обозначают его символом .