Постройте плоский граф, изоморфный графу, образованному ребрами и вершинами шестиугольной пирамиды. Чему равно цикломатическое число этого графа? Удалите необходимое количество…

Вот решение по пунктам.

1. Плоский граф, изоморфный графу шестиугольной пирамиды

• Вершины: A (вершина пирамиды) и B1, B2, B3, B4, B5, B6 (вершины основания, образующими шестиугольник).
• Рёбра: AB1, AB2, AB3, AB4, AB5, AB6 и B1B2, B2B3, B3B4, B4B5, B5B6, B6B1.
• Плоская вставка: разместить B1..B6 по окружности в порядке по часовой стрелке, A над центром окружности. Соединить A с каждым Bi и соединить соседние Bi по окружности. Это даёт планарную (плоскую) реализацию.

2. Число цикломатическое графа

• Обозначения: n = число вершин, m = число рёбер, c = число компонент.
• Здесь n = 7 (A и 6 Bi), m = 12 (6 ребер ABi и 6 ребер между Bi), c = 1 (граф связан).
• Цикломатическое число μ равно m - n + c = 12 - 7 + 1 = 6.

3. Удаление ребер до остовного дерева

• Остовное дерево для этого графа должно иметь n - 1 = 6 ребер.
• Удалить следует 6 рёбер. Простой выбор: удалить все рёбра основания B1B2, B2B3, B3B4, B4B5, B5B6, B6B1.
• Останется граф с вершинами {A, B1, ..., B6} и ребрами {AB1, AB2, AB3, AB4, AB5, AB6}, что является звездой K1,6 и потому остовным деревом (связный ацикличный граф с 6 рёбрами).