Перевірка графа на дводольність

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

Дводольний граф

Приклад дводольного графа

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

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

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

Але, як показує практика, шукати всі прості цикли незручно. Набагато простішим способом перевірки граф на дводольність являється алгоритмом, що базується на ідеї фарбування графа. Розглянемо його більш детально.

Для цього, припустимо, що у нас є два кольори, наприклад, синій і червоний. Всі сині вершини будуть належати першій частці, а червоні – другій. Звідси випливає дуже просте правило: всі вершини, суміжні з синіми повинні бути червоними, і, навпаки, всі вершини, суміжні з червоними – синіми. Отже, вибравшив в якості стартової будь-яку з вершин та пофарбувавши її в довільний колір, виконуємо глибинний обхід графа. При цьому, у тому випадку, коли ми переходимо у нову вершину, то фарбуєио її в колір відмінний від кольору попередньої вершини. Якщо ж на деякому кроці, скориставшись непереглянутим ребром, потрапимо у пофарбовану вершину, і, більше того, виявиться, що її колір збігається з кольором попередньої вершини, то це свідчить про те, що граф не є дводольним. В іншому випадку – знайдемо один з варіантів розбиття вершин графа на дві частини.

Перевірка графа на дводольність – приклад:

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

Дводольний граф - приклад

Неорієнтований граф задачі

Для цього, як зазначалося вище, вибравши в якості початкової вершину номер «1» та зафарбувавши її в синій колір, рухаємося по першому зустрічному ребру. В нашому випадку таким являється ребро . Виходячи з того, що вершину «2» ми ніколи раніше не відвідували, заходимо в неї, фарбуємо її в червоний колір і проходимо по першому не пройденому інцидентному їй ребру. Через те, що непройденних ребер, інцидентних «2», не залишилось, повертаємрся у «1».

Для вершини номер «1» виявляємо непройдене ребро і проходимо його. Оскільки «3» — нова вершина, залишаємося в ній і фарбуємо її в червоний колір. У «3» немає ребер, що залишилися непройденими, тому, аналогічним чином, повертаємося назад у стартову вершину.

І на останньому кроці, скориставшись ребром , переходимо у вершину номер «4», фарбуємо її в червоний колір і на цьому алгоритм обходу графа в глибину завершуємо (всі ребра являються пройденими а вершини переглянутими та повністю сканованими).

Розбиття вершин неорієнтованого графа на дві підмножини

Переглянувши отримане дерево, приходимо до висновку, що заданий граф є дводольним (вершини, що поєднуються одним ребром зафарбовані у різні кольори), і множина його вершини ділиться на дві підмножини наступного вигляду: , .

Блок-схема алгоритму перевірки графа на дводольність

Дводольний граф блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*