【离散数学·图论】（复习）

一、基本概念

1.一些基本术语：

2.点u，v邻接（或相邻）: 边e称为关联顶点u和v,or e连接u和v;

3.G=(V,E)中，顶点v所有邻居的集合：N(v), 成为v的邻域。

4.度 ： deg(v)

5.悬挂点：度为1的顶点；

6.孤立点：度为0的顶点。

二、几个定理and概念

1.握手定理：边数的2倍=度数。  （总度数一定为偶数）

2.无向图有偶数个奇数度顶点。 （由1.） (定理2)

3.入度： ;   出度：

4.有向图，边数=入度=出度   (定理3)

5.完全图：  , 每个顶点的度：n-1

6.圈图：

7.轮图：  顶点数：n+1，边数：2n

8.立方体图：   顶点数：2^n,边数: n*（2^（n-1））

9.二部图（二分图）：用颜色判断

10.完全二部图 

11.从旧图到新图： （子图，并图等）

12.加权图 ： 边上带权重

三、图的表示

1.邻接表

2.邻接矩阵

3.关联矩阵：

当ej关联vi时 ：1；or : 0；

四、其它概念

1.图的同构：

对于G1(V1,E1)，G2(V2,E2) ，存在映上的从V1到V2 的函数f；

f性质：对所有a,b  a和b在G1里相邻<->a和b在G2里相邻。

2.通路：从u到v,  (边的序列)

            长度：通路中边的数目

                      对于权重图，则为各边的权重之和。

   回路：若一条通路在相同的顶点开始和结束，且长度大于0，则它是一条回路。

   若通路或回路不重复的包含相同的边，那么它就是简单的。

   各边全不同的：简单回路；

   各点全不同的：基本回路；

3.可达性：vi到vj从在通路（不管长度）。

4.无向图连通性：

连通图：每一对顶点间都有一条路径；

or : 不连通图；

5.连通分量：是G的连通子图，而不是G的其它连通子图的真子图。（即G的最大连通子图）

6.有向图连通性：

（1）强连通：对任意a,b  a到b有，b到a也有；

（2）弱连通：在有向图的基本无向图中是连通的；

7.计算顶点间的通路：用矩阵相乘。

五、欧拉回/通路  （可一笔画出）  （边不重复）

1.欧拉回路 充要： 所有顶点度数都为偶数；

2.欧拉通路 充要：有2个顶点度数为奇数，其它为偶数。

六、哈密顿回/通路 （点不重复）  （无充要条件）

1.哈回=>....  (性质)

   定理：

2....=>哈

定理：

3....=>哈回

（1）狄拉克定理：

（2）奥尔定理：

例：

答：m=n>=2;

七、平面图与着色：

1.欧拉公式：

设G是带e条边和v个顶点的连通平面简单图。设r是G的平面图表示中的面数，则 r=e-v+2。

2.图着色

简单图的着色：给每个顶点都指定一种颜色，使没有两个相邻的顶点颜色相同。

（平面图的着色数不超过4）