离散数学-图论基础复习

离散数学-图论基础复习

定理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为割边或桥。http://www.cnrencai.com/

【离散数学-图论基础复习】相关文章：

中考语文基础知识复习试题08-08

《公共基础知识》复习资料（经济术语）03-20

2015公共基础知识复习资料（4）12-31

2015公共基础知识复习资料（5）03-26

2015公共基础知识复习资料（6）03-26

2016电气工程师考试《专业基础》知识复习考点07-20

二年级下册期末基础知识复习试题07-16

2016自学考试计算机与网络技术基础复习题07-23

2017年成人高考《生态学基础》复习试题及答案08-09

打好基础的名言01-10