дводольні графи

Граф називається дводольним, якщо безліч його вершин можна так розбити на дві підмножини, щоб кінці кожного ребра належали різним підмножини. Ці підмножини називаються частками. Таким чином, кожна з часткою породжує порожній підграф. Прикладом двудольного графа є проста ланцюг при будь-якому : Одна частка породжується вершинами з парними номерами, інша - з непарними. Граф - приклад графа, яка не є дводольним: при будь-якому розбитті безлічі його вершин на дві підмножини в одному з цих підмножин виявляться дві суміжних вершини.

Прикладне значення поняття двудольного графа пов'язано з тим, що за допомогою таких графів моделюються відносини між об'єктами двох типів, а такі відносини часто зустрічаються на практиці (наприклад, ставлення "продукт використовується у виробництві вироби "Між вихідними продуктами і готовими виробами, або" працівник володіє професією "Між працівниками і професіями). У математиці такі відносини теж нерідкі, один з найбільш поширених їх видів - відносини інцидентності. Нехай - безліч, а - сімейство його підмножин. елемент і безліч інцідентни один одному, якщо . Ставлення инцидентности можна описати за допомогою двудольного графа , в котрому , . на Мал. 3.3 показаний граф відносини інцидентності для , , де , , , .

Взагалі кажучи, розбиття множини вершин двудольного графа на частки можна здійснити не єдиним способом. Так, в графі з тільки що наведеного прикладу можна взяти в якості часткою безлічі і . У той же час в самому визначенні цього графа вже закладено "природне" розбиття на частки і . Дводольні графи, що виникають в додатках, нерідко бувають задані саме так - з безліччю вершин, спочатку складається з двох частин, і з безліччю ребер, кожне з яких з'єднує вершини з різних частин.

Якщо розбиття на частки не задано, то може виникнути питання, чи існує воно взагалі, тобто чи є даний граф дводольним? Якщо в графі вершин, то є розбиття множини вершин на дві підмножини і безпосередня перевірка всіх цих розбиття буде дуже трудомісткою справою. Наступна теорема дає критерій дводольних, а з її докази можна витягти і ефективний алгоритм перевірки дводольних. Детально такий алгоритм буде описаний в "Пошук в ширину" .

Теорема 5. Наступні твердження для графа рівносильні:

Доказ.

Доведемо, що з (1) слід (2). нехай - двочастковий граф, в якому вибрано деякий розбиття на частки, - цикл довжини у графі . при будь-якому вершини і суміжні і, отже, належать різним часткам. Таким чином, одна частка складається з усіх вершин з непарними індексами, тобто , Інша - з усіх вершин з парними індексами. але вершини і теж суміжні і повинні належати різним часткам. отже, - парне число.

Очевидно, що з (2) випливає (3); залишається довести, що з (3) випливає (1). Розглянемо граф , В якому немає простих циклів непарної довжини. Ясно, що граф, в якому кожна компонента зв'язності - двочастковий граф, сам двочастковий. Тому можна вважати, що граф зв'язний. Зафіксуємо в ньому деяку вершину і доведемо, що для будь-яких двох суміжних між собою вершин і має місце рівність . Дійсно, припустимо спочатку, що . нехай - найкоротший шлях з в - найкоротший шлях з в . Ці шляхи починаються в одній вершині: , А закінчуються в різних: , . Тому знайдеться таке , що і при всіх . Але тоді послідовність є простим циклом довжини . отже, . Припустимо, що . якщо - найкоротший шлях з в , То, очевидно, що - найкоротший шлях з в , Отже, . Отже, відстані від двох суміжних вершин до вершини розрізняються рівно на одиницю. Тому, якщо позначити через безліч всіх вершин графа, відстань від яких до вершини парне, а через безліч всіх вершин з непарними відстанями до , То для кожного ребра графа один з його кінців належить множині , Інший - безлічі . Отже, граф - двочастковий.

нехай - цикл в графі . Безліч вершин циклу породжує в підграф, який містить всі ребра цього циклу, але може містити і ребра, йому не належать. Такі ребра називають хордами циклу . Простий цикл, який не має хорд, - це породжений простий цикл. У графі, зображеному на Мал. 3.4 , Хордами циклу є ребра , і , А цикл - породжений простий цикл. Зауважимо, що будь-який цикл довжини є породженим простим циклом.

нехай - простий цикл довжини в деякому графі, - хорда цього циклу. ребро разом з ребрами циклу утворює два циклу меншої довжини, і (Див. Мал. 3.5 ), Сума довжин яких дорівнює .

Значить, якщо - цикл непарної довжини, то один з циклів , теж має непарну довжину. Звідси випливає, що в графі, в якому є цикл непарної довжини, є і породжений простий цикл непарної довжини. Тому критерій дводольні справедливий і в наступному формулюванні.

Слідство .Граф є дводольним тоді і тільки тоді, коли в ньому немає породжених простих циклів непарної довжини.