离散数学——图论基础复习

定理1: D (v1)+D (v2)+...D (vn) = 2m。
每个顶点的边数之和==2*一个图的边数

推论在任何图(无向或有向)中，奇数度的顶点数都是偶数。

定理2:在有向图中，d+(v1)+...d+(vn) = d-(v1)+...d (vn) = m.
所有顶点度之和=所有顶点度之和=图的边数[/]子图G-V '的连通分支和G的连通分支满足P(G-V ')> P(G)，且V '的任一真子集V ''''被删除后，P(G-V '''= P(G)，则V '称为G的点割集.若点割集中只有一个顶点V，则V

边割集的定义:若边集E’有一个子集，G删除E’(E’中的所有边都从G中删除)后，G的连通分支数和所得子集的连通分支数满足P(G-E’)= P(G)，则称E’为G的边割集，若边割集中只有一条边E，则称E为割边或桥。