可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便

Chapter7Graphs

图论图/Graph：

可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。1/11/202317.1图的概念/IntroductionofGraph7.2图的术语/GraphTerminology7.3图的表示与同构/RepresentingGraphandGraphIsomorphism7.4连通性/Connectivity7.5欧拉道路与哈密尔顿道路/EulerandHamiltonPaths7.6最短道路问题/ShortestPathProblem7.7平面图/PlanarGraphs7.8图的着色/GraphColoring1/11/202327.1图的概念/IntroductionofGraph[定义]图

Ｖ是一个非空有限集，Ｅ是Ｖ上的一个二元关系，有序对（Ｖ，Ｅ）称为有向图/DirectedGraph。

若将E中的有序对看成是无序的（即将e=(a,b)看成e={a,b}），则称（Ｖ，Ｅ）为无向图/UndirectedGraph。有向图和无向图统称为图/Graph，记为G。

G=（Ｖ，Ｅ）1/11/20233[定义]顶点：Ｖ中的元素称为顶点，用带标记的点表示，也称为结点/Vertices。[定义]边：在有向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G的有向边/directededge。用由ａ到ｂ带箭头的线把ａ和ｂ连起来；在无向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G的无向边/undirectededge。a、ｂ间用连线连结，有向边和无向边统称为G的边/edge。1/11/20234[定义]图的分类

对图G=（Ｖ，Ｅ）。若对于任意的（ａ，ｂ）∈Ｅ，ab,则称图G为简单图/SimpleGraph。

对图G=（Ｖ，Ｅ）。若允许Ｅ是一个重集，则称图G为重图/Multigraph。其相同的元素称为重边。对图G=（Ｖ，Ｅ）。若G既允许是重图又允许是非简单图，则称图G为拟图/Pseudograph。

一般的G称为线性图/LinearGraph。1/11/20235图的模型

NicheOverlapGraphsinEcologyInfluenceGraphsRound-RobinTournamentsPrecedenceGraphsTrafficMapFamilyGraphs1/11/202367.2图的术语/GraphTerminology[定义]相邻和关联：在无向图G中，若e=（ａ，ｂ）∈Ｅ，则称ａ与b相邻/adjacent，或边e关联a、ｂ/incident或联结a、b/connect。a、b称为边e的端点或结束顶点/endpoint.

在有向图G中，若e=（ａ，ｂ）∈Ｅ，即箭头由ａ到ｂ，称ａ相邻到ｂ，或a关联或联结b。a称为e的起点/initialvertex，b称为e的终点/terminalorendvertex。1/11/20237[定义]自回路：若（ａ，ａ）∈Ｅ，（{ａ，ａ}∈Ｅ），称边（ａ，ａ）（{ａ，ａ}）是自回路/loop。[定义]孤立顶点：若ａ∈Ｖ，ａ不与其他顶点相邻，称ａ为孤立顶点/isolated。1/11/20238[定义]顶点的次：在无向图G中，与a相邻的顶点的数目称为a的次或度/degree。记为deg(a)或d(a)。

在有向图G中，以a为终点的边的条数称为a的入次或入度/in-degree。记为deg–(a)或d–(a)。以a为起点的边的条数称为a的出次或出度/out-degree。记为deg+(a)或d+(a)。1/11/20239[定理1(Handshaking)]设无向图G=（V，E）有e条边，则G中所有顶点的次之和等于e的两倍。证明思路：利用数学归纳法。[定理2]无向图中次为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的次分类，再利用定理1。1/11/202310[定理3]设有向图G=（V，E）有e条边，则G中所有顶点的入次之和等于所有顶点的出次之和，也等于e。证明思路：利用数学归纳法。1/11/202311有向图与无向图的对应：无向图对应有向图：加上箭头。

有向图对应无向图：去掉箭头。称为underlyingundirectedgraph1/11/202312一些特殊的简单无向图：（1）CompleteGraphs/完全图Kn

(n>0)

（2）Cycles/环图Cn(n>2)

（3）Wheels/轮图Wn

(n>2)

（4）n-Cubes/n-立方图Qn

(n>0)

（5）BipartiteGraphs/二分图

CompleteBipartiteGraphs/完全二分图Kn,m1/11/202313[定理4]设无向完全图G有n个顶点，则G有n(n-1)/2条边。1/11/202314一些特殊的其他图：（1）有向完全图（2）零图（3）平凡图（4）正则图：若图Ｇ＝（Ｖ，Ｅ）中每个顶点的次均为n，称此图Ｇ是n-正则的/n-regular。（PP455T27）1/11/202315计算机处理和网络应用特殊图表示：（1）串行处理/Seriallineararraynetwork

（2）并行处理/Parallel

Kn

、Star、Cn、Wn2-dimensionalarraynetworkhypercubenetwork1/11/202316[定义]子图：Ｇ＝（Ｖ，Ｅ）是图，若Ｇ’＝（Ｖ’，Ε’）也是图且满足：

(1)Ｖ’Ｖ；(2)Ｅ’Ｅ；则称Ｇ’为Ｇ的子图/subgraph。注：当Ｖ’＝Ｖ时，称Ｇ’为Ｇ的生成子图。当Ｅ’≠Ｅ时，或Ｖ’≠Ｖ时称Ｇ’为Ｇ的真子图。1/11/202317[定义]补图：关于完全图的子图的补图称为此子图的绝对补图，若子图记为Ｇ，则补图记为。[定义]补图/complementarygraph

：Ｇ＝（Ｖ，Ｅ）是图，Ｇ’＝（Ｖ’，Ε’）是Ｇ的子图，Ｅ”＝Ｅ－Ｅ’，Ｖ”＝V－V’或是Ｅ”中边所关联的所有顶点集合，则Ｇ”＝（Ｖ”，Ｅ”）称为Ｇ’关于Ｇ的相对补图。1/11/202318图A图B1/11/202319图C图D1/11/202320图E图F1/11/202321图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｂ的边［ａ，ｂ］是孤立边图Ｄ是图Ｃ的子图图Ｆ是图Ｄ关于图Ｃ的余图图Ｅ是图Ｃ的补图（Ａ是完全图，Ｃ是Ａ的子图)1/11/202322说明：图Ｃ不是Ｅ的补图。（不互为补图）因为：

Ｅ”＝Ｅ－Ｅ’＝{[b,c],[b,d],[b,e],[c,d],[c,e],[d,e]}

Ｖ”＝{b,c,d,e}而图C多了顶点a。1/11/202323[定义]子图：