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

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

Графы 1.1

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

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

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

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

1.

Вася считает, что в его классе у всех разное число друзей-одноклассников. Не ошибается ли он?

2.

В некоторой стране 100 городов. Из каждого города выходит 6 дорог. Сколько всего дорог в этой стране?

3.

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

4.

В королевстве Маленьком 15 городов. Король приказал сделать так, чтобы из каждого города выходило по 5 дорог к другим городам Маленького. Удастся ли выполнить такой приказ?

5.

Может ли в королевстве Средненьком, в котором из каждого города выходит по 3 дороги, быть ровно 100 дорог?

6.

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

7.

Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.

8.

Можно ли фигуры, изображённые на рисунке, нарисовать, не отрывая карандаша от бумаги и не проходя ни по какой линии дважды?

9.

Можно ли расставить на шахматной доске 8 коней так, чтобы никакие два коня не били одинаковое число других?

10.

Можно ли нарисовать 9 отрезков так, чтоб каждый пересекался ровно с 3 другими?