Меню Главная Случайная статья Настройки Двудольный граф Материал из https://ru.wikipedia.org Двудольный граф или биграф в теории графов — это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют. Содержание 1 Определение 1.1 Связанные определения 2 Примеры 3 Свойства 4 Проверка двудольности 5 Применения 6 См. также 7 Ссылки Определение Граф ${\displaystyle G=(W,E)}$ называется двудольным, если множество его вершин можно разбить на две части ${\displaystyle U\cup V=W}$ так, что: ни одна вершина в ${\displaystyle U}$ не соединена с вершинами в ${\displaystyle U}$; ни одна вершина в ${\displaystyle V}$ не соединена с вершинами в ${\displaystyle V}$. В этом случае, подмножества вершин ${\displaystyle U}$ и ${\displaystyle V}$ называются долями двудольного графа ${\displaystyle G}$. Связанные определения Двудольный граф называется полным двудольным (это понятие отлично от полного графа; то есть, такого, в котором каждая пара вершин соединена ребром), если для каждой пары вершин ${\displaystyle u\in U,v\in V}$ существует ребро ${\displaystyle (u,v)\in E}$. Для ${\displaystyle |U|=i,|V|=j}$ такой граф обозначается символом ${\displaystyle K_{i,j}}$. Примеры Примеры двудольных графов: любое дерево является двудольным графом; любой простой цикл, состоящий из чётного числа вершин; любой планарный граф, у которого каждая грань ограничена чётным количеством ребер. Двудольные графы естественно возникают при моделировании отношений между двумя различными классами объектов. К примеру граф футболистов и клубов: ребро соединяет соответствующего игрока и клуб, если игрок играл в этом клубе. Двудольные графы используют для описания LDPC-кодов. Свойства Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. В частности двудольный граф не может содержать клику размером более 2. Граф является двудольным тогда и только тогда, когда он 2-хроматический; то есть его хроматическое число равняется двум. Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые ${\displaystyle k}$ элементов одной из долей связаны по крайней мере с ${\displaystyle k}$ элементами другой (Теорема о свадьбах). Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным. Любой двудольный граф является совершенным. Проверка двудольности Чтобы проверить граф на двудольность, в каждой компоненте связности нужно выбрать любую вершину и помечать остальные вершины при обходе графа (например, поиском в ширину) поочерёдно как четные и нечетные (см. иллюстрацию). Если конфликты не возникают, то четные вершины образуют множество ${\displaystyle U}$, а нечётные — множество ${\displaystyle V}$. Применения Сети Петри Граф Леви Теория кодирования Factor graph[англ.] Граф Таннера См. также Словарь терминов теории графов Биекция Многодольный граф Квазидвудольный граф Ссылки Hazewinkel, Michiel, ed. (2001), Graph, bipartite, Encyclopedia of Mathematics (англ.), Springer, ISBN 978-1-55608-010-4 Information System on Graph Classes and their Inclusions: bipartite graph Weisstein, Eric W. Bipartite Graph (англ.) на сайте Wolfram MathWorld. Bipartite graphs in systems biology and medicine