Таблицы Брадиса

Сколько всего было сыграно матчей?

Сколько всего было сыграно матчей?

Элементы математики в задачах - Г. А. Мерзон

Теория графов 2

листок 3Д / март 2005

Задача 1. В турнире по олимпийской системе участвовали п команд. Сколько всего было сыграно матчей?

Задача 2. Докажите, что граф с п вершинами, степень каждой из

п — 1

которых не менее ——, связен.

Задача 3. В связном графе все вершины имеют степень 100. Докажи­те, что после удаления любого из ребер он остается связным.

Задача 4. Докажите, что в любом связном графе есть подграф, явля­ющийся деревом и содержащий все вершины (максимальное подде­рево).

Задача 5. Докажите, что из любого связного графа можно выкинуть вершину и выходящие из нее ребра так, чтобы он остался связным.

Задача 6*. В кубической коробке п х п х п лежало п3 единичных ку­биков. Кубики высыпали, каждый просверлили по диагонали, затем все плотно нанизали на нить и связали в кольцо (соединили вершину первого кубика с вершиной последнего). При каких п получившееся «ожерелье» можно убрать обратно в коробку?

Задача 7*. Все 28 Петиных одноклассников имеют по различному числу друзей в этом классе. Сколько из них дружат с Петей? А если одноклассников п?

Задача 8* (теорема Кэли). В графе с п вершинами каждая вершина соединена с каждой ребром (такой граф называется полным). Дока­жите, что существует ровно пп—2 способов выкинуть несколько ребер так, чтобы оставшийся граф являлся деревом.

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