离散数学图论基础知识点(一)

时间:2024-04-03 08:20:11

1、 图的基本概念:

图论中的图由结点和连接结点的边组成。边可以是有方向的,也可以是无方向的。由有方向的边构成的图称为有向图,由无方向的边构成的图称为无向图。

2、几个重要的定义:

(1)平行边:关联一对结点的多于一条的边(在有向图中平行边的方向是一致的)。

(2)邻接:如果有边关联与一对结点,则称这对结点是邻接的。

(3)环:一条边的两个端点关联于同一个节点,每个环给它的结点提供 2 度。

(4)孤立点:任何边都不关联的点。

(5)n阶图:结点数为n的图。

(6)零图:只有结点没有边的图。

(7)平凡图:1 阶零图称为平凡图。

(8)空图:结点集为空集的图。

度的概念:

1、度数(简称 度):边和结点关联的次数之和为该结点的度数,记作d(Vi)。

2、出度即d+(Vi):以结点为起点所关联的边数。

3、入度即d-(Vi):以结点为终点所关联的边数。

4、悬挂结点:度数为 1 的结点。

5、悬挂边:悬挂结点所对应的边。

6、❤️握手定理(图论的基本定理):所有结点的度数之和为边数的 2 倍,即d(Vi)=2e。

7、❗️❗️握手定理的推论(很重要):度数为奇数的结点的个数为偶数。

8、????定理:在有向图中,所有出度数=所有入度数=边数。

3、图的分类:

1、简单图:图中不含平行边,也不含环。

2、多重图:图中含有平行边。

3、完全图(Kn):在无向简单图中任何结点都与其余的结点相邻;在n阶有向简单图中的任意两个结点v和u,既有有向边(v,u),又有有向边(u,v)。

4、✨:对于n阶无向完全图来说,每个结点的度数为n-1,所有结点的总度数为n(n-1),根据握手定理边数为n(n-1)/2 。而n阶有向完全图的边数为n(n-1) 。

5、????:n阶无向简单图的 最大度数<=n-1 .
n阶有向简单图的 最大度数<=2(n-1) .

6、正则图:所有结点度数一样的图。

7、环图(Cn):节点数 n>=3的环绕相连的图,环图都是正则图。

8、轮图(Wn):给环图添加一个结点,并把这个结点和每个节点逐个链接得到的图。

9、方体图(Qn):描述困难,不如看下图!
离散数学图论基础知识点(一)

10、二分图:把结点集V划分为两个子集V1和V2,使每条边有一个端点在V1中,另一个端点在V2中,这样得到的图便是二分图。

11、完全二分图:V1中的每个结点和V2中的每个结点均有且仅有一条边相连。

12、带权图:每个结点或每条边都带有数值的图。

4、图的小运算:

1、 设图G=(V,E)。
从 G 图中删去边 e 得到的图表示为G-e,称为删除边运算;从 G 图中删去某个边集E1 得到的图表示为 E-E1,称为删除边集运算。与此同时还有删除结点运算删除结点集运算。定义与上面的类似,在此就不解释了。

2、边的收缩(G\e):从 G 图中删去边 e,将 e 的两个端点 u、v用一个新的结点 w 代替,将 u、v关联的所有边都关联结点 w,称为 e 的收缩。

3、加新边:在两个同属于某个结点集的两个结点v、u之间加一条边。表示为 GU(u,v)或 G+(u,v)。