电路等级

2024-05-19 04:49:05 379

令“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”。

根据顶点定理的总和，

n∑i=1 度（V_i）=2|E|

6×3=2|E|

|E|=9

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

=9–（6–1）=4