Ранг графа определяется как , где n – число вершин, k – число компонент связности графа. Коранг графа, или цикломатический ранг, есть , где m – число ребер.
Ранг-полином графа G имеет вид
,
где – ранг графа G , а – коранг остовного (т.е. включающего в себя все вершины графа) подграфа H, а – его ранг. Суммирование ведется по всем остовным подграфам графа G.
Ранг полином служит для анализа множества остовных подграфов. Так, например, коэффициент при в есть число подграфов размера k, а значение равно числу подграфов (включая несобственный подграф), ранг которых равен рангу самого графа.
Пример 12.8. Найти ранг-полином графа, изображенного на рис. 12.8.
Решение. Найдем все 16 остовных подграфов графа G (рис. 12.9). Множество представим в виде четырех графов размера 1 (т.е. с одним ребром), шести графов размера 2, четырех графов размера 3 и двух несобственных графов (пустой граф и граф G).
Рис. 12.9
Учитывая, что ранг графа равен 3, получаем сумму: