137 Изобразите два графа с шестью вершинами степени 2: один связный — нет.

Привет! Давай разберемся. Степень вершины — это количество рёбер, которые к ней подходят. Если у всех шести вершин степень 2, это значит, что каждая вершина соединена ровно с двумя другими.

Граф 1: Связный

Когда у всех вершин степень 2, самый простой связный граф — это цикл. Нарисуем 6 точек (вершин) и соединим их по кругу.

1. Вершины: 1, 2, 3, 4, 5, 6.
2. Рёбра: (1,2), (2,3), (3,4), (4,5), (5,6), (6,1).

Проверим степени: у каждой вершины по два соседа, значит, степень у каждой вершины равна 2. Этот граф связный, потому что из любой вершины можно добраться до любой другой.

Граф 2: Не связный

Если граф не связный, значит, он состоит из нескольких отдельных частей (компонент). Поскольку у каждой вершины степень 2, каждая такая часть тоже должна быть циклом.

1. Вариант 1: Два цикла по 3 вершины.
• Часть 1: Вершины 1, 2, 3. Рёбра: (1,2), (2,3), (3,1).
• Часть 2: Вершины 4, 5, 6. Рёбра: (4,5), (5,6), (6,4).
2. Вариант 2: Один цикл из 4 вершин и один цикл из 2 вершин. (Но цикл из 2 вершин — это просто два ребра между двумя точками, что немного необычно, но математически возможно).
• Часть 1: Вершины 1, 2, 3, 4. Рёбра: (1,2), (2,3), (3,4), (4,1).
• Часть 2: Вершины 5, 6. Рёбра: (5,6), (6,5).

Мы можем выбрать любой из этих вариантов. Например, возьмем два треугольника:

Граф:

• Вершины: 1, 2, 3, 4, 5, 6.
• Рёбра: (1,2), (2,3), (3,1), (4,5), (5,6), (6,4).

Здесь у каждой вершины степень 2, но граф не связный, потому что из вершин {1, 2, 3} нельзя добраться до вершин {4, 5, 6} и наоборот.

Ответ:

• Связный граф: цикл из 6 вершин.
• Не связный граф: два непересекающихся цикла (например, два цикла из 3 вершин каждый).