30.Двудольные графы.

Дан граф G с множествами (N,U).

Граф G называется двудодьным, если множество его вершин можно разбить на 2 подмножества, называемые долями, такие, что вершины любого ребра попадают в разные доли.G=(N1∪N2,U)-двудольный

Теорема. Для того, чтобы граф был двудольным, необходимо и достаточно, чтобы любой простой цикл этого графа имел чётную длину (количество рёбер цикла).

Доказательство. Необходимость. Предположим, что исходный граф- двудольный (i1,i2,…,in,i1)-некоторый его цикл. Множество вершин двудольного графа можно разбить на 2 подмножества так, что любое его ребро соединяет одну вершину из одного подмножества, вторую -из второго. Предположим, что вершины i1ЄNi, i2ЄN2. Вершины, удалённые от i1 на нечётное расстояние принадлежат N2, вершины, удалённые на чётное расстояние и сама вершина i2 принадлежат N1. Так как в исходном графе имеется ребро (in,i1), то в последовательности i1,…,in вершина in удалена от вершины i1 на нечётное расстояние. Учитывая ребро (in,i1) получаем, что длина цикла чётная.

Достаточность. Предположим, что любой цикл графа имеет чётную длину и покажем, что граф двудольный. Предположим, что граф связный (если это не так, то каждую компоненту связности можно рассматривать отдельно). Выбираем произвольную вершину i1 и заносим её во множествоN1, все вершины, удалённые от i1на нечётное расстояние заносим в N2, все вершины, удалённые на чётное расстояние заносим в N1. Покажем, что множества N1 и N2не имеют общих вершин. Если бы это было не так, то есть, если бы ∃ jЄ(N1∩N2), то это бы означало, что в исходном графе имеются две цепи: цепь чётной длины, соеденяющая вершины i и j, и цепь нечётной длины, соединяющая эти вершины (возможно, эти цепи имеют ещё некоторые вершины, кроме i и j).

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

Осталось показать, что любые 2 вершины, входящие в N1 и любые 2 вершины, входящие в N1, не являются смежными.

Рассмотрим доказательство для вершин из множ N2(для N1 аналогично).Из вершины i1множества N2 ведут цепи нечётной длины.

Предположим, что j1и j2 смежны в исходном графе. Это будет означать, что в исходном графе есть цикл, содержащий вершины, i1, j1,j2 нечётной длины. Получим противоречие.

Алгоритм распознования двудольности.

1.Пусть N1=N2=Выбераем произвольную вершину i и заносим её в N1(iЄN1)

2.Выбираем все такие вершины, каждая из которых смежна, по крайней мере одной вершине из N1, и заносим их в N2. Выбераем все такие вершины графа, каждая из которых смежна с вершиной из множества N2 и заносим в N1.

3.Проверяем:если N1 и N2 имеют общие вершины, то исходный граф не является двудольным. Конец работы алгоритма. Иначе переходим на шаг 4.

4. Если N1∪N2≠N, то переходим на шаг 2, и если N1∪N2=N, то граф двудольный и конец работы алгоритма.