Графы и турниры

Поймём сначала такой факт, что если в графе степень каждой вершины не больше то его вершины можно покрасить в цвет. Действительно это так, будем по очереди красить вершины, и каждый раз у нас будет не более запретов. Тогда вершины графа можно правильным образом покрасить в цвет. Ориентируем каждое ребро от вершины с цветом меньшего номера к вершине с цветом большего номера. Нетрудно понять, что любой путь в полученном графе будет разноцветный, а значит его длина будет не более

Рассмотрим двудольный граф, вершинами левой доли — строчки, правой доли — столбцы, а рёбра — оставшиеся клетки. Докажем, что для доли, соответствующей строчкам, выполняется условие леммы Холла, откуда и будет следовать решение задачи. Выберем любые строчек. Если столбец не соединён ребром ни с одной из выбранных строчек, то в нём вырезали хотя бы клеток. Тогда таких столбцов не более Следовательно, выбранные строчек соединены с хотя бы строчками. Но для всех Условие леммы Холла доказано.

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

Рассмотрим двудольный граф, в которой вершины левой доли — красные треугольники, правой доли — зелёные треугольники, а рёбра проведены между зелёными и красными треугольниками, которые можно проткнуть одной булавкой. Заметим, что задача равносильна поиску паросочетания в рассматриваемом графе, которое покрывает всю левую долю (а значит и правую). Для доказательства существования такого паросочетания докажем условие леммы Холла. Рассмотрим любые красных треугольников. Предположим, что из этих треугольников ведут рёбра в зелёных треугольников. Значит эти зелёных треугольников покрывают красных треугольников, а так как треугольники равновеликие, то Следовательно, условие леммы Холла выполнено.

Достаточно показать, что мы можем заполнить ещё одну строчку с соблюдением условий. Рассмотрим двудольный граф, вершинами левой доли будут числа от до вершинами правой доли — столбцы, и проведём все рёбра от чисел к тем столбцам, в которых их нет. Заметим, что степени всех вершин равны по Воспользуемся таким следствием из леммы Холла. Если в двудольном графе в одной доле вершин, а в другой не меньше причём степени вершин в каждой доле одинаковые между собой, то тогда можно выделить паросочетание в доле с вершинами. Следовательно, получаем, что в рассматриваемом графе есть паросочетание, покрывающее левую долю (а значит и правую). Тогда следуя этому паросочетанию мы можем расставить числа в строке, а значит, и во всей таблице.

Рассмотрим двудольный граф, вершинами которого будут мальчики и конфеты, а рёбра будем проводить от мальчика к конфете, если та ему нравится. Если для доли мальчиков выполняется условие леммы Холла, то найдём паросочетание, покрывающее мальчиков и раздадим конфеты мальчикам, следуя ему. Предположим, что условие леммы Холла не выполняется. Пусть — это максимальное по включению множество мальчиков, для которого не выполняется лемма Холла, а — это множество конфет, которые нравятся мальчикам из Понятно, что Удалим из графа вершины из множеств и Так как то осталось не менее конфет. Для оставшегося графа для доли мальчиков выполнено условие леммы Холла, так как иначе множество было не максимальным по включению. Значит в оставшемся графе есть паросочетание, покрывающее мальчиком. Раздадим оставшимся мальчикам конфеты, следуя этому паросочетанию, а мальчикам из раздадим оставшиеся конфеты (их хватит, так после удаления осталось не менее конфет). Нетрудно убедится, что при такой раздаче конфет все условия задачи выполнены.

Пусть язык знают меньше всего людей. Тогда возможны два случая: (a) язык знают менее человек и (b) язык знают более человек. В первом случае определим язык как язык, который знают меньше всего людей, не считая языка. Во втором случае определим язык как язык, который знают меньше всего людей среди всех людей, знающих язык. Заметим, что всего люди знают языков, а значит язык знают не более людей. Эти люди помимо языка знают ещё менее языков, а значит в случая (b) язык знают менее людей.

Рассмотрим двудольный граф, вершинами левой доли будут математиков, вершинами правой доли будут и языки, причём у каждого языка будет по клонов. Также проведём рёбра от математиков ко всем языкам, которые они знают. Заметим, что от каждого математика ведёт хотя бы рёбер. Следовательно, от любых математиков ведёт или рёбер. Докажем, что для полученного графа выполнено условие леммы Холла. Рассмотрим любых математиков. Если то условие леммы Холла выполнено. Если то условие леммы Холла не выполнено только в случае, когда эти математиков знают один и тот же язык. Но в этом случае эти математиков знают один и тот же набор из трёх языков, два из которых это и языки. Следовательно, это случай (b). Но это невозможно, так как людей, знающих одновременно и язык меньше Если то условие леммы Холла не выполнено только в случае, когда эти математиков не знают какой-то из и языков. Пусть все эти математиков не знают третий язык. Но язык знают меньше всего людей, значит это случай (a). Но тогда язык знает не более людей, а из людей, не знающих третий язык не более знают язык. Значит язык знает не менее Осталось заметить, что что противоречит выборы языка в случае (a). Мы доказали, что для рассматриваемого графа есть паросочетание, покрывающее долю математиков, а это и есть разбиение их на группы по человек с общим языком.

