А) Изобразите простой граф, степень каждой вершины которого равна 3, а все его простые циклы имеют длину как минимум 5. Б) Изобразите простой граф, степень каждой вершины которого равна 3, а все его простые циклы имеют длину как минимум 6. Простой граф —

Решение задачи по теории графов

А) Построение графа со степенью вершин $k=3$ и длиной цикла $\text{girth} \ge 5$

Дано:

1. Граф простой (нет петель, нет кратных рёбер).
2. Степень каждой вершины $d(v) = 3$ (граф 3-регулярный).
3. Длина самого короткого цикла (гирт) $\text{girth} \ge 5$.

Найти: Изобразить такой граф.

Решение:

Поскольку гирт должен быть не менее 5, в графе не должно быть треугольников ($C_3$) и четырёхугольников ($C_4$).

Самый простой 3-регулярный граф, удовлетворяющий условию $\text{girth} \ge 5$, — это Призматический граф или, в данном случае, Граф призмы над пятиугольником...