Муниципальное автономное образовательное учреждение лицей №14 имени Заслуженного учителя Российской Федерации А.М. Кузьмина

Индивидуальный проект по теме:

«Двудольные графы»

Автор работы:

ученица 10 класса А

Куприянова Елизавета,

Научный руководитель:

Неверовская Светлана Владимировна

Тамбов

2016

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ        3

ОСНОВНАЯ ЧАСТЬ        4

1.        общее понятие        4

2.        лемма холла        7

практика        9

3.        теорема кенига        10

практика        13

ЗАДАЧИ        14

ЗАКЛЮЧЕНИЕ        16

СПИСОК ЛИТЕРАТУРЫ        17

ВВЕДЕНИЕ

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления.

Побывав в зимней математической школе при МФТИ, я узнала о небольшой, но в то же время сложной олимпиадной теме. Речь идет о теме “Двудольные графы”. Времени на нее уделялось относительно немного, и я решила изучить ее более подробно самостоятельно.

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

Объектом исследования является процесс изучения темы “Двудольные графы”.

Предмет исследования – возможность применения полученных знаний.

Цель исследования – рассмотреть и овладеть знаниями о теме “Двудольные графы”.

В процессе работы я поставила перед собой следующие задачи:

• Разобрать всевозможную теорию по теме “Двудольные графы”;
• Собрать в своем проекте различные задачи на данную тему.

ОСНОВНАЯ ЧАСТЬ

1. общее понятие

Двудольный граф – граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.

        Все вершины графа можно покрасить в два цвета так, что ребра соединяют только разноцветные вершины.

Рисунок 1

Полный двудольный граф – двудольный граф, у которого все вершины в разных долях соединены ребрами.

Рисунок 2

        Любое дерево – двудольный граф(в дереве отсутствуют любые циклы, в том числе и нечетные).

Рисунок 3

Теорема:

 – двудольный граф тогда и только тогда, когда все его простые циклы имеют четную длину.

• Доказательство в одну сторону(“”):

1. Раскрасим вершины графа в два цвета.
2. Возьмем какой-то простой цикл.
3. Все вершины разбились на пары.
4. Следовательно, граф четной длины.

