НОУ ІНТУЇТ | лекція | Найважливіші класи графів

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

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

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

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

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

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

Доказ.

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

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

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

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

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

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

Якщо розбиття на частки не задано, то може виникнути питання, чи існує воно взагалі, тобто чи є даний граф дводольним?