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

рис.1. Двудольный граф.

Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего, если множество его вершин можно разбить на две части U \cup V = W, |U|>0, |V|>0, так, что

  ни одна вершина в U не соединена с вершинами в U и

  ни одна вершина в V не соединена с вершинами в V

Двудольный граф называется полным, если для каждой пары вершин u \in U, v \in V существует ребро (u,v) \in E. Для |U|=i, |V|=j

такой граф называется K_{i, j}

 

 

Свойства

 

    Граф является двудольным  тогда и только тогда, когда  он не содержит цикла нечётной  длины. Поэтому двудольный граф  не может содержать клику размером  более 2.

    Граф является двудольным  тогда и только тогда, когда  он 2-раскрашиваем (то есть его  хроматическое число равняется  двум)

    Граф разбивается на  пары разноцветных вершин тогда  и только тогда, когда любые  k элементов одной из долей связаны по крайней мере с k элементами другой (Теорема Холла).

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

Проверка двудольности

Проверка двудольности с помощью чётности расстояний

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

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

Заметим, что граф Кm. n имеет ровно m + n вершин и mn ребер.

Обозначение. Кm. N

Определение. Если в двудольном графе  каждая вершина из V1 соединена с каждой вершиной из V2, то граф называется полным двудольным.

Пример

 На рис.31  изображены двудольные  графы.

Примеры

1. «Задача о трёх колодцах»

В некоторой деревне есть три  колодца. Трое жителей, живущие в  трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?

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

2 «Пять хуторов расположены в вершинах правильного пятиугольника. Нужно проложить дороги от каждого из них к остальным так, чтобы не было перекрестков.»

 

3. Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!» «Не может быть этого», - ответил приятелю Витя Иванов, победитель олимпиады. Почему он так ответил?

Решение. Представим всех ребят в  классе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины  будет выходить по семь ребер. Сумма  степеней вершин графа будет равна 25x7=175. Это нечетное число. А нам  известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

4. . В стране 15 городов, каждый соединен дорогами не менее чем с 7-ю другими. Докажите, что из любого города можно проехать в любой другой либо напрямую, либо через один промежуточный город.

Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью  городами В1, В2, …, В7, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В1, В2, …, В7, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.

5. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

 

Решение. В графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам – красным. Каждое ребро графа соединяет  ровно две вершины: одну синюю  и одну красную. Пусть всего x красных  и y синих вершин (x+y=28 – уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно 3x, с другой – 4y. Получим уравнение №2: 3x=4y. Решая систему из двух уравнений, легко найти, что x=16 а y=12.

6. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

Решение: в любом графе существуют две вершины с одинаковой степенью. Изобразим класс в виде графа, вершины которого – ученики, а ребрами соединены только те вершины, которые обозначают знакомых. В этом графе есть две вершины с одинаковой степенью, следовательно, в классе есть двое ребят с одинаковым числом знакомых.

7. Двудольный граф представляет возможные варианты 4 групп крови у ребенка супругов, один из которых имеет кровь II группы (тип АО), а второй произвольного типа Х. Изолированная вершина ВВ означает невозможность появления такого типа крови ни при каком Х.

Таблица 1

Может отдавать кровь группа Может принимать кровь группы

ОО - I группа I           I, II, III, IV                                           I

АА и АО - II группа    II  II, IV                                               I, II

ВВ и ВО - III группа   III, III, IV                                              I, III

АВ - IV группа             IV , IV                                                 I, II, III, IV