Тема 7. Регулярные графы

Задание 1. Изобразите k -регулярный граф на n вершинах: k = 3, n = 10; k = 4, n = 15; k = 5, n = 7; k = 8, n = 7; k = 2, n = 10; k = 3, n = 12; k = 4, n = 14; k = 7, n = 9; k = 10, n = 8; k = 2, n = 6;

Задание 2. Найдите число ребер k -регулярного графа на n вершинах.

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

Задание 4. Является ли регулярным графом граф Петерсена? Найдите в графе Петерсена путь длины 4, циклы длины 5, 6, 8, 9, разрезы из 3, 4, 5 ребер.

Задание 5. Изобразите все кубические (то есть 3-регулярные) графы на вершинах.

Задание 6. Является ли регулярным графы тел Платона?

Задание 7. Докажите, что 2-регулярный граф на n точках совпадает с .

Задание 8. Приведите пример неизоморфных 3-регулярных графов.

Задание 9. В государстве 100 городов, и из каждого выходит по 4 дороги. Сколько всего дорог в государстве?

Задание 10. Может ли в государстве, в котором из любого города выходит ровно 3 дороги, быть 100 городов?