4. Изобразите граф, у которого: а) три цикла длины 3; б) два цикла длины 4. Запишите для каждого графа по две разных цепи.

Решение:

а) Граф с тремя циклами длины 3.

Для создания трех циклов длины 3, нам понадобится минимум 3 вершины. Если мы используем 3 вершины \( v_1, v_2, v_3 \) и соединим их ребрами \( (v_1, v_2), (v_2, v_3), (v_3, v_1) \), мы получим один цикл длины 3.

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

Вариант 1 (6 вершин):

Вершины: \( v_1, v_2, v_3, v_4, v_5, v_6 \).

Циклы:

1. \( v_1 - v_2 - v_3 - v_1 \)
2. \( v_1 - v_4 - v_5 - v_1 \)
3. \( v_1 - v_4 - v_6 - v_1 \)

Цепи:

1. \( v_2 - v_1 - v_4 \)
2. \( v_3 - v_2 - v_1 - v_5 \)

Вариант 2 (5 вершин, чтобы было сложнее):

Вершины: \( v_1, v_2, v_3, v_4, v_5 \).

Циклы:

1. \( v_1 - v_2 - v_3 - v_1 \)
2. \( v_1 - v_2 - v_4 - v_1 \)
3. \( v_1 - v_3 - v_4 - v_1 \)

Цепи:

1. \( v_2 - v_1 - v_3 \)
2. \( v_4 - v_2 - v_1 - v_3 \)

б) Граф с двумя циклами длины 4.

Для создания двух циклов длины 4, нам понадобится минимум 4 вершины. Если мы используем 4 вершины \( v_1, v_2, v_3, v_4 \) и соединим их как квадрат \( v_1 - v_2 - v_3 - v_4 - v_1 \), мы получим один цикл длины 4. Чтобы получить второй цикл длины 4, можно добавить диагональ или использовать другую комбинацию вершин.

Вариант 1 (4 вершины):

Вершины: \( v_1, v_2, v_3, v_4 \).

Циклы:

1. \( v_1 - v_2 - v_3 - v_4 - v_1 \)
2. \( v_1 - v_2 - v_4 - v_3 - v_1 \) (здесь нарушено условие, что цикл должен быть длиной 4. Необходимо перестроить граф.)

Правильный Вариант 1 (4 вершины):

Вершины: \( v_1, v_2, v_3, v_4 \).

Ребра: \( (v_1, v_2), (v_2, v_3), (v_3, v_4), (v_4, v_1) \) - первый цикл длины 4.

Ребра: \( (v_1, v_3), (v_3, v_2), (v_2, v_4), (v_4, v_1) \) - второй цикл длины 4.

Цепи:

1. \( v_1 - v_2 - v_3 \)
2. \( v_1 - v_3 - v_4 \)

Вариант 2 (5 вершин):

Вершины: \( v_1, v_2, v_3, v_4, v_5 \).

Циклы:

1. \( v_1 - v_2 - v_3 - v_4 - v_1 \)
2. \( v_1 - v_2 - v_5 - v_4 - v_1 \)

Цепи:

1. \( v_1 - v_2 - v_3 \)
2. \( v_3 - v_4 - v_1 - v_5 \)

Ответ: Приведены два варианта построения графов с соответствующими цепями.