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

时间:2024-08-27 22:21:50 学人智库 我要投稿
  • 相关推荐

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

定理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.unjs.com/

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

考研英语基础复习攻略02-27

美妆腮红的基础画法12-31

管理学基础教学课件01-01

中医基础理论:脏腑的概述12-05

综合基础知识考试技巧03-23

旅游管理综合基础知识12-31

平面设计的几个基础定律12-31

关于期末考试复习的英语复习方法08-16

电子技术基础知识集锦06-18

电子技术基础知识大全12-12