МАЛЫЙ МЕХМАТ МГУ

Кружок для 9-11 классов

Занятие 6. Двудольные графы

Напоминание. Лемма о рукопожатиях: количество вершин нечётной степени в графе — чётно.
Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что не будет ребер с концами одинакового цвета. Вершины белого и чёрного цвета называются белой и чёрной долями соответственно.
(Понятно, что раскраска, в которой белый цвет заменили чёрным, а чёрный белым, также подходит. Поэтому важен не цвет каждой вершины, а то, в одну долю с какими вершинами она попала.)
Двудольный граф, в котором между долями проведены все возможные рёбра, называется полным двудольным графом. Он обозначается \(K_{n, m}\), где n — число вершин в одной доли, а m — в другой.

1.

Нарисуйте граф \(K_{3, 4}\), убедитесь, что он двудольный — раскрасьте его в два цвета нужнм образом.

2.

В графе каждая вершина покрашена в синий или зелёный цвет. При этом каждая синяя вершина связана с пятью синими и восемью зелёными, а каждая зелёная — с девятью синими и шестью зелёными. Каких вершин больше — синих или зелёных?

3.

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

4.

В классе каждый мальчик дружит с тремя девочками, а каждая девочка — с пятью мальчиками. При этом 17 детей из этого класса любят участвовать в математических боях, а в их классной комнате 15 двухместных парт. Сколько всего ребят в классе?

5.

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

6.

а)

Какое наибольшее число рёбер (без петель и кратных рёбер) может быть в двудольном графе с k белыми и m чёрными вершинами?

б)

Какое наибольшее количество рёбер может быть в двудольном графе с 2n вершинами? А с 2n + 1?

7.

Докажите, что если в двудольном графе степени всех вершин одинаковы, то вершин каждого цвета поровну.

8.

В каждой строке и в каждом столбце таблицы \(8 \times 8\) стоит ровно две фишки. Докажите, что их можно покрасить в чёрный и белый цвет так, чтобы в каждом столбце и в каждой строке стояли разноцветные фишки.

9.

В прошлом учебном году в Москве прошли математическая олимпиада, Турнир Ломоносова и Турнир Городов. В каждом соревновании участвовало нечётное число учеников математического класса гимназического лицея «\(\pi\)–тая школа», причем каждый ученик участвовал в нечётном числе олимпиад. Всего в классе 20 учеников. Докажите, что нашёлся ученик, не пришедший ни на одну олимпиаду.

10.

Теорема Кёнига. Докажите, что граф является двудольным тогда и только тогда, когда все циклы в этом графе имеют четную длину:

а)

Докажите, что если граф двудольный, то в нём нет нечётных циклов.

б)

Докажите, что если в графе нет нечётных циклов, то он двудольный.