45.Приложение теоремы Рамсея. Теорема Ван дер Вардена.

Головоломка о вечеринке представляет собой задачу, типичную для приложений теории Рамсея. Какое количество людей достаточно для того, чтобы образовать группу, в которой всегда окажется либо четверо людей знакомых друг с другом, либо четверо, друг с другом незнакомых? На этом рисунке гости представлены точками. Каждое красное ребро на этом графе соединяет гостей, знакомых друг с другом, а каждое синее — незнакомых. В группе из 17 точек, изображённых на рисунке, невозможно найти четыре точки для которых сеть соединяющих их рёбер была бы целиком красной или целиком синей Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось либо четверо знакомых, либо четверо незнакомых друг с другом. На самом деле во всякой группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо незнакомых друг с другом. Если множество всех натуральных чисел любым способом разбито на конечное число классов, то хотя бы один из этих классов содержит сколь угодно длинную арифметическую прогрессии.

Этот удивительный по простоте формулировки и очень нетривиальный по доказательству результат выдающийся российский математик и педагог Александр Яковлевич Хинчин (19.07.1894-18.11.1959) назвал одной из жемчужин теории чисел. Знаменитая теорема Ван дер Вардена утверждает, что для любых натуральных чисел n>2, r>1 найдется такое минимальное натуральное число W(n,r), что в любой раскраске множества натуральных чисел {1,...,W(n,r)} в r цветов найдется одноцветная арифметическая прогрессия длины n. Величину W(n,r) из теоремы Ван дер Вардена принято называть функцией Ван дер Вардена. 

46.Двудольные графы. Теорема Кенига

 Граф называется двудольным, если  причем каждое ребро графа имеет один конец из другой — из . Двудольные графы применяются, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. Например, в генетике — признаки и гены, в химии — кислоты и основания, в экономике — производители и потребители. С двудольными графами связана задача о назначениях. Пусть   — множество претендентов на рабочие места, — множество рабочих мест. Необходимо каждого из претендентов обеспечить работой в соответствии с его профессиональной подготовкой. Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. Поэтому двудольный граф не может содержать клику размером более 2. Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум) Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые k элементов одной из долей связаны по крайней мере с k элементами другой (Теорема Холла). Двудольный граф, у которого в каждой части больше 2 вершин, является непланарным. Для того, чтобы проверить граф на предмет двудольности, достаточно в каждой компоненте связности выбрать любую вершину и помечать оставшиеся вершины во время обхода графа (например, поиском в ширину или в глубину) поочерёдно как чётные и нечётные (см. иллюстрацию). Если при этом не возникнет конфликта, все чётные вершины образуют множество U, а все нечётные — V.Теорема Кёнига — одна из основных в комбинаторике. Она гласит: Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин «линия» обозначает либо строку, либо столбец в матрице). Теорема Кёнига представляет собой матричный аналог критерия Холла существования системы различных представителей у семейства подмножеств конечного множества. Сформулирована и доказана Д. Кёнигом (D. Konig) в 1931 г.