Построить граф 8 вершин 1степени

Задача: построить граф на 8 вершинах, каждая вершина имеет степень 1. Идея: - Узел с степенью 1 должен быть соседем ровно одного другого узла. Значит граф состоит только из независимых пар вершин, связанных ребром. - Это называется матчинг (совпадающее соединение). Для 8 вершин получится 4 пар и 4 ребра. Граф не будет связан, будет состоять из 4 компонентов, каждый из которых — граф с двумя вершинами и одним ребром (K2). Пошаговое решение: 1) Обозначим вершины: v1, v2, v3, v4, v5, v6, v7, v8. 2) Соединим их в пары так, чтобы пары не пересекались: - Ребро (v1, v2) - Ребро (v3, v4) - Ребро (v5, v6) - Ребро (v7, v8) 3) Проверим степени: - deg(v1) = 1, deg(v2) = 1 - deg(v3) = 1, deg(v4) = 1 - deg(v5) = 1, deg(v6) = 1 - deg(v7) = 1, deg(v8) = 1 Все вершины имеют степень 1. 4) Свойства полученного графа: - Число ребер: 4 (так как сумма степеней 8, а |E| = сумма степеней / 2 = 8/2 = 4) - Граф состоит из 4 компонент, каждая из которых — K2 (два связанных вершины). - Граф 1-регулярный (каждая вершина имеет степень 1). - Граф разобщённый; не является связным. Также он бипартитен (каждая компонента состоит из одного ребра). Вариант изображения (ASCII): v1 -- v2 v3 -- v4 v5 -- v6 v7 -- v8 или в виде списка смежности: v1: {v2} v2: {v1} v3: {v4} v4: {v3} v5: {v6} v6: {v5} v7: {v8} v8: {v7} Дополнительно: - Это единственный по изоморфизму класс 1-регулярного графа на 8 вершинах: разложение на 4 несокращённых ребра (4 K2). Другие варианты будут изоморфны этому, только метки вершин разные. Если хочешь, могу привести ещё один конкретный пример пары вершин (например, v1–v8, v2–v7, v3–v4, v5–v6) и проверить степени.