历史：1736年 19世纪
应用：计算机科学、化学、运筹学、经济学、语言学等
内容：图的基本概念、包括 路径和环,欧拉回路，哈密尔顿回路/货郎担问题，图同构、平面图等。

6.1 引言

边遍历

定义

图G是由非空结点集合V={v₁,v₂,v₃…,v_n}以及边集合E{e₁,e₂,e₃,…,e_n}两部分组成，其中每条边可用一个结点对表示，记作G=<V,E>。

①定义中的结点对可以是有序的，也可以是无序的，若边e所对应的结点对e_i=<v_i1,v_i2>是有序的，则称e_i是有向边，若边e所对应的结点e_i=<v_i1,v_i2>，i=1,2,…,n是无序的，则称e_i是无向边。

②有向边简称弧,v_i1称为弧e_i的始点, v_i2,称为弧e_i的终点,统称为e_i的端点.无向边简称棱。

每一条边都是无向边的图称为无向图.无向图用G表示,但有时用G泛指图,如图所示.

无向图

每一条边都是有向边的图称为有向图.有向图只能用D表示,如图所示.

有向图

图的常用术语

• ①孤立点:与任何边都不关联的顶点。
• ②顶点与边的关联：若e_k=(vi,vj)∈E(或e_x=<v_i,v_j>∈E),称e_k与v_i及v_j关联。
• ③环:如果e_k=(v_i,v_j)(或e =<v_i,v_j>),且v_i=v_j,则称e_k为环。
• ④顶点与顶点的相邻或邻接:若e_k为无向边,即e_k=(v_i,v_j)∈E,称v_i与v_j相邻;若e_k为有向边,即e_k=<v_i,v_j)>∈E,称v_i邻接到v_j,v_j邻接于v_i,还称v_i是e_k的始点,v_j是e_k的终点。
• ⑤边与边的相邻:若e_k和e_l,至少有一个公共端点,则称e_k与e_l相邻。
• ⑥平行边:若在无向图中,关联一对顶点的无向边多于1条，称这些边为平行边.平行边的条数称为重数。

特殊图类

①有限图:V,E 均为有限集。
②n 阶图:IVl=n.其中,IVI指的是结点集合V的结点的个数。
③零图:E=∅.即图中没有边,只有孤立点。
④平凡图:E=∅且IVI=1.即只有一个孤立点构成的图。
⑤多重图:含平行边的图。
⑥简单图:既不含平行边也不含环的图。
⑦完全图：

• a.无向完全图:在含n个点无向图中，各点之间都有边相连的无向图叫做有n个点的完全图,用K_n表示。如图7.6表示的为K₅。
• b.有向完全图:有向图中各点之间都有两条相向的边连接的图,称为有向完全图.如图7.7所示的为3个结点的有向完全图。

完全图

图中结点度数

1、无向图结点的度数
设G=<V,E>为无向图,与顶点，关联的边的条数称为v的度,记作 deg(v)。
约定:每个环算两条边,则环的度数为2。
最大度:△(G)max{d(v)lv∈V} 最小度,δ(G) min{d(v)lv∈V}。
由定义可知零图中各点度数为0，完全图k_n各点的度数为n-1。

握手定理

定理1
设图G是具有n个结点、m条边的无向图,具中结点集合为V={v₁ ,v₂,…,v_n},则
即顶点度数之和等于边数之和的两倍
定理1是显然的,因为在计算各点的度数时,每条边都计算两次,于是图G中全部顶点的度数之和就是边数的2倍.
定理2
在任何无向图中，度数为奇数的结点必定是偶数个。
2、有向图结点的度数
设D=<V,E>为有向图,以顶点v为起始结点的弧的条数称为结点v的出度,记作 deg⁺(v).以顶点v为终止结点的弧的条数称为v的入度,记作 deg^-(v).入度和出度之和称为顶点v的度,记作deg(v).显然有
定理3
在任何有向图中，所有节点的入度之和等于所有节点的出度之和，即

3、度数序列
设V={v₁ ,v₂,…,v_n}为图G的顶点集，称{d(v₁),d(v₂),…d(v_n)}为G的度数序列。

---

习题：P261 1,4,7,10,20,30

6.2路径与回路

定义

在有向图中,从顶点v₀到顶点v_n的一条路径是图中的边的序列,其中每一条边的终点是下一条边的起点。

