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

Занятие 8. Графы

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

Примеры графов:

каркас любого многогранника в пространстве (т. е. множество его вершин и рёбер);
схема линий метро;
граф знакомств для некоторой компании людей (вершины соответствуют людям, вершины соединены ребром, если соответствующие им люди знакомы).

Часто решение задачи значительно упрощается, если представить условие в виде графа, обозначив какие-либо объекты точками, а отношения между ними - рёбрами графа.

Приведём решение задачи 6 занятия 7 («кони»). Занумеруем клетки доски числами 1, 2, ..., 9 как показано на рисунке. Каждой клетке сопоставим точку плоскости, и соединим соответствующие точки отрезком в случае, если из одной клетки можно попасть в другую ходом коня. В результате мы получим граф в виде восьмиугольника и одной изолированной точки. Исходная и требуемая расстановка коней изображены на рисунках а) и б) соответственно.

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

1.	В некоторой стране 100 городов. Из каждого города выходит 6 дорог. Сколько всего дорог в этой стране?
2.	Двое по очереди проводят диагонали выпуклого 20-угольника. Запрещается проводить диагонали, имеющие общие точки (даже вершины) с уже проведёнными. Проигрывает тот, кто не может сделать ход. Кто из соперников имеет выигрышную стратегию?
3.	На занятие математического кружка пришло 10 школьников, им было предложено 10 задач. Каждую задачу решило два школьника, и каждый школьник решил по две задачи. Докажите, что можно организовать рассказ решений так, чтобы каждый школьник рассказывал решение одной из решённых им задач, и решения всех задачи были рассказаны.
4.	Можно ли фигуры, изображённые на рисунке, нарисовать, не отрывая карандаша от бумаги и не проходя ни по какой линии дважды?
5.	Докажите, что в любой компании из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
6.	Докажите, что в любом графе количество вершин, из которых выходит нечётное число рёбер, чётно.
7.	В Флатландии столица соединена авиалиниями с 21 городом, город Дальний – с одним, все остальные города – с 20 городами. Докажите, что из столицы можно прилететь в Дальний (быть может, с пересадками).
8.	В городе М с любой станции метро до любой другой можно проехать (быть может с пересадками). Докажите, что одну из станций можно закрыть на ремонт так, чтобы с любой оставшейся станции до любой другой можно было бы по прежнему проехать на метро.
9.	В шестиугольнике ABCDEF противоположные стороны попарно параллельны (AB\|\|DE, BC\|\|EF, CD\|\|FA). Докажите, что площадь треугольника ACE составляет не менее половины площади шестиугольника.
10.	Существуют ли такие целые числа x, y и z, что сумма их квадратов равна 1999?

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!