Лемма Кёнига о бесконечном пути

Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе. Эта теорема играет важную роль как пример в конструктивной математике и теории доказательств.

Доказана Денешем Кёнигом в 1927 году^[1].

Формулировка

Пусть $\Gamma$ — бесконечный, но локально конечный (то есть каждая его вершина имеет конечную степень) связный граф. Тогда $\Gamma$ содержит бесконечный простой путь, то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.

Замечания

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

Примечания

↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

Диаграмма Фейнмана — графическое представление математических уравнений, описывающих взаимодействия субатомных частиц в рамках квантовой теории поля. Этот инструмент изобрёл американский физик Ричард Фейнман в конце 1940-х годов, во время его работы в Корнельском университете, для выполнения расчётов рассеяния частиц.

<span class="mw-page-title-main">Теорема Кёнига (комбинаторика)</span>

В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.

Ко́мпле́ксный ана́лиз, тео́рия фу́нкций ко́мпле́ксного переме́нного — раздел математического анализа, в котором рассматриваются и изучаются функции комплексного аргумента.

О́стовное де́рево графа — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все $\text{[math]}$ вершин исходного графа и содержит $\text{[math]}$ ребро.

Пото́к — одно из основных понятий интуиционистской математики.

Теорема Тура́на даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа.

Теорема о свадьбах — утверждение о том, что в двудольном графе для любого натурального $\text{[math]}$ любые $\text{[math]}$ вершин одной из долей, где $\text{[math]}$ не превышает числа вершин доли, связаны по крайней мере с $\text{[math]}$ различными вершинами другой доли тогда и только тогда, когда граф разбивается на пары по первой доле.

В математике дискретный оператор Лапласа — аналог непрерывного оператора Лапласа, определяемого как отношения на графе или дискретной сетке. В случае конечномерного графа дискретный оператор Лапласа имеет более общее название: матрица Лапласа.

Теорема Эйлера для многогранников — теорема, устанавливающая связь между числом вершин, рёбер и граней для многогранников, топологически эквивалентных сфере.

Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество $\text{[math]}$ может быть разбито на $\text{[math]}$ попарно непересекающихся цепей, где $\text{[math]}$ — количество элементов наибольшей антицепи множества $\text{[math]}$ .

В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.

Теорема о примитивном элементе — это результат в теории полей, описывающий условия, при которых конечное расширение поля является простым. Более подробно, теорема о примитивном элементе характеризует расширения конечной степени $\text{[math]}$ , такие что существует примитивный элемент $\text{[math]}$ с $\text{[math]}$ .

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

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

Модулярная кривая $\text{[math]}$ — это риманова поверхность или соответствующая алгебраическая кривая, построенная как фактор комплексной верхней половины плоскости H по конгруэнтной подгруппе $\text{[math]}$ модулярной группы целочисленных 2×2 матриц SL(2, Z). Термин модулярная кривая может также использоваться для ссылок на компактифицированные модулярные кривые $\text{[math]}$ , которые являются компактификациями, полученными добавлением конечного числа точек к фактору. Точки модулярной кривой параметризуют классы изоморфизмов эллиптических кривых, вместе с некоторой дополнительной структурой, зависящей от группы $\text{[math]}$ . Эта интерпретация позволяет дать чисто алгебраическое определение модулярных кривых без ссылок на комплексные числа, и, более того, доказывает, что модулярные кривые являются полем определения либо над полем Q рациональных чисел, либо над круговым полем. Последний факт и его обобщения имеют фундаментальную важность в теории чисел.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

Гипотеза Сеймура о второй окрестности — это нерешенная математическая проблема об ориентированных графах, сформулированная Полом Сеймуром. Интуитивно понятно, что в социальной сети, описываемой таким графом, у кого-то будет хотя бы столько же друзей друзей, сколько и друзей. Эта проблема также известна как гипотеза Сеймура о расстоянии два.

Голоно́ми́я — один из инвариантов связности в расслоении над гладким многообразием, сочетающий свойства кривизны и монодромии, и имеющий важное значение как в геометрии, так и геометризированных областях естествознания, таких как теория относительности и теория струн. Обыкновенно речь идёт о голономии связностей в векторном расслоении, хотя в равной степени имеет смысл говорить о голономии связности в главном расслоении или даже голономии связности Эресманна в локально тривиальном топологическом расслоении.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.