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

Решение задачи о семи кенигсбергских мостах.

Вопрос задачи: возможно ли найти такой маршрут, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз?

В терминах теории графов эта задача может быть сформулирована так: является ли мультиграф семи кенигсбергских мостов эйлеровым графом?

Найдем степени вершин. Степень А = 3, ст. В =5, ст. D = 3, ст. С =3.

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

Ответ. Такой маршрут не существует.

Определение 27.Графназывается двудольным, если множество его вершин V можно разбить на два таких непересекающихся подмножества V₁ и V₂ , что никакие две вершины из одного и того же подмножества не соединены между собой ребрами.

Замечание. Чтобы подчеркнуть, что данный граф – двудольный, его вершины на диаграмме располагают параллельными строками или столбцами:

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

Определение 28.Двудольныйграф называется полным двудольным, если каждая вершина V₁ соединена с каждой вершиной V₂.

Обозначение: U_n,m – полный двудольный граф, множество V₁ которого содержит n вершин, а V₂ – m вершин. В таком графе имеется (n ∙ m) ребер.

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

Например:

Теорема 4. Граф двудолен тогда и только тогда, когда все его простые циклы имеют четную длину. (Простые циклы – все вершины различны, начальная и конечная вершины совпадают)

С двудольными графами связана задача о назначениях. Пусть имеется несколько рабочих мест для строителей, несколько – для слесарей, какое-то число мест для маляров, монтажников и т. д. – всего m рабочих мест. С другой стороны, имеется n претендентов. Причем, некоторые из претендентов владеют несколькими профессиями. Можно ли всех претендентов обеспечить работой, и каждому из них предоставить должность в соответствии с его профессиональной подготовкой?

Понятно, что это можно сделать далеко не всегда. Во-первых, д. б. m ≥ n. Но этого мало, пусть, например, вакантными являются три места монтажника и одно место строителя. Тогда группу, состоящую из двух строителей и одного строителя – монтажника, нельзя обеспечить работой. Один из строителей окажется незанятым.

Сформулируем задачу в терминах графов. Пусть V₁ – множество претендентов, V₂ – множество вакантных рабочих мест. Вершину a из V₁ соединим ребром с вершиной b из V₂, если претендент a способен занять рабочее место b. Тогда получим двудольный граф G (рис. 9) Наша задача заключается в том, чтобы из этого графа выделить подграф G₁ , состоящий из компонент, в каждой из которых только две вершины, и эти вершины соединены ребром (рис. 10 ). G₁ – подграф назначений.

Теорема 5(необходимое и достаточное условие существования подграфа назначения)

Пусть множество V₁ двудольного графа G содержит n вершин. Для того, чтобы граф G содержал подграф назначений G₁, необходимо и достаточно, чтобы для любого подмножества , содержащего k вершин, k = 1,2,…,n , нашлось k вершин из V₂, каждая из которых соединена ребром хотя бы с одной вершиной из А.

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

Замечание 1. От ограничения m ≥ n можно отказаться и изучать вопрос о том, сколько и каких подграфов назначений с тем или иным числом компонент можно образовать из данного двудольного графа и т. д.

Замечание 2. Немецкий математик Герман Вейль называл задачу о назначениях задачей о деревенских свадьбах. В его трактовке V₁ и V₂ – это множества девушек и юношей, живущих в одной деревне, а ребра графа означают, что юноша и девушка знакомы (или симпатичны) друг с другом. Желая обеспечить каждую девушку женихом из множества знакомых (или симпатичных) парней, мы должны будем отыскать в этом двудольном графе подграф назначений.

Замечание 3. Подобно двудольным графам можно рассматривать трехдольные и k-дольные с любым k.