Найти цикломатическое число коранг число остовных деревьев в графе

Цикломатическое число – число γG=mG-nG+kG, где m(G) – число ребер, n(G) – число вершин, k(G) – число связных компонент.
Оно показывает, сколько ребер надо удалить из графа, чтобы в нем не осталось ни одного цикла.
Коранг – число γ*G=nG-kG, где n(G) – число вершин, k(G) – число связных компонент.
Оно показывает число ребер, входящих в любой остов графа.
mG=7; nG=5; kG=1
γG=7-5+1=3
γ*G=5-1=4
Число остовных деревьев может быть вычислено при помощи матричной теоремы о деревьях (теоремы Кирхгофа).
Определим матрицу Кирхгофа
K=kijn×n;kij=-1, если вершины смежные0, если вершины не смежныеpvi, если i=j и pvi- степень вершины vi
Степени вершин:
pA=3; pB=3; pC=3; pD=3; pE=2
K=kij=30-1-1-103-1-1-1-1-13-10-1-1-130-1-1002
Все алгебраические дополнения Aij=-1i+jMij матрицы Кирхгофа равны между собой и их общее значение равно количеству остовных деревьев графа.
Возьмем, например, алгебраическое дополнение элемента k11.
A11=-123-1-1-1-13-10-1-130-1002=приведем кверхнетреугольномувиду
B=A*13+BC=A*13+C→D=A*13+D3-1-1-1083-43-130-4383-130-13-1353C=B*12+C→D=B*18+D3-1-1-1083-43-13002-1200-12138
D=C*12+D→3-1-1-1083-43-13002-1200032
→A11=3-1-1-1083-43-13002-1200032=3*83*2*32=24
Значит, существует 24 остовных деревьев графа G.