Двудольный граф (биграф ) кратко

Привет, сегодня поговорим про двудольный граф биграф , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двудольный граф биграф , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

Содержание

• 1 Определение
• 2 Примеры
• 3 Свойства
• 4 Проверка двудольности
• 5 Применения
• 6 Вау!! 😲 Ты еще не читал? Это зря!

Биграф

Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Определение

Полный двудольный граф

Неориентированный граф называется двудольным, если множество его вершин можно разбить на две части , , , так, что

• ни одна вершина в не соединена с вершинами в и
• ни одна вершина в не соединена с вершинами в

Двудольный граф называется полным двудольным (это понятие отлично от полного графа, т.е., такого, в котором каждая пара вершин соединена ребром), если для каждой пары вершин существует ребро . Об этом говорит сайт https://intellect.icu . Для

такой граф обозначается символом .

Примеры

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

• Цикл состоящий из четного числа вершин.
• Любой планарный граф, у которого каждая грань ограничена четным количеством ребер.

Свойства

• Граф является двудольным тогда и только тогда, когда он не содержит цикла нечетной длины. Поэтому двудольный граф не может содержать клику размером более 2.
• Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум)
• Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые элементов одной из долей связаны по крайней мере с элементами другой ( Теорема Холла).
• Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным.

Проверка двудольности

Проверка двудольности с помощью четности расстояний

Для того, чтобы проверить граф на предмет двудольности, достаточно в каждой компоненте связности выбрать любую вершину и помечать оставшиеся вершины во время обхода графа (например, поиском в ширину) поочередно как четные и нечетные (см. иллюстрацию). Если при этом не возникнет конфликта, все четные вершины образуют множество , а все нечетные — .

Применения

• Сети Петри
• Граф Леви
• Теория кодирования
  • Factor graph
  • Tanner graph

Вау!! 😲 Ты еще не читал? Это зря!

• Словарь терминов теории графов
• Биекция

Надеюсь, эта статья про двудольный граф биграф , была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое двудольный граф биграф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.