Тема 5. Классические графы. Путь, цикл, связный граф

Задание 1. Может ли путь (цикл) иметь длину 1,2,..., n,...? Пусть (цикл) общего вида?

Задание 2. Укажите в графе К ₅ циклы, содержащие 4, 5, 6, 10 ребер. Какие из них простые?

Задание 3. Докажите, что если степень каждой вершины графа , то в графе существует цикл.

Задание 4. Докажите, что, если граф имеет все простые циклы четной длины, то он не имеет ни одного цикла нечетной длины.

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

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

Задание 7. Дано множество из 15 костей домино от 0-0 до 4-4. Сколькими способами их можно уложить в цикл, соблюдая правила игры?

Задание 8. Для изображенного графа найдите путь наименьшей и наибольшей длины то вершины 1 до вершины 2; от вершины 1 до вершины 7.

Задание 9. Пусть для каждой вершины графа G выполняется условие . Покажите, что в G существует цикл длины .

Задание 10. Пусть G – граф на 2 n вершинах, не содержащих треугольников. Докажите, что граф содержит не более циклов и приведите пример, когда это достигается (экстремальная теорема Турана).

Задание 11. Разделяющим множеством графа G называется множество его ребер, при удалении которого число компонентов графа увеличивается. Разрезом графа G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Приведите примеры разрезов в графах . Докажите, что число общих ребер цикла и разреза в связном графе четно.

Задание 12. Обхватом графа называется длина его кратчайшего цикла. Найдите обхваты графов , графа Петерсена, графов тел Платона.

Задание 13. Изобразите граф на вершинах с ребрами и компонентами: n = 8, k = 3, m = 15; n = 8, k = 3, m = 5; n = 8, k = 3, m = 20; n = 8, k = 3, m = 10; n = 10, k = 2, m = 36; n = 10, k = 2, m = 8; n = 10, k = 2, m = 20; n = 10, k = 2, m = 6.

Задание 14. Приведите пример с n вершинами и ребрами, n =3, 4, 5, 6, 7.

Задание 15. Граф G на n вершинах имеет m ребер и k компонент. Сколько ребер и компонент имеет граф ? Приведите примеры.

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

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