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

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

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

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

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

Читати повністю