Ранг-полином графа

Ранг графа определяется как , где n – число вершин, k – число компонент связности графа. Коранг графа, или цикломатический ранг, есть , где m – число ребер.

Ранг-полином графа G имеет вид

,

где – ранг графа G , а – коранг остовного (т.е. включающего в себя все вершины графа) подграфа H, а – его ранг. Суммирование ведется по всем остовным подграфам графа G.

Ранг полином служит для анализа множества остовных подграфов. Так, например, коэффициент при в есть число подграфов размера k, а значение равно числу подграфов (включая несобственный подграф), ранг которых равен рангу самого графа.

Пример 12.8. Найти ранг-полином графа, изображенного на рис. 12.8.

Решение. Найдем все 16 остовных подграфов графа G (рис. 12.9). Множество представим в виде четырех графов размера 1 (т.е. с одним ребром), шести графов размера 2, четырех графов размера 3 и двух несобственных графов (пустой граф и граф G).

 

Рис. 12.9

 

Учитывая, что ранг графа равен 3, получаем сумму: