Теорема о свадьбах (также теорема о мальчиках и девочках, теорема Холла) — утверждение о том, что в двудольном графе для любого натурального любые вершин одной из долей, где не превышает числа вершин доли, связаны по крайней мере с различными вершинами другой доли тогда и только тогда, когда граф разбивается на пары по первой доле.
Для случая регулярных графов степени теорема легко выводится из существования эйлерова цикла в каждой связной компоненте графа; на этой идее можно построить доказательство для всех регулярных графов.[2]
Вариации и обобщения
Из теоремы о свадьбах немедленно следует, что любой регулярный двудольный граф степени допускает совершенное паросочетание.
Теорема обобщается на двудольные графы с бесконечным множеством вершин, при условии, что все вершины имеют конечную степень.
Пример бесконечного двудольного графа в котором не выполняется теорема о свадьбах
Пример бесконечного двудольного графа, для которого теорема не верна — прямой цилиндрический стакан, который строится следующим образом: первая доля множества вершин — точки верхней окружности стакана и центр нижнего основания; вторая доля — точки окружности нижнего основания; рёбра графа — все радиусы нижнего основания и вертикальные отрезки боковой поверхности.
теорема Татта о паросочетаниях — обобщение теоремы о свадьбах на случай произвольных конечных, но необязательно двудольных, графов.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Двудо́льный граф или бигра́ф в теории графов — это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют.
В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.
Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество может быть разбито на попарно непересекающихся цепей, где — количество элементов наибольшей антицепи множества .
В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в различных цветов для заданного значения или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.
Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
Граф ТуранаT(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь подмножеств размером и подмножеств размером . Таким образом, это полный r-дольный граф
Теорема об упаковке кругов описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости, то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки кругов утверждает, что обратное также верно:
Задача Заранкиевича, открытая проблема в математике, задаёт вопрос о наибольшем возможном числе рёбер в двудольном графе, имеющем заданное число вершин, но не содержащего полных двудольных подграфов заданного размера. Задача принадлежит области экстремальной теории графов, ветви комбинаторики, и названа именем польского математика Казимира Заранкиевича, описавшего некоторые специальные случаи данной задачи в 1951.
Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет в худшем случае. В случае плотных графов время работы ограничивается , а для случайного графа алгоритм работает почти за линейное время.
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф Gk-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Проблема Ружи – Семереди или (6,3)-проблема спрашивает о максимальном числе рёбер в графе, в котором любое ребро принадлежит единственному треугольнику. Эквивалентно, проблема спрашивает о максимальном числе рёбер в сбалансированном двудольном графе, рёбра которого можно разбить на линейное число порождённых паросочетаний, или максимальное число троек, которые можно выбрать из точек так, что каждые шесть точек содержат максимум две тройки. Проблема названа именем Имре З. Ружи и Эндре Семереди, которые первыми доказали, что ответ меньше, чем на медленно растущий множитель.
Теорема Мендельсона — Далмейджа — утверждение о свойстве паросочетаний в двудольных графах: если для двудольного графа с подмножествами вершин и существуют паросочетания и такие, что насыщает , а насыщает , то существует паросочетание , которое насыщает одновременно множества и
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
