98. Рассмотрите граф на рисунке 55. а) Сколько вершин в его остовном дереве? б) Сколько рёбер в его остовном дереве? в) Найдите цикломатическое число этого графа.

Остовное дерево связного графа содержит все вершины исходного графа и на одну вершину меньше рёбер.

На рисунке 55 имеется 8 вершин. Поэтому в любом его остовном дереве:

а) \(8\) вершин;

б) \(8-1=7\) рёбер.

На рисунке граф имеет 8 вершин и 18 рёбер. Поэтому его цикломатическое число:

\(\mu=m-n+1=18-8+1=11\).

Ответ: а) 8; б) 7; в) 11.