Деревья

.

Если n – число вершин, а m – число ребер графа G, то любое его остовное дерево имеет n вершин и (n – 1) ребер. Таким образом, остовное дерево получается отбрасыванием (m – n + 1) ребер графа G. Число m – n + 1 называется цикломатическим числом графа G.

Если каждому ребру графа приписано некоторое положительное число, называемое его весом, или стоимостью, то граф называется нагруженным. Стоимостью нагруженного графа считается суммарная стоимость всех его ребер. Многие задачи, связанные с построением экономичных систем сообщения или информационных систем, приводят к задаче поиска остовного дерева минимальной стоимости.