МАЛЫЙ МЕХМАТ МГУ
Занятие 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 |
