Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Question

Вопрос:

Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Фотография

Ответ ассистента

Accepted Answer

**Ответ: Построить два неодинаковых (неизоморфных) графа с заданными степенями вершин возможно.** Степень вершины — это количество ребер, которые из неё выходят. Нам нужно, чтобы в обоих графах были вершины со степенями: $1, 1, 2, 2, 3, 3$. **Вариант 1 (Связный граф):** Представь цепочку или кольцо с ответвлениями. Соединим вершины так, чтобы получился один общий путь: 1. Соединим две вершины степени 3 между собой. 2. От каждой вершины степени 3 пустим по одной вершине степени 1 (конечные точки). 3. Оставшиеся две вершины степени 2 вставим «в разрыв» между вершинами степени 3, чтобы они образовали цикл или длинную перемычку. **Вариант 2 (Несвязный граф):** Разделим вершины на две отдельные группы: 1. Первая группа: Цикл из 3-х вершин (треугольник). У каждой вершины в цикле степень уже равна 2. Чтобы сделать две вершины со степенью 3, добавим к двум из них по «хвосту» (вершине степени 1). - Получим степени: $3, 3, 2, 1, 1$. 2. Вторая группа: У нас осталась одна лишняя вершина со степенью 2. Но по условию нам нужно 6 вершин. **Исправленное решение:** Чтобы графы были точно разными, можно варьировать связи между вершинами с наибольшей степенью: - **Граф А:** Вершины со степенью 3 соединены друг с другом напрямую. - **Граф Б:** Вершины со степенью 3 **не** соединены друг с другом напрямую (между ними стоят вершины степени 2). Так как структура связей разная, графы будут неодинаковыми, хотя набор степеней вершин у них совпадает.

Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Ответ ассистента

Другие решения