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

Кружок 7 класса

Руководитель Блинков Александр Давидович
2007/2008 учебный год

Графы

1.
Какие из следующих пяти графов изоморфны?

2.
Нарисуйте все неизоморфные друг другу графы с не более чем четырьмя вершинами.

3.
Нарисуйте граф, вершинами которого являются натураль¬ные числа от 1 до 15, а рёбрами соединены числа, одно из которых делится на другое.

4.
Постройте граф с пятью вершинами, в котором нет ни трёх попарно соединённых, ни трёх попарно несоединённых вершин.

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

6.
Укажите степени всех вершин графов из задачи 3.

Дополнительные задачи

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

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

Супербонус

9.
Найти наибольшее возможное количество рёбер в графе с n вершинами, если известно, что среди произвольных
а) трёх,
б*) четырёх его вершин есть две, не соединённые ребром.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS