Тема 4. Изоморфные графы

Задание 1. Приведите примеры неизоморфных графов, имеющих одинаковое число вершин и одинаковые наборы степеней вершин.

Задание 2. Какие из указанных графов являются изоморфными? Сколько существует изоморфизмов в каждом случае?

Задание 3. Какой граф изоморфен графу ; ; ; ?

Задание 4. Докажите, что число вершин самодополнительного графа равно 4 k или 4 k + 1. Найдите все самодополнительные графы с числом вершин, не превосходящим 5.

Задание 5. Покажите, что с точностью до изоморфизма существует ровно 2 графа с 2 вершинами; 4 графа с 3 вершинами; 11 графов с 4 вершинами; 34 графа с 5 вершинами. Кроме того, можно показать, что с точностью до изоморфизма существует ровно 156 графов с 6 вершинами; 1044 графа с 7 вершинами; 12346 графов с 8 вершинами.

Задание 6. Покажите, что с точностью до изоморфизма существует ровно 1 связный граф с 2 вершинами; 2 связных графа с 3 вершинами; 6 связных графов с 4 вершинами; 21 связный граф с 5 вершинами. Можно показать, что с точностью до изоморфизма существует ровно 112 связных графов с 6 вершинами; 853 связных графа с 7 вершинами; 11120 графов с 8 вершинами.

Задание 7. Покажите, что с точностью до изоморфизма существует ровно 1 дерево с 2 вершинами; 2 дерева с 3 вершинами; 6 деревьев с 4 вершинами; 20 деревьев с 5 вершинами. Можно показать, что с точностью до изоморфизма существует ровно 105 деревьев с 6 вершинами.

Задание 8. Покажите, что с точностью до изоморфизма существует ровно 3 ориентированных графа с 2 вершинами и 13 ориентированных графов с 3 вершинами; при этом связных 2 и 3, соответственно.