4. На рисунке показано 4 графа. а) Сколько рёбер в графе 2? б) Укажите степени вершин в графе 2. в) Укажите среди графов: 1) одинаковые; 2) связные; 3) с циклами.

Решение:

а) Количество рёбер в графе 2:

Ребро — это линия, соединяющая две вершины графа. В графе 2 мы видим:

• Одно ребро, соединяющее две вершины.
• Одно петлевое ребро (ребро, которое начинается и заканчивается в одной и той же вершине).

Таким образом, в графе 2 всего 2 ребра.

б) Степени вершин в графе 2:

Степень вершины — это количество рёбер, инцидентных этой вершине. Петлевое ребро учитывается дважды.

• Вершина слева: к ней подходит одно ребро. Её степень равна 1.
• Вершина справа: к ней подходит одно ребро, и есть петлевое ребро, которое начинается и заканчивается в этой вершине (считается как два ребра). Общая степень равна 1 + 2 = 3.

Ответ: Степени вершин равны 1 и 3.

в) Анализ графов:

1) Одинаковые графы:

Два графа называются одинаковыми (изоморфными), если между их вершинами существует взаимно однозначное соответствие, сохраняющее смежность (т.е. если две вершины соединены ребром в одном графе, то и соответствующие им вершины соединены ребром в другом графе).

• Граф 3 и Граф 4 являются одинаковыми. Они оба представляют собой полный граф с 3 вершинами (K₃).

2) Связные графы:

Граф называется связным, если между любыми двумя его вершинами существует путь.

• Граф 1: Не связный (две отдельные компоненты).
• Граф 2: Связный.
• Граф 3: Связный.
• Граф 4: Связный.

3) Графы с циклами:

Цикл — это путь, который начинается и заканчивается в одной и той же вершине, и при этом не содержит повторяющихся рёбер (кроме начального и конечного).

• Граф 1: Нет циклов.
• Граф 2: Содержит цикл (петлевое ребро).
• Граф 3: Содержит цикл (например, треугольник, образованный тремя вершинами и тремя рёбрами).
• Граф 4: Содержит цикл (также треугольник).

Ответ:
1) Одинаковые: Графы 3 и 4.
2) Связные: Графы 2, 3, 4.
3) С циклами: Графы 2, 3, 4.