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

Обозначим вершины основания шестиугольной пирамиды через \(v_1,v_2,v_3,v_4,v_5,v_6\), а вершину-апекс — через \(a\).

В графе 7 вершин: 6 вершин основания и 1 вершина-апекс. Число рёбер равно \(6+6=12\): шесть рёбер образуют цикл основания, ещё шесть соединяют апекс с вершинами основания.

Граф связный, поэтому цикломатическое число:

\[\nu=m-n+1=12-7+1=6.\]

Следовательно, цикломатическое число графа равно 6.

Чтобы получить остовное дерево, нужно удалить \(\nu=6\) рёбер. Например, удалим рёбра \(v_1v_2\), \(v_2v_3\), \(v_3v_4\), \(v_4v_5\), \(v_5v_6\), \(v_6v_1\). Оставшиеся рёбра образуют звезду с центром в вершине \(a\), то есть остовное дерево.

Ответ: цикломатическое число равно 6; для получения остовного дерева необходимо удалить 6 рёбер.