页面打开中,请稍候...
www.Gzu521.com
| 贵 州 学 习 网 |
|
定理1： d(v1)+d(v2)+....d(vn)=2m. 各顶点上边数之和==2*图的边数 推论 任何图(无向的或有向的)中，度为奇数的顶点个数为偶数。 定理2：有向图中:d+(v1)+...d+(vn)=d-(v1)+...d(vn)=m. 所有顶点出度之和=所有顶点入度之和=图边数 割点定义：设无向图中，存在顶点集v’,使g删除v’（将v’中顶点及其关联的边都删除）后，所得子图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为割边或桥。 |
责任编辑：gzu521
当前位置:
