что такое двудольный граф
Двудольные графы. Проверка графа на двудольность
Определение двудольного графа
Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.
Существует ещё один признак двудольности графа: граф является двудольным тогда и только тогда, когда в нём отсутствуют циклы нечётной длины.
Проверка графа на двудольность
Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS.
Начинаем покраску с произвольной вершины, которую красим в произвольный цвет. При прохождении по каждому ребру красим следующую вершину в противоположный цвет. Если при переборе соседних вершин мы нашли вершину, уже покрашенную в тот же цвет, что и текущая, то в графе существует нечётный цикл, а значит, он не является двудольным.
Реализация
Хроматическое число графа
Определение двудольных графов обобщается на произвольное количество цветов. Хроматическим числом графа называется минимальное количество цветов, в которые можно покрасить его вершины так, чтобы каждое ребро соединяло вершины различного цвета. Хроматическое число двудольных графов равно \(2\), а хроматическое число графа, изображённого ниже, равно \(3\).
Задача проверки возможности покраски графа \(k\) цветами при \(k \ge 3\) не имеет эффективного (полиномиального) решения. Единственным доказанным решением является полный перебор всех покрасок за \(O(k^N)\). Эта задача является классической NP-полной (не имеющей полиномиального решения) задачей.
brestprog
Олимпиадное программирование в Бресте и Беларуси
Двудольный граф
Связанные понятия
Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является 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 элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.
Что такое двудольный граф
Получите 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 наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия
Теория графов. Основные понятия и виды графов
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