• Доказательство в обратную сторону("”):

1. Пусть  - некоторая вершина.
2. Будем считать, что граф – связанный. Т.е. если взять какую-то одну компоненту, раскрасить ее в два цвета, взять следующую компоненту, снова раскрасить ее в два цвета. Поскольку между компонентами ребер никаких нет, можно красить любым способом, лишь бы в компонентах проблем не возникало.
3. Берем некоторую вершину. Поскольку мы живем в одной компоненте связанности, все вершины как-то связаны с вершиной . Мы можем рассматривать самые короткие пути, которые ведут в эту вершину.
4. Рассмотрим кратчайшие пути из  в остальные вершины. Покрасим  в белый цвет. Если путь из  в  - четный, то красим  в белый цвет, а если путь – нечетный, то красим  в черный цвет.
5. Докажем, что нет ребер между одноцветными вершинами. От противного. У нас есть две доли, в какой-то доле внутри нашлось ребро, соединяющее вершины этой доли. И где-то здесь у нас живет вершина . Тогда у нас есть какой-то путь в . Давайте поймем, что найдется простой цикл нечетной длины, ведь просто цикл нечетной длины уже нашелся (). Давайте сделаем цикл простым. Пойдем путями  и , если эти пути никогда не пересекутся, то мы уже нашли простой цикл. Пусть эти пути пересеклись,  - точка пересечения, тогда путь из  в   по разным маршрутам имеет одну и ту же длину, потому что у нас путь из  в   был кратчайшим. Путь из  в  по  - кратчайший, а путь из  в  по  - тоже кратчайший, следовательно, у них одна и та же длина. Получается, что  имеет нечетную длину, а следовательно, цикл простой.

        Следствие: всякое дерево, содержащее более одной вершины, является двудольным графом.

Рисунок 4

Паросочетание – набор ребер, такой что любая вершина – конец ровно одного из них.

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

Очевидно, что всякое совершенное паросочетание максимально. Обратное неверно.

2. лемма холла

Данная лемма также известная как лемма о свадьбах или лемма о девушках.

Имеется n юношей и n девушек, которые как-то между собой знакомы, и известно, что любые k юношей вместе знакомы хотя бы с k девушками. Тогда их можно переженить таким образом, что в каждой паре будут знакомые.

Дополнение: 

Мы берем любой набор юношей, тогда смотрим девушек, которые с ними знакомы. Тогда девушек будет не меньше, чем юношей.

Доказательство по индукции:

Понятно, что условие не только достаточное, но и необходимое.

База:  очевидна (если есть 1 юноша, то есть девушка, которая с ним знакома)

Переход от  к .

Два случая:

1.  Есть группа из  юношей, которая знакома ровно с  девушками. Тогда, во-первых, понятно, что по предположению индукции с этой группой мы можем разобраться, потому что , ежели такая группа найдется, то в этой группе по предположению индукции мы так можем переженить. Если мы сейчас проверим, что в дополнение к этой группе требуемое условие выполнено, то задача будет выполнена. Проверим, что дополнение к этой группе тоже удовлетворяет условию леммы Холла. Мы берем этих самых юношей, выкидываем девушек, которые с ними знакомы, забываем про них, потому что их мы можем разбить на пары. Остается  юношей и  девушек(C). Эти оставшиеся юноши и девушки тоже должны удовлетворять условию  леммы Холла. Давайте в этом убедимся. Пусть группа юношей – A, группа девушек – B, группа оставшихся юношей и девушек, о которых говорилось выше, - С. Тогда возьмем m юношей из группы С. Рассмотрим группу , у нас получается  юношей. Эти юноши знакомы с  девушек. Давайте посмотрим, что будет, если отсюда выкинуть А.  знакомы с  (некая добавка D). Что будет, если мы отсюда выкинем А? Из группы  надо будет стереть всех знакомых с А. Тогда все остальные девушки должны быть знакомы с . А как выглядят все знакомые с ? Это как раз и есть группа . Поэтому мы получили, что те юноши, которые составляют группу , знакомы с девушками из группы (в группе  у нас  человек, тогда в группе  получается  человек). Выходит, что те  юношей знакомы с  девушками. Таким образом, оставшиеся  юношей и оставшиеся  девушек тоже удовлетворяют условию леммы Холла. Следовательно, про предположению индукции, их мы можем разбить на пары, а, соответственно, тех, что выкинули, мы тоже может разбить на пары.
2. Если такая группа не найдется, то любых  юношей сторого больше, чем  знакомых девушек, то есть мы имеем хотя бы  знакомых девушек. Тогда у нас есть  юноша и  девушка. Мы берем их этого набора любого юношу. Он знаком с какой-то девушкой, так как по условию леммы Холла в группе из одного юноши тоже есть хотя бы одна знакомая девушка. Тогда у нас останется  юношей и  девушек. НО! Если мы возьмем теперь  юношей, то сколько у нас будет знакомых девушек? Вместе с той одной получается хотя бы , а без той – хотя бы . А когда мы выкинем тех девушку и юношу, у нас останется набор из  юношей и  девушек, которые удовлетворяют условию леммы Холла. А значит, по предположению индукции, мы можем разбить их на пары.

Следствие:

Для набора из  юношей и  девушек верно, что любые  юношей знакомы хотя бы с  девушками, а значит любые  девушек знакомы хотя бы с  юношами. В лемме Холла мы можем менять юношей и девушек местами.

Переформулировка на языке графов:

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

Несложно заметить, что эта та же самая теорема.

Пусть доля  - юноши, а доля  – девушки, тогда знакомства – это наличие ребра в графе.

Условие: для любого  количество вершин, смежных с  (количества элементов в области ).

Мы берем какое-то количество юношей. И тогда девушки, которые с ними знакомы, их количество не меньше, чем количество юношей. Ну а паросочетание – это и будет разбиение юношей и девушек на пары.

Переформулировка на языке теории множеств:

У нас есть множества , и для любого набора этих множеств (набора индексов) количество элементов в объединении множеств() хотя бы k ().

практика

Задача:

Подсчитать количество совершенных паросочетаний у дерева на n вершинах.

Решение:

        Дерево может либо иметь лишь одно совершенное паросочетание, либо не иметь таких паросочетанй вообще. Докажем это по индукции.

Дерево (определенное на 2 вершинах) имеет единственное совершенное паросочетание, а дерево (определенное на 1 вершине) совершенного паросочетания не имеет. Рассмотрим теперь дерево  на  вершинах и какой-то лист  в нем. Совершенное паросочетание должно покрывать вершину . Следовательно, оно должно включать в себя ребро , где  - единственная смежная с  вершина дерева . При этом все другие ребра, инцидентные , в строящееся паросочетание включать уже нельзя. Удаляя тогда вершины , мы получаем в общем случае лес, состоящий из нескольких деревьев. По индукционному предположению, у каждого из этих деревьев имеется либо одно, либо ни одного совершенного паросочетания. Предположим, что в каждом из этих деревьев имеется совершенное паросочетание. В этом случае, добавляя к ребрам этих паросочетаний ребро , мы получаем единственное паросочетание в исходном дереве . В противном случае, в дереве  совершенные паросочетания отсутствуют.

Задача:

Найти количество совершенных паросочетаний в полном графе  на 2n вершинах.

Решение:

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

Задача:

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

Решение:

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

Пусть существуют k юношей, которые знакомы с меньше, чем k девушками. Пусть они знакомы с n девушками.

Тогда от доли юношей будет отходить 3k ребер, при этом знакомы юноши только с n девушками. А от доли девушек выходит 3n ребер, которые приходят ко всем юношам. Тогда получаем, что . Но по условию , а значит . Противоречие. Следовательно, k юношей знакомы не менее, чем с k девушками, тогда мы можем составить k пар. Значит, можем выбрать 8 ладей, не бьющих друг друга.

Задачи для тренировки:

1. Из шахматной доски вырезали 7 клеток. Докажите, что на оставшиеся клетки можно поставить 8 не бьющих друг друга ладей.
2. Лист бумаги с обеих сторон разбит на 2016 многоугольников равной площади. Докажите, что его можно проткнуть в 2016 местах, чтобы каждый многоугольник оказался проткнутым ровно по одному разу.
3. На улице болтунов живут по n юношей и n девушек, причем каждый юноша знаком ровно с k девушками., а каждая девушка – ровно с k юношами.

• Докажите, что все юноши и девушки могут одновременно говорить со своими знакомыми по телефону.
• Докажите, что юноши и девушки могут звонить друг другу по телефону так, чтобы за k часов каждый поговорил с каждым из своих знакомых по часу.

3. теорема кенига

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

Рассмотрим две величины:

1. Максимальное количество не бьющих друг друга ладей, которые можно оставить().
2. Наименьшее количество линий, которыми можно накрыть все ладьи(). Будем линией называть либо строку, либо столбец. Мы можем брать линию и накрывать ее.

Доказать:

Доказательство:

•  – очевидно, т.к. если у нас есть линии, накрывающие всю картинку, то в каждой линии стоит не больше одной ладьи, т.к. ладья бьет всю линию). Значит в каждой линии не больше одной ладьи, следовательно, всего ладей не больше, чем всего линий.
• (количество ладей больше, либо равно количеству линий). Пусть все накрывается  строками и  столбцами. Тогда . Всю расстановку ладей мы накрыли . Если мы будем менять местами строки, то ничего не изменится. Мы сможем добиться следующей картинки:

