2. Нарисуйте какой-нибудь граф, в котором 4 вершины, нет петель и ровно: а) 3 цикла; б) 2 цикла.

Задание 2. Графы с циклами

Давай нарисуем графы с заданным количеством вершин и циклов.

а) Граф с 4 вершинами и 3 циклами

Чтобы получить 3 цикла в графе с 4 вершинами, мы можем соединить вершины так, чтобы образовалось несколько замкнутых путей. Вот один из возможных вариантов:

В этом графе:

• Вершины: 1, 2, 3, 4.
• Рёбра: (1,2), (2,3), (3,1), (3,4), (2,4).
• Циклы:
• 1-2-3-1
• 2-3-4-2
• 1-2-4-3-1

б) Граф с 4 вершинами и 2 циклами

Для двух циклов можно нарисовать такую схему:

В этом графе:

• Вершины: 1, 2, 3, 4.
• Рёбра: (1,2), (2,3), (3,1), (3,4).
• Циклы:
• 1-2-3-1
• 1-3-4-? (тут нет цикла, надо дорисовать)

Исправим предыдущий граф для 2 циклов. Нам нужно 4 вершины и 2 цикла. Это значит, что нам нужно добавить 2 ребра к дереву из 4 вершин (которое имеет 3 ребра). Получится 3+2 = 5 рёбер. Изначально в дереве 3 ребра, и в нём 0 циклов.

Давай попробуем иначе. Нам нужно 4 вершины и 2 цикла. Это значит, что граф не будет деревом.

Вариант для 2 циклов:

В этом графе:

• Вершины: 1, 2, 3, 4.
• Рёбра: (1,2), (2,3), (3,1), (3,4), (2,4).
• Циклы:
• 1-2-3-1
• 2-3-4-2

Ответ:

• а) Пример графа с 4 вершинами и 3 циклами показан выше.
• б) Пример графа с 4 вершинами и 2 циклами показан выше.