(a) Предположим, что в любом паросочетании не более ребра. По теореме Кёнига имеем, что в этом графе есть вершинное покрытие состоящее из не более вершины, причём степень каждой вершины в не более Следовательно, рёбер не более что противоречит условию.

(b) Рассмотрим двудольный граф, вершины левой доли — цифры в десятках, правой — цифры в единицах. Рёбра — выбранные числа. Далее применяем пункт

Выделим какой-то цикл Если это не весь граф, то из какой-то вершины цикла есть ещё одно ребро (пусть ). Из двусвязности графа знаем, что в графе есть путь из в Пусть это часть пути от до первого пересечения с циклом Тогда можно выделить два цикла, содержащих ребро что противоречит условию.

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

a b Между любыми двумя вершинами есть два непересекающихся пути по теореме Менгера.

b a При удалении любой вершины между любыми двумя оставшимися остался путь (одна из частей цикла), а значит граф двусвязен.

a c Пусть даны вершина и ребро Пусть — соседи ( так как граф двусвязен). По теореме Геринга между множествами и есть два непересекающихся пути. Следовательно, есть цикл через и ребро

c a Аналогично b a.

(a) Пусть это рёбра и По теореме Геринга между множествами и есть два непересекающихся пути, которые и образуют вместе с рёбрами и искомый цикл.

(b) Нет. Легко видеть, что в графе на картинке ниже нет цикла, который содержит три отмеченных ребра, но он трехсвязный.

(a) В недвудольном графе существует цикл нечетной длины. Обозначим этот цикл за Для вершин из этого цикла условие выполняется. Поэтому рассмотрим вершину которая лежит вне этого цикла. По теореме Геринга и в силу того, что наш граф двусвязный получаем, что существует два непересекающихся пути из в Обозначим вершины цикла за в порядке обхода. Пусть пути из в идут в вершины и где Тогда цикл или цикл будет нечётной длины.

(b) В недвудольном графе существует цикл нечетной длины. Пусть это не весь граф. Тогда есть вершина вне этого цикла. По доказательству из прошлого пункта мы знаем, что есть нечетный цикл, который содержит и при этом точно имеет общее ребро с этим нечетным циклом, но такого не может быть по условию.

Докажем индукцией по База при очевидна.

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

Индукция по База при справедлива, искомое дерево — две вершины, соединённые ребром.

Переход: пусть у нас есть произвольный набор из чисел, сумма которых Понятно, что хотя бы одно из них равно иначе сумма будет больше Также очевидно, что хотя бы одно число не меньше двойки. Выкинем единицу и уменьшим на один. Для нового набора можно построить дерево из условия. Вернём число, равное одному и соединим соответствующую ему вершину с вершиной, соответствующей числу Дерево для -го числа построено.

Индукция по База при и

Переход: выкинем две вершины и Для оставшегося графа по предположению расставим стрелки так, как нужно. Вернём вершины. Из всех вершин проведём стрелку в из проведём стрелку в Из проведём стрелку во все вершины. Нетрудно убедиться, что описанная конструкция удовлетворяет условию.

Давайте оставим в задаче только цвета. Все вершины с цветами от до будут цвета аналогично определим цвета и Теперь будем доказывать задачу индукцией по если у нас есть цвета, то мы хотим найти одноцветное поддерево. База очевидна по принципу Дирихле, теперь докажем переход. Раскрасим вершины -го уровня таким образом: пусть есть хотя бы два цвета на -ом уровне, тогда покрасим вершину на -ом в цвет По предположению индукции можно выделить -поддерево, все вершины которого будут одного цвета. Тогда давайте к каждой вершине добавим по висячие цвета Такие найдутся по нашему методу покраски. Переход доказан. Мы получили даже более сильное утверждение, так что исходная задача верна.

Индукция по База при тривиальна.

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

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

Рассмотрим произвольную вершину смежную с Её степень хотя бы Всего не более вершин, не смежных с Значит, соединена хотя бы с вершинами, смежными с Последнее выражение при нечётном равно при чётном — В силу произвольности выбора так можно сказать про любую вершину, смежную с

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

Рассмотрим такое разбиение рёбер графа на множества: выделим треугольников Осталось рёбер, выходящих из оставшихся без множества. Каждое из них поместим в отдельное множество. Теперь выкинем вершину и все рёбра, которые уже находятся в множествах. Получился граф на -й вершине, рёбра которого по предположению разбиваются на не более чем нужных нам множеств. Таким образом, всего не более Далее, рассматривая разные случаи чётности нетрудно убедиться, что последняя величина не превосходит

Посчитаем рёбра в графе детей двумя способами – тогда их , где в классе мальчиков и девочек, однако тогда существует такое , что и , значит, число учеников в классе кратно 8. Между 30 и 35 такое число одно — 32.

Нарисуем ориентированный граф, где стрелка идет от человека к человеку , если ударил . Пусть всего человек. Тогда так как из каждого человека выходит по 4 стрелки, то всего стрелок . С другой стороны, так как в каждого человека входит 3 стрелки, то всего стрелок Противоречие.