Графы


Страница для печатиSend by emailPDF версия

Графы

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

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

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

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

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

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

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

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

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

Супербонус

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