Что такое двудольный граф
Двудольный граф (теория графов)
Содержание
Определение
Двудольный граф называется полным, если для каждой пары вершин 
существует ребро 
. Для
Свойства
Проверка двудольности
Алгоритм Хопкрофта — Карпа
Применения
См. также
Полезное
Смотреть что такое «Двудольный граф (теория графов)» в других словарях:
Чётный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия
Двудольный граф — Биграф Двудольный граф или биграф это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия
Граф ожидания — (или граф ожидания транзакций) инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой … Википедия
ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… … Химическая энциклопедия
Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия
Двудольные графы. Проверка графа на двудольность
Определение двудольного графа
Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.
Существует ещё один признак двудольности графа: граф является двудольным тогда и только тогда, когда в нём отсутствуют циклы нечётной длины.
Проверка графа на двудольность
Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS.
Начинаем покраску с произвольной вершины, которую красим в произвольный цвет. При прохождении по каждому ребру красим следующую вершину в противоположный цвет. Если при переборе соседних вершин мы нашли вершину, уже покрашенную в тот же цвет, что и текущая, то в графе существует нечётный цикл, а значит, он не является двудольным.
Реализация
Хроматическое число графа
Определение двудольных графов обобщается на произвольное количество цветов. Хроматическим числом графа называется минимальное количество цветов, в которые можно покрасить его вершины так, чтобы каждое ребро соединяло вершины различного цвета. Хроматическое число двудольных графов равно \(2\), а хроматическое число графа, изображённого ниже, равно \(3\).
Задача проверки возможности покраски графа \(k\) цветами при \(k \ge 3\) не имеет эффективного (полиномиального) решения. Единственным доказанным решением является полный перебор всех покрасок за \(O(k^N)\). Эта задача является классической NP-полной (не имеющей полиномиального решения) задачей.
brestprog
Олимпиадное программирование в Бресте и Беларуси
Что такое двудольный граф
Получите 30₽ за публикацию своей разработки в библиотеке «Инфоурок»
и получить бесплатное свидетельство о размещении материала на сайте infourok.ru
Попробуйте УМНЫЙ ПОИСК по курсам повышения квалификации и профессиональной переподготовки
Граф называется двудольным, если его вершины можно разбить на две группы (две доли) так, что каждое ребро в этом графе соединяет вершины, принадлежащие разным группам.
Двудольный граф удобно изображать, нарисовав отдельно вершины двух долей.
Пример.
На школьном балу каждый мальчик станцевал с тремя девочками, а каждая девочка — с четырьмя мальчиками.
Этот граф может выглядеть следующим образом:
Не все графы являются двудольными. Например, граф с тремя вершинами, в котором каждые две вершины соединены ребром, не является двудольным.
Утверждение.
Сумма степеней всех вершин одной доли двудольного графа равна сумме степеней всех вершин другой его доли и равна общему числу рёбер в двудольном графе.
ЗАДАЧА 1. (Поиск количества вершин в одной доле по известным степеням всех вершин и количеству вершин в другой доле.)
На школьном балу каждый мальчик станцевал с тремя девочками, а каждая девочка — с четырьмя мальчиками. Сколько мальчиков пришло на бал, если всего было 9 девочек?
РЕШЕНИЕ.
Пусть на бал пришли х мальчиков.
Каждая девочка станцевала ровно с 4 мальчиками. Значит, степень каждой вершины в левой доле графа равна 4.
Каждый мальчик станцевал ровно с 3 девочками. Значит, степень каждой вершины в правой доле графа равна 3.
Причём в левой доле 9 вершин (9 девочек), а в правой доле – неизвестно (обозначим х).
Тогда можно составить уравнение:
х = 12.
ОТВЕТ: 12 мальчиков.
ЗАДАЧА 2. (Поиск количества вершин в одной доле по известным степеням всех вершин и количеству вершин в другой доле.)
Десять хулиганов кидали снежки в окна школы. Первый хулиган попал в окно ровно 1 раз, второй — ровно 2 раза, …, десятый — ровно 10 раз, причём никакой хулиган не попал в одно и то же окно дважды. В каждое школьное окно либо попали снежком 5 раз, либо не попали вовсе. Сколько школьных окон пострадали от снежков?
РЕШЕНИЕ.
Рассмотрим двудольный граф.
Левая доля графа состоит из 10 вершин (10 хулиганов).
Правая доля состоит из х вершин (количество пострадавших окон).
Если хулиган попал в какое-то окно, то соответствующие вершины будем соединять ребром.
Степени вершин в левой доле: 1, 2, 3, …, 10 (количество попаданий в окна каждым хулиганом).
Степень каждой «пострадавшей» вершины в правой доле графа равна 5 (т.к. в каждое окно либо попали 5 раз, либо ни разу не попали, а количество окон, которые не пострадали, нас не интересует).
Тогда можно составить уравнение:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 5 ∙ х,
х = 11.
ОТВЕТ: 11 окон.
ЗАДАЧА 3. (Равенство сумм степеней вершин в долях используется для составления уравнения.)
В школе олимпийского резерва каждый хоккеист дружит с 5 гимнастками и 5 хоккеистами из школы, а каждая гимнастка дружит с 4 гимнастками и 4 хоккеистами. Какое наименьшее суммарное количество хоккеистов и гимнасток может учиться в школе олимпийского резерва?
РЕШЕНИЕ.
Рассмотрим двудольный граф.
Вершины левой доли – это хоккеисты и хоккеистки (их количество обозначим Х). Каждый хоккеист дружит с 5 гимнастами. Тогда сумма степеней вершин левой доли равна 5Х.
Вершины правой доли – гимнасты и гимнастки (их количество обозначим Г). Каждый гимнаст дружит с 4 хоккеистами. Тогда сумма степеней вершин правой доли равна 4Г.
Эти суммы должны быть равны.
Составим уравнение:5Х = 4Г.
В этом уравнении левая часть должна делиться на 4, а правая часть должна делиться на 5.
Чтобы левая часть делилась на 4, число Х нужно брать из набора <4, 8, 12, …>.
При этом число Х должно быть больше 4, т.к. каждый хоккеист дружит с 5 хоккеистками.
Значит, число 4 не подходит.
Если Х = 8, то Г = 10.
Всего общее количество составит минимум Х + Г = 8 + 10 = 18.
Двудольный граф (теория графов)
Содержание
Определение
Двудольный граф называется полным, если для каждой пары вершин существует ребро . Для
Свойства
Проверка двудольности
Алгоритм Хопкрофта — Карпа
Применения
См. также
Полезное
Смотреть что такое «Двудольный граф (теория графов)» в других словарях:
Чётный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия
Двудольный граф — Биграф Двудольный граф или биграф это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия
Граф ожидания — (или граф ожидания транзакций) инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой … Википедия
ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… … Химическая энциклопедия
Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия
Двудольный граф
Связанные понятия
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер).
В теории графов вершиной называется фундаментальная единица, образующая графы — неориентированный граф состоит из множества вершин и множества рёбер (неупорядоченных пар вершин), в то время как ориентированный граф состоит из множества вершин и множества дуг (упорядоченных пар вершин). На рисунках, представляющих граф, вершина обычно обозначается кружком с меткой, ребро — линией, дуга — стрелкой, соединяющей вершины.
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.