Двудольные графы. Двудольным графом называют такой граф G(X Y,E), такой что

Двудольным графом называют такой граф G (X Y, E), такой что

1) X Y = ,

2)

3)

Пример двудольного графа и его матрица смежности показаны на рис. 2.35.

Рисунок 2.35

Свойства двудольного графа:

1) Множество вершин графа состоит из двух непересекающихся подмножеств таких, что внутри каждого подмножества нет смежных вершин.

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

3) Двудольный граф не имеет простых циклов нечетной длины.

Двудольные графы могут быть как ориентированными, так и неориентированными, однако большинство задач на двудольных графах ставятся и решаются так, как будто граф ориентирован. При этом предполагается, что начала дуг лежат в множестве X, а их концы в множестве Y. Матрица смежности остается такой же, что и у неориентированного двудольного графа.

Рассмотрим некоторые задачи на двудольных графах.