Рисунок 5

Больше ладей нигде не стоит, их всех запихнули сюда.

Рассмотрим отдельно первый кусок и докажем, что в нем можно поставить  ладей, не бьющих друг друга. Аналогично со вторым куском, где можно поставить  ладей. Так как кусочки разные и друг друга бить не могут, то получится  ладей.

Считаем, что в каждой строке и столбце стоит ладья. Проверим, удовлетворяет ли первый прямоугольник условию леммы Холла, т.е. что-то у нас будет юношами, а что-то – девушками. Пусть строки – юноши, а столбцы – девушки. Тогда у нас есть  юношей и хотя бы  девушек(т.е. если есть какая-то строка, такая что на этой части нет ни одной ладьи, то эту строку можно было выкинуть сразу, т.к. все ладьи в области 3 накрыты столбцами. А в области 1 хотя бы одна строка есть, следовательно, у каждого юноши хотя бы одна знакомая девушка.

Рассмотрим только столбец из первого прямоугольника. У нас есть  строк и сколько-то столбцов. Возьмем несколько строк. На этих частях строк ладьи стоят хотя бы в . Почему это так? Предположим, что ладьи стоят меньше, чем в  столбцах. Мы можем стереть эти  строк. Ладьи, которые стоят в области 3, нас не волнуют, так как они все равно накрыты  столбцами. А  строк мы можем заменить на новые меньше, чем  столбцов, так как ладьи стоят меньше, чем в   столбцов. Мы получим, что покрытие меньше, чем  линиями. Следовательно, у каждого юноши найдется набор столбцов хотя бы в  штук, получается, что у каждого юноши хотя бы  девушек. По лемме Холла мы можем разбить строки и столбцы в области 1 на пары(знакомство – наличие ладьи на пересечении). Мы можем этим  строкам в области 1 выбрать  столбцов в пары, т.е. есть какая-то строка, есть какой-то столбец, если мы выбрали пару, значит есть какая-то ладья на пересечении и т.д. Таким образом, мы соберем  ладей, потому что мы образовали  пар. Аналогичные рассуждения проведем с областью 2, только строки заменятся столбцами. Таким образом, выберем здесь  ладей, а остальные выкинем. Из области 3 мы выкинем вообще все ладьи. Итак, мы сумеем выбрать хотя бы  не бьющих друг друга ладей.

Переформулировка на языке теории графов:

У нас  - двудольный граф.

В этом графе мы рассмотри две вещи:

• Максимальное паросочетание, которое покрывает наибольшее количество вершин (мы берем максимальное возможное количество ребер, которые не умеют общих концов).
• Наименьшее количество вершин в графе таких, что все ребра выходят из этих вершин.

Эти величины равны между собой.

Давайте поймем, что это та же самая теорема.

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

практика

Задача:

В компании юношей и девушек не менее n человек. Оказалось, что среди них нельзя составить  брак по знакомству. Докажите, что тогда можно выбрать n людей так, что из любой пары знакомых один выбран.

Доказательство:

Так как из компании n юношей и девушек нельзя выбрать n+1 брак по знакомству. То, переходя на язык теории графов, минимальное вершинное покрытие двудольного графа равно n. По теореме Кенига, минимальное вершинное покрытие равно максимальному паросочетанию в двудольном графе, откуда получаем, что максимальное вершинное покрытие нашего графа равно n. А значит, можно выбрать n людей так, что из любой пары знакомых один выбран.

Задача:

Докажите, что из 51 числа, не большего 100, можно выбрать 6 чисел, любая пара которых отличается в обоих разрядах.

Доказательство:

Пусть десятки – юноши, а единицы – девушки. Тогда от каждого юноши может выходить по 9 ребер, а от каждой девушки – по 10 ребер, где ребро – это знакомство юноши и девушки или по ,условию задачи, число. Тогда минимум у нас может быть 6 чисел. Получается, что минимальное вершинное покрытие в двудольном графе равно 6, откуда следует, что максимальное паросочетание тоже равно 6. Значит, можно выбрать 6 чисел, любая пара которых отличается в обоих разрядах.

Задача для тренировки:

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

ЗАДАЧИ

1. На кружке 20 ученикам было предложено 20 задач. Каждый ученик решил две задачи, и каждую задачу решили ровно двое из них. Докажите, что можно так организовать разбор задач, чтобы каждый ученик объяснил одну задачу, и все задачи были разобраны.
2. На шахматной доске стоят 8k ладей по k ладей в каждой горизонтали и вертикали. Докажите, что на доске можно выбрать 8 ладей, не бьющих друг друга.
3. На дискотеке каждый юноша знаком не менее, чем с M девушками, а каждая девушка – не более, чем с M юношами. Доказать, что каждый юноша может пригласить на танец знакомую девушку.
4. В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками. Семнадцать из них любят играть в математическое домино. Всего в классе пятнадцать парт. Сколько детей учится в классе?
5. В строку выписано одиннадцать целых чисел. Для любой группы подряд идущих чисел подсчитана ее сумма(группы из одного числа тоже учитываются). Какое наибольшее количество сумм могло оказаться нечетными?
6. Саша записал в клетки шахматной доски числа от 1 до 64 в неизвестном порядке и сказал Ване сумму чисел в каждом прямоугольнике из двух клеток, добавив, что числа 1 и 64 лежат в одной диагонали. Докажите, что благодаря этой информации Ваня может определить, где какое число записано.
7. В лагерь приехало некоторое количество детей, причем каждый ребенок имеет от 50 до 100 знакомых среди остальных. Доказать, что вожатый Максим сможет раздать им майки 1331 цветов так, чтобы у каждого ребенка среди его знакомых было не менее 20 различных цветов.
8. Квадрат со стороной 1 разбит двумя способами на n равновеликих многоугольников. Доказать, что можно выбрать в квадрате n точек так, что в каждом многоугольнике любого из этих разбиений будет по выбранной точке.
9. Имеется граф, все вершины которого имеют четную степень. Доказать, что из него можно выкинуть некоторое количество ребер, чтобы в оставшемся графе степень каждой вершины была равна двум.
10. Дворец в форме треугольника со стороной 50 метров разбит на 100 треугольников комнат со сторонами 5 метров. В каждой стенке между комнатами есть дверь. Какое наибольшее число комнат сможет обойти человек, не заходя ни в какую комнату более одного раза?
11. Сможет ли конь обойти шахматную доску 7*7 так, чтобы побывать на каждом поле ровно по одному разу и вернуться последним ходом на исходное поле?
12. Можно ли в клетки шахматной доски расставить натуральные числа так, чтобы для любых клеток с общей стороной одно из чисел делилось на другое, а для всех остальных пар клеток такого не было?
13. Пусть в таблице n*n записаны неотрицательные числа, и суммы чисел в каждой строке и в каждом столбце равны 1. Доказать, что можно выбрать n клеток таблицы, из которых никакие две не стоят в одном и том же столбце и в одной и той же строке, и при этом в каждой выбранной клетке число будет положительным.
14. Клетчатый прямоугольник покрыт доминошками так, что каждую клетку покрывают ровно 2 доминошки. Докажите, что доминошки можно разбить на две группы так, что каждая группа полностью покрывает прямоугольник в один слой.
15. В одной стране из каждого города выходит по три железные дороги. Две компании хотят их все приватизировать. Однако антимонопольный комитет требует, чтобы из каждого города выходили дороги обеих компаний. Докажите, что компании могут договориться, чтобы это требование было выполнено.

ЗАКЛЮЧЕНИЕ

Работая над проектом, я выполнила поставленную перед собой цель, т.е. освоила и научилась применять полученные знания по теме “Двудольные графы”. Работая с различными сборниками задач и статьями в математических журналах, считаю нужным отметить отрывочность рассмотрения этой темы.

Для достижения этой цели я изучила теорию по данной теме и связала ее воедино.

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

СПИСОК ЛИТЕРАТУРЫ

1. http://www.zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.dvudol
2. http://foxford.ru/wiki
3. http://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf
4. http://www.rkarasev.ru/common/upload/taskprob.pdf
5. http://www.alenn.ru/attachments/article/327/О.%20Нечаева.%20Применение%20леммы%20Холла.pdf