• —条路径中,如果同一条边不出现两次,则称此路径是简单路径。
• —条路径中，如果同一顶点不出现两次,则称此路径是基本路径(或叫链)。
• 如果路径的始点vo和终点vn相重合,即vo=vn ,则此路径称为回路。
• 没有相同边的回路称为简单回路,通过各顶点不超过一次的回路称为基本回路。
• 路径P中所含边的条数称为路径P的长度。

子图

定义

如果V(H)⊆V(G)且E(H)⊆E(G),则称H是G的子图，记作H⊆G。

支撑子图

若H是G的子图且V(H)=V(G)，则称H是G的支撑子图（或生成子图）

诱导子图

设图H=<V',E'>是图G=<V,E>的子图。若对任意结点u∈V'，v∈V'，如果(u,v)∈E,有(u,v)∈E',则H由V'唯一地确定，并称H是结点集合V'的点诱导子图,记作G(V')；如果H无孤立结点，且由E'所唯一确定，则称H是边集E'的边诱导子图，记作G(E')。
例： 图7.9中，图(b)与(c)均为(a)的子图，(c)为(a)的支撑子图，(b)为(a)的点诱导子图也是(a)的边诱导子图。

例：图7.10中，(a)--(f)都是(a)的子图，其中(a)--(d)为(a)的支撑子图，(e)为(a)的点诱导子图，(f)为(a)的边诱导子图。

---

连通图

1、无向图中两顶点的连通
在一个无向图G中，若从顶点u到v存在通路，则称u与v连通。
规定：u到自身总是连通的。
2、有向图中两顶点的可达
在一个有向图D中，若存在从顶点u到v有向通路，则称u可达v。
规定：u到自身总是可达的。
有向通路是有方向性的，所以在有向图中，若u可达v，但反之不成立。
3、无向图的连通性
在无向图中，若从顶点v₁到顶点v₂有路径，则称顶点v₁与v₂是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图，否则称G是非连通图。
4、有向图的连通性
一个有向图D=(V,E)，将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图.如果一个有向图的基图是连通图，则有向图D是弱连通的，否则称D为非连通的.若D中任意两点u,v都有从u可达v，或从v可达u,则称D是单向连通的;若D中每点u均可达其他任一点v,则称D是强连通的.

欧拉图

欧拉通路与欧拉回路、欧拉图概念

经过图G的每条边一次且仅一次,而且走遍每个结点的通类,称为欧拉通路。
经过图G的每条边一次且仅一次的回路,称为欧拉回路,具有欧拉回路的图称为欧拉图。
注:①欧拉回路要求边不能重复,结点可以重复.笔不离开纸,个里及地疋元所有的边且走过所有结点,就是所谓的一笔画.。
②凡是一笔画中出现的交点处,线一出一进总应该通过偶数条(偶度点),只有作为起点和终点的两点才有可能通过奇数条(奇度点).
习题：P271,1,4,13,21,22,34

哈密尔顿图

定义：经过图中每个顶点一次且仅一次的通路(回路),称为哈密尔顿通路(哈密尔顿回路).存在哈密尔顿回路的图叫哈密尔顿图.
注意：欧拉图与哈密尔顿图研究目的不同,前者要遍历图的所有边,后者要遍历图的所有点。
虽然都是遍历问题,两者的困难程度却大不相同.欧拉图问题,欧拉已经解决了,而哈密尔顿问题却是一个至今仍未解决的难题,在大多数情况下,人们还是采用尝试求解方法来解决。
哈密尔顿图的判定定理1
设G是n(n≥3)阶无向简单图.
①若G中任何一对不相邻的顶点的度数之和都大于等于n-1,则G中存在哈密尔顿通路;
②若G中任何一对不相邻的顶点的度数之和都大于等于n,则G是哈密尔顿图.
哈密尔顿图的判定定理2
在n(n≥2)阶有向图D=<V,E>中,如果所有有向边均用无向边代替,所得无向图中含生成子图K。,则有向图D中存在哈密尔顿通路.
推论n(n≥3)阶有向完全图是哈密尔顿图.

哈尔顿图和欧拉图的区别

欧拉:每条边一次
哈密尔顿(H回路):每个节点一次可能有哈密尔顿回路，没有欧拉回路
哈密尔顿回路还没找到简单的判别条件

图的表示

20节