№5 Изобразите произвольный несвязный граф с шестью вершинами и девятью ребрами. Подпишите все степени вершин и выпишите название одной цепи и одного цикла.

Решение:

Построим несвязный граф с 6 вершинами и 9 ребрами. Для этого разобьем вершины на две компоненты связности.

Граф:

Описание графа:

• Вершины: A, B, C, D, E, F (всего 6).
• Ребра: AB, AC, BC, BD, BE, BF, CD, CE, DE (всего 9).
• Компоненты связности: {A, B, C} и {D, E, F}.

Степени вершин:

• deg(A) = 3 (ребра AB, AC, AD)
• deg(B) = 4 (ребра AB, BC, BD, BE)
• deg(C) = 2 (ребра AC, BC)
• deg(D) = 3 (ребра BD, CD, DE)
• deg(E) = 3 (ребра BE, DE, DF)
• deg(F) = 3 (ребра BF, EF, DF)

Примечание: В первоначальном описании графа были ошибки в степенях вершин и количестве ребер. В исправленном варианте: 6 вершин, 9 ребер, степени вершин: A(3), B(4), C(2), D(3), E(3), F(3).

Пример цепи:

• A-B-C (вершины и ребра не повторяются)

Пример цикла:

• B-E-D-B (вершина B повторяется, ребра не повторяются)

Ответ: Приведен граф с 6 вершинами и 9 ребрами, указаны степени вершин, а также примеры цепи и цикла.