电路等级

令“ G”为具有“ n”个顶点和“ m”个边的连通图。G的生成树“ T”包含(n-1)个边。

因此，为了获得生成树= m-(n-1)，需要从“ G”中删除的边数，这称为G的电路秩。

这个公式是正确的，因为在生成树中，您需要具有“ n-1”条边。在“ m”条边中，您需要在图中保留“ n-1”条边。

因此，从“ m”中删除“ n-1”条边可以将其从图形中删除，以便获得生成树，该树不应形成循环。

示例

看一下下图-

对于上面示例中给出的图形，您有m = 7个边和n = 5个顶点。

那么电路等级是

G = m – (n – 1)
= 7 – (5 – 1)
= 3

示例

令“ G”为具有六个顶点的连通图，并且每个顶点的度为三个。找到电路等级“ G”。

根据顶点定理的总和，

6×3 = 2 | E |

| E | = 9

电路等级= | E | –（| V | – 1）

= 9 –（6 – 1）= 4