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

Вот решение по пунктам. 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 рёбрами).