Ниже три разных графа на 8 вершинах, в каждом из которых две вершины изолированы. Пусть изолированными будут вершины 7 и 8. Остальные 6 вершин образуют разные структуры.
Граф 1: путь на 6 вершинах плюс две изоляции
- Вершины: 1,2,3,4,5,6,7,8
- Изолированы: 7, 8
- Ребра: {(1,2), (2,3), (3,4), (4,5), (5,6)}
- Примерная форма: 1—2—3—4—5—6 7 8
- Примечание: это путь P6 плюс две isolated.
Граф 2: цикл на 6 вершинах плюс две изоляции
- Вершины: 1,2,3,4,5,6,7,8
- Изолированы: 7, 8
- Ребра: {(1,2), (2,3), (3,4), (4,5), (5,6), (6,1)}
- Примерная форма: 1—2—3—4—5—6—(замыкается в цикл) 7 8
- Примечание: это цикл C6 с двумя изолированными вершинами.
Граф 3: полная двудольная связность K3,3 на 6 вершинах плюс две изоляции
- Вершины: 1,2,3,4,5,6,7,8
- Изолированы: 7, 8
- Ребра (между двумя тройками): {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)}
- Примерная форма: две тройки вершин 1-2-3 и 4-5-6 с полным пересечением между ними; 7 и 8 лежат отдельно
- Примечание: это K3,3, тоже на 6 вершин, дополненный двумя изолированными.
Дополнительные пояснения:
- Все графы обладают 8 вершинами, ровно две из них изолированы (7 и 8).
- В первом графе средняя степень вершин 1–6 равна 1–2 (для концевых и внутренних вершин соответственно); во втором графе все вершины 1–6 имеют deg = 2; в третьем графе вершины 1–3 и 4–6 имеют deg = 3.
- Это три разных по изоморфизму графа: путь P6, цикл C6 и K3,3 (вместе с двумя изолированными вершинами).
Если нужно, могу привести матрицы смежности для каждого графа или преобразовать в графическую схему ASCII.
