图论-图的基本概念
- 格式：pdf
- 大小：371.95 KB
- 文档页数：15
下载文档原格式
合集下载
图论及其应用
图论及其应用简介图论是计算机科学中的一个重要分支，研究的对象是由边与顶点组成的图形结构以及与其相关的问题和算法。
图论的应用广泛，涵盖了计算机科学、网络科学、物理学、社会学、生物学等多个领域。
本文将介绍图论的基本概念、常用算法以及一些实际的应用案例。
图的基本概念图由顶点（Vertex）和边（Edge）组成，记作G=(V, E)，其中V为顶点的集合，E为边的集合。
图可以分为有向图和无向图两种类型。
有向图有向图中的边具有方向性，即从一个顶点到另一个顶点的边有明确的起点和终点。
有向图可以表示一种有序的关系，比如A到B有一条边，但B到A可能没有边。
有向图的表示可以用邻接矩阵或邻接表来表示。
无向图无向图中的边没有方向性，任意两个顶点之间都有相互连接的边。
无向图可以表示一种无序的关系，比如A与B有一条边，那么B与A之间也有一条边。
无向图的表示通常使用邻接矩阵或邻接表。
常用图论算法图论中有许多经典的算法，其中一些常用的算法包括：深度优先搜索（DFS）深度优先搜索是一种用于遍历或搜索图的算法。
通过从起始顶点开始，沿着一条路径尽可能深入图中的顶点，直到无法再继续前进时，返回上一个顶点并尝试下一条路径的方式。
DFS可以用于判断图是否连通，寻找路径以及检测环等。
广度优先搜索（BFS）广度优先搜索也是一种用于遍历或搜索图的算法。
不同于深度优先搜索，广度优先搜索逐层遍历顶点，先访问离起始顶点最近的顶点，然后依次访问与起始顶点距离为2的顶点，以此类推。
BFS可以用于寻找最短路径、搜索最近的节点等。
最短路径算法最短路径算法用于计算图中两个顶点之间的最短路径。
其中最著名的算法是迪杰斯特拉算法（Dijkstra’s A lgorithm）和弗洛伊德算法（Floyd’s Algorithm）。
迪杰斯特拉算法适用于没有负权边的图，而弗洛伊德算法可以处理带有负权边的图。
最小生成树算法最小生成树算法用于找到一个连通图的最小的生成树。
其中最常用的算法是普里姆算法（Prim’s Algorithm）和克鲁斯卡尔算法（Kruskal’s Algorithm）。
(图论)图的基本概念--第一章
证明 设G＝<V，E>为任意一图，令
V1＝{v|v∈V∧d(v)为奇数} V2＝{v|v∈V∧d(v)为偶数} 则V1∪V2＝V，V1∩V2＝ ，由握手定理可知
2m d (v) d (v) d (v)
vV
vV1
vV2
由于2m和 d (v) ，所以 d (v) 为偶数，
举例
NG(v1) ＝ {v2，v5} NG(v1) ＝ {v1，v2，v5} IG(v1) ＝ {e1，e2，e3}
Г+D(d ) ＝ {c} Г-D(d ) ＝ {a，c} ND(d ) ＝ {a，c} ND(d ) ＝ {a，c，d}
简单图与多重图
定义1.3 在无向图中，关联一对顶点的无向边如果多于1条，则 称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，并且这些 边的始点和终点相同(也就是它们的方向相同)，则称这些边 为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。
无向图和有向图
定义1 一个无向图是一个有序的二元组<V，E>,记作G，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E称为边集，它是无序积V&V的多重子集，其元素称为无向 边，简称边。
定义2 一个有向图是一个有序的二元组<V，E>，记作D，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向 边，简称边。
vV2
vV1
但因V1中顶点度数为奇数， 所以|V1|必为偶数。
问题研究
问题：在一个部门的25个人中间，由于意见不同，是否可能每 个人恰好与其他5个人意见一致？
图论（1）--图的基本概念
图论（1）--图的基本概念有向图和⽆向图的建⽴以及赋权图引⼊Q：什么是图论？A：图论是数学的⼀个分⽀。
它以图为研究对象。
图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。
现在我们来探讨⽆向图和有向图的概念以及如何去建⽴最基本的图的模型什么是图对于初⼊图论的⼈来说，复杂的定义可能会直接劝退他们，现在我来举⼀个⾮常简单的例⼦。
这就是最常见的图，由于它没有指向，即没有明确的⽅向，它被称为⽆向图。
图是由顶点和边组成的，你应该很容易就知道那些元素是顶点，那些是边。
下⾯的具有⽅向的便是有向图：若有的边有向，有的边⽆向，则称为混合图。
接下来我们将引⼊更多的概念：若两个顶点有边相连，则称两个顶点相相邻，两个点称为起点/终点或端点如1指向2，则这两个顶点相邻，这两个顶点被称为断点，⽽1被称为起点，2被称为终点。
仅含⼀个顶点的边称为⾃环在⽆向图中，包含顶点v的边的个数，称为顶点的度。
在有向图中，以v为起点的边的个数，称为点的出度，以v为终点的边的个数，称为顶点的⼊度。
⽆向图的建⽴建⽴简单⽆向图，我们使⽤Matlab，版本为R2017a。
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并⽣成⼀个图% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4]; %s为顶点，必须保证连续且从1开始的正整数t1 = [2,3,1,1]; %边 s与t之间是⼀⼀对应的G1 = graph(s1, t1);plot(G1) %画出效果图效果图：带汉字的⽆向图：% 注意字符串元胞数组是⽤⼤括号包起来的哦s2 = {'学校','电影院','⽹吧','酒店'};t2 = {'电影院','酒店','酒店','KTV'};G2 = graph(s2, t2);plot(G2, 'linewidth', 2) % 设置线的宽度% 下⾯的命令是在画图后不显⽰坐标set( gca, 'XTick', [], 'YTick', [] );效果图：有向图的建⽴：% ⽆权图 digraph(s,t)s = [1,2,3,4,1];t = [2,3,1,1,4];G = digraph(s, t);plot(G)set( gca, 'XTick', [], 'YTick', [] );注意边的顺序和⽅向，依次为1指向2,2指向3,3指向1,4指向1和1指向4效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。
图论导引参考答案
图论导引参考答案图论导引参考答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。
图由节点和边组成，节点表示对象，边表示对象之间的连接关系。
图论在计算机科学、网络分析、社交网络等领域有着广泛的应用。
本文将介绍图论的基本概念和常见算法，并提供一些参考答案来帮助读者更好地理解和应用图论。
一、图的基本概念1.1 有向图和无向图图可以分为有向图和无向图两种类型。
有向图中，边有方向，表示节点之间的单向关系；而无向图中，边没有方向，表示节点之间的双向关系。
1.2 路径和环路径是指图中一系列节点和边的连续序列，路径的长度为路径中边的数量。
如果路径的起点和终点相同，则称之为环。
1.3 连通图和连通分量在无向图中，如果任意两个节点之间都存在路径，则称该图为连通图。
连通图中的极大连通子图称为连通分量。
1.4 强连通图和强连通分量在有向图中，如果任意两个节点之间都存在路径，则称该图为强连通图。
强连通图中的极大强连通子图称为强连通分量。
二、图的存储方式2.1 邻接矩阵邻接矩阵是一种常见的图的存储方式，使用一个二维矩阵来表示图中节点之间的连接关系。
矩阵的行和列分别表示节点，矩阵中的元素表示节点之间是否存在边。
2.2 邻接表邻接表是另一种常见的图的存储方式，使用一个数组和链表的结构来表示图中节点之间的连接关系。
数组中的每个元素表示一个节点，链表中的每个节点表示与该节点相连的边。
三、常见图算法3.1 深度优先搜索（DFS）深度优先搜索是一种用于遍历图的算法。
从图中的一个节点开始，沿着一条路径一直深入直到无法继续为止，然后回溯到上一个节点，继续深入其他路径。
DFS可以用于判断图的连通性、寻找路径等问题。
3.2 广度优先搜索（BFS）广度优先搜索也是一种用于遍历图的算法。
从图中的一个节点开始，先访问其所有相邻节点，然后再依次访问这些节点的相邻节点，以此类推。
BFS可以用于计算最短路径、寻找连通分量等问题。
3.3 最小生成树算法最小生成树算法用于求解一个连通图的最小生成树，即包含图中所有节点且边的权重之和最小的子图。
图论：图的基本概念
3.子图 设 G = (V, E)是一个图，图 H = (V1, E1)称为 G 的一个子图, 其中 V1 是 V 的非
空子集且 E1 是 E 的子集 如果 G1 是 G 的子图,则说 G 包含 G1
Tips:
1.注意，顶点集合非空
∑ 2.显然的，Kn 有
p
k(k ‒ ������)
������(������,������)·2 ������ 个子图
Tips:
1.生成子图中包含原图的所有顶点
n(������ ‒ ������)
2.显然的，Kn 有2 ������ 生成子图
表示
设 x 是 G 的一条边,则 G 的生成子图(V,E\{x})简记为 G-x(生成子
图只能去边)
如果 u 和 v 是 G 的两个不邻接的顶点,则图(V,E∪{u,v})简记成
设 G 是一个连通图，则下列命题等价： (1)G 是一个欧拉图 (2)G 的每个顶点的度都是偶数 (3)G 的边集能划分成若干互相边不相交的圈
(3)延伸---欧拉迹 1.包含图的所有顶点和边的迹称为欧拉迹 判定 图 G 有一条欧拉迹当且仅当 G 是连通的且有两个奇度顶点 2.一笔画问题 若每个顶点的度均为大于或等于 2 的偶数,图又是连通的,则这个图能 一笔画出,并且最后还能回到出发点。
(2)当 v0=vn 时，则称此通道为闭通道(回路/复杂回路) (3)在计算通道的长时，重复走过的边重复计算
(4)如果一条闭通道上的各边互不相同，则此闭通道称为闭迹(简单回
路)
(5)如果闭通道上各顶点互不相同,则称此闭通道为圈,或回路(初级回
路)
(6)可见，迹和路是通道的特例，闭迹和回路是闭通道的特例。
图 G 为偶图的充分必要条件是它的所有圈都是偶数长 6.5 欧拉图
空子集且 E1 是 E 的子集 如果 G1 是 G 的子图,则说 G 包含 G1
Tips:
1.注意，顶点集合非空
∑ 2.显然的，Kn 有
p
k(k ‒ ������)
������(������,������)·2 ������ 个子图
Tips:
1.生成子图中包含原图的所有顶点
n(������ ‒ ������)
2.显然的，Kn 有2 ������ 生成子图
表示
设 x 是 G 的一条边,则 G 的生成子图(V,E\{x})简记为 G-x(生成子
图只能去边)
如果 u 和 v 是 G 的两个不邻接的顶点,则图(V,E∪{u,v})简记成
设 G 是一个连通图，则下列命题等价： (1)G 是一个欧拉图 (2)G 的每个顶点的度都是偶数 (3)G 的边集能划分成若干互相边不相交的圈
(3)延伸---欧拉迹 1.包含图的所有顶点和边的迹称为欧拉迹 判定 图 G 有一条欧拉迹当且仅当 G 是连通的且有两个奇度顶点 2.一笔画问题 若每个顶点的度均为大于或等于 2 的偶数,图又是连通的,则这个图能 一笔画出,并且最后还能回到出发点。
(2)当 v0=vn 时，则称此通道为闭通道(回路/复杂回路) (3)在计算通道的长时，重复走过的边重复计算
(4)如果一条闭通道上的各边互不相同，则此闭通道称为闭迹(简单回
路)
(5)如果闭通道上各顶点互不相同,则称此闭通道为圈,或回路(初级回
路)
(6)可见，迹和路是通道的特例，闭迹和回路是闭通道的特例。
图 G 为偶图的充分必要条件是它的所有圈都是偶数长 6.5 欧拉图
图论基础知识的名词解释
图论基础知识的名词解释图论是数学的一个分支，研究图的属性和关系。
图是由节点和节点之间的边组成的抽象模型，被广泛应用于计算机科学、网络分析、医学和社会科学等领域。
下面，我们将解释一些图论中常用的基础概念和术语。
1. 图 (Graph)图是图论研究的基本对象，由一组节点和连接这些节点的边组成。
节点也被称为顶点 (Vertex)，边则是节点之间的连接线。
图可以分为有向图 (Directed Graph) 和无向图 (Undirected Graph) 两种类型。
在有向图中，边有方向，从一个节点指向另一个节点；而在无向图中，边没有方向，节点之间的关系是双向的。
2. 顶点度数 (Degree of a Vertex)顶点度数指的是一个顶点与其他顶点相邻的边的数量。
在无向图中，顶点度数即与该顶点相连的边的数量；在有向图中，则分为入度 (In-degree) 和出度 (Out-degree)。
入度表示指向该节点的边的数量，而出度表示从该节点出发的边的数量。
3. 路径 (Path)路径指的是通过边连接的一系列节点，形成的顺序序列。
路径的长度是指路径上边的数量。
最短路径 (Shortest Path) 是指连接两个节点的最短长度的路径。
最短路径算法被广泛应用于计算机网络中的路由选择和地图导航系统中的路径规划。
4. 连通图 (Connected Graph)连通图是指图中的任意两个节点之间都存在路径的图。
如果一个图不是连通图，那么它可以被分割为多个连通分量 (Connected Component)。
连通图在社交网络分析和传感器网络等领域中具有重要的应用。
5. 完全图 (Complete Graph)完全图是指任意两个节点之间都存在边的图。
在完全图中，每对节点之间都有一条边相连。
n个节点的完全图有n(n-1)/2条边。
完全图经常用于描述需要互相交流的问题，如计算机网络中的通信。
6. 树 (Tree)树是一种无环连通图，其中任意两个节点之间有且仅有一条路径相连。
图论常考知识点总结
图论常考知识点总结1. 图的基本概念图是由顶点集合和边集合构成的。
顶点之间的连接称为边，边可以有方向也可以没有方向。
若图的边没有方向，则称图为无向图；若图的边有方向，则称图为有向图。
图的表示方式：邻接矩阵和邻接表。
邻接矩阵适合存储稠密图，邻接表适合存储稀疏图。
2. 图的连通性连通图：如果图中任意两点之间都存在路径，则称该图是连通图。
强连通图：有向图中，任意两个顶点之间都存在方向相同的路径，称为强连通图。
弱连通图：有向图中，去掉每条边的方向之后，所得到的无向图是连通图，称为弱连通图。
3. 图的遍历深度优先搜索（DFS）：从起始顶点出发，沿着一条路往前走，走到不能走为止，然后退回到上一个分支点，再走下一条路，直到走遍图中所有的顶点。
广度优先搜索（BFS）：从起始顶点出发，先访问它的所有邻居顶点，再按这些邻居顶点的顺序依次访问它们的邻居顶点，依次类推。
4. 最短路径狄克斯特拉算法：用于计算图中一个顶点到其他所有顶点的最短路径。
弗洛伊德算法：用于计算图中所有顶点之间的最短路径。
5. 最小生成树普里姆算法：用于计算无向图的最小生成树。
克鲁斯卡尔算法：用于计算无向图的最小生成树。
6. 拓扑排序拓扑排序用于有向无环图中对顶点进行排序，使得对每一条有向边(u,v)，满足排序后的顶点u在顶点v之前。
以上就是图论中一些常考的知识点，希望对大家的学习有所帮助。
当然，图论还有很多其他的知识点，比如欧拉图、哈密顿图、网络流等，这些内容都值得我们深入学习和探讨。
图论在实际应用中有着广泛的应用，掌握好图论知识对于提升计算机科学和工程学的技能水平有着重要的意义。
图论讲义-图的基本概念
到目前为止，判断两图同构 还只能从定义出发。判断过 程中不要将两图同构的必要 条件当成充分条件。
注意：在研究图的过程中，顶点的位置以及边的曲直长短 都是无关紧要的。而且也没有假定这些顶点和边都要在一 个平面上（正方体的顶点和棱也可构成图）。我们研究的 只是顶点的多少及这些边是连接那些顶点的。
五、顶点的度
若e=(u,v)，则表示u到v的一条边（Edge），此时的
图称为无向图(Undigraph)。
有向图（Digraph）、无向图(Undigraph)
V1 V4
V1
V5 V2 V3 V2 V3
V4
有向图（Digraph）、无向图(Undigraph)
例1、设V={v1,v2,v3,v4,}，E={e1,e2,e3,e4,e5}，满足e1=(v1,v2)，
六、路与图的连通性
v1 v2 v5
图G中，取Γ1=v1v2v3，
v3
v4
G
Γ2=v1v2v3v4v2， Γ3=v1v2v3v2v3v4 则 Γ1,Γ2,Γ3依次为长为2,4,5的 通路，其中Γ1与Γ2为简单通路， Γ1为基本通路。 由定义可看出,G中v1v2v5v1为 长为3的圈，v1v2v3v4v2v5v1为 长为6的简单回路。
e2=(v2,v3)，e3=(v2,v3)，e4=(v3,v4)，e5=(v4,v4),则G=(V,E)是一个图。图 中边集E的边也可直接由点对表示，而将E作为多重集（即允许E中有相同元素的 集合）。 例2、设V={v1,v2,v3,v4}，E={(v1,v2)，(v1,v2)，(v2,v3)}，则H=(V,E)是 一个图。 e
d (V ) 2m
i 1 i
n
五、顶点的度
推论：任何图（无向图或有向图）中，度为奇数的顶点个
图论--图的基本概念
图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。
注意：元素可以重复出现的集合称作多重集合。
某元素重复出现的次数称作该元素的重复度。
例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。
从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。
1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。
通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。
与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。
通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。
⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。
（2）顶点数称作图的阶，n个顶点的图称作n阶图。
（3）⼀条边也没有的图称作零图，n阶零图记作N n。
1阶零图N1称作平凡图。
平凡图只有⼀个顶点，没有边。
（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。
（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。
（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。
（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。
图论参考答案
图论参考答案图论参考答案图论作为一门数学分支，研究的是图的性质与关系。
图由节点（顶点）和连接节点的边组成，它可以用来解决许多实际问题，如网络规划、社交网络分析等。
本文将从图的基本概念、图的表示方法、图的遍历算法以及图的应用等方面进行探讨。
一、图的基本概念图由节点和边构成，节点表示对象，边表示节点之间的关系。
图可以分为有向图和无向图两种类型。
在有向图中，边有方向，表示从一个节点到另一个节点的箭头；而在无向图中，边没有方向，表示节点之间的双向关系。
图中的节点可以用来表示不同的实体，如人、地点、物品等。
而边则表示节点之间的关系，可以是实体之间的联系、交互或者依赖关系等。
图的度是指与节点相连的边的数量。
在无向图中，节点的度等于与之相连的边的数量；而在有向图中，节点的度分为入度和出度，入度表示指向该节点的边的数量，出度表示从该节点出发的边的数量。
二、图的表示方法图可以使用邻接矩阵和邻接表两种方式进行表示。
邻接矩阵是一个二维数组，其中的元素表示节点之间的关系。
如果节点i和节点j之间有边相连，则邻接矩阵中的第i行第j列的元素为1；否则为0。
邻接矩阵的优点是可以快速判断两个节点之间是否有边相连，但是对于稀疏图来说，会浪费大量的空间。
邻接表是一种链表的形式，其中每个节点都有一个指针指向与之相连的节点。
邻接表的优点是可以有效地节省空间，适用于稀疏图。
但是在判断两个节点之间是否有边相连时，需要遍历链表，效率较低。
三、图的遍历算法图的遍历算法是指以某个节点为起点，按照一定的规则依次访问图中的所有节点。
深度优先搜索（DFS）是一种常用的图遍历算法。
它的思想是从起始节点开始，沿着一条路径一直访问到最后一个节点，然后回溯到上一个节点，继续访问其他路径。
DFS可以用递归或者栈来实现。
广度优先搜索（BFS）是另一种常用的图遍历算法。
它的思想是从起始节点开始，先访问所有与起始节点直接相连的节点，然后再依次访问与这些节点相连的节点。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
若 i, j 中有奇数，比如 i 是奇数，则路 P 上 v0 到 vi 的一段与边 v0vi 构成一个偶圈； 若 i, j 都是偶数，则路 P 上 vi 到 v j 的一段与边 v0vi 及 v0v j 构成一个偶圈。证毕。 例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2。 证明：由上例知，G 中有长分别为 i + 1, j + 1和 j − i + 2 的圈。若 i + 1, j + 1， j − i + 2 三 数有公因数 m > 2 ，则 m | ( j − i) ，于是 m | 2 ，这是不可能的。因此 i + 1, j + 1， j − i + 2
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
注： （1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。 （2）简单图 G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。
（3）对任意 x, y ∈V (G) ，从 x 到 y 的具有最小长度的路称为 x 到 y 的最短路（shortest path）， 其长度称为 x 到 y 的距离(distance)，记为 dG ( x, y) 。 （4）图 G 的直径(diameter): D = max{dG ( x, y) |∀x, y ∈V (G)} .
5. 路和圈
途径(walk)：图 G 中一个点边交替出现的序列 w = v e v e i0 i1 i1 i2 ⋯eik vik 。
迹(trail)：边不重的途径。 路(path): 顶点不重复的迹。
（注：简单图中的路可以完全用顶点来表示， P = v vi0 i1 ⋯vik ）
闭途径（closed walk）：起点和终点相同的途径。 闭迹(closed trail)：起点和终点相同的迹，也称为回路（circuit）. 圈(cycle): 起点和终点相同的路。
点导出子图(induced subgraph)：设V ′ ⊆ V (G) ，以V ′ 为顶点集，以两端点均在V ′ 中的边 的全体为边集所组成的子图，称为 G 的由顶点集V ′ 导出的子图，简称为 G 的点导出子图， 记为 G[V ′] .
边导出子图(edge-induced subgraph)：设 E′ ⊆ E(G) ，以 E′ 为顶点集，以两端点均在 E′ 中 的边的全体为边集所组成的子图，称为 G 的由边集 E′ 导出的子图，简称为 G 的边导出子图， 记为 G[E′].
图论与网络流理论
（Graph Theory and Network Flow Theory）
主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问 题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
内容提要
第一章 图的基本概念
图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。
第六章 图的着色问题
点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章 网络流理论
有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费 用流问题；最小费用最大流；网络流理论的应用。
主要参考书
[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [3] 蒋长浩，图论与网络流，中国林业出版社，2001。 [4] 田丰，马仲蕃，图与网络流理论，科学出版社，1987。 [5] 徐俊明，图论及其应用，中国科技大学出版社，1998。 [6] 王树禾，图论及其算法，中国科技大学出版社，1994。 [7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。 考核方式：平时成绩＋期末闭卷笔试
和 Y。
（2）否则，设 u′ 是 P 与 Q 的最后一个公共顶点，因 P 的 (u, u′) 段和 Q 的 (u, u′) 段都是 u 到 u′ 的最短路，故这两段长度相等。
假如 P，Q 的奇偶性相同，则 P 的 (u′, v1) 段和 Q 的 (u′, v2 ) 段奇偶性相同，这两段与边 e 构成一个奇圈，与定理条件矛盾。可见 P，Q 的奇偶性不同，从而 v1, v2 分属于 X 和 Y。
完全二部图(complete bipartite graph)：在二部图 G = ( X ∪ Y , E) 中，若 X 的每个顶点与 Y 的每个顶点有边连接，则称 G 为完全二部图；若 | X |= m ， | Y |= n ，则记此完全二部图为 Km,n 。
定理 1.1.2 一个图是二部图当且仅当它不含奇圈。
8. 图的同构
由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图
第二章 图的连通性
割点、割边和块；边连通与点连通；连通度；Whitney 定理；可靠通信网络的设计。
第三章 匹配问题
匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图
欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团
支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
X = {v ∈V (G) | d (u, v)＝odd} ，Y = {v ∈V (G) | d (u, v)＝even}。 任取一条边 e = v1v2 ，欲证 v1, v2 分属于 X 和 Y。设 P，Q 分别是 u 到 v1, v2 的最短路。 （1）如果 P = Q + v2v1 或 Q = P + v1v2 ，则 v1, v2 到 u 的距离奇偶性相反， v1, v2 分属于 X这便证明了 G 是一个二 Nhomakorabea图。 证毕。
7. 连通性 图中两点的连通：如果在图 G 中 u，v 两点有路相通，则称顶点 u，v 在图 G 中连通。 连通图（connected graph）：图 G 中任二顶点都连通。 图的连通分支（connected branch, component）：若图 G 的顶点集 V(G)可划分为若干非空子集
圈。证毕。
例 1.1.3 设 G 是简单图，若δ (G) ≥ 3 ,则 G 必有偶圈。
证明：设 P = v0v1 ⋯vk 是 G 的最长路。 因为 d (v0 ) ≥ 3 ， 所以存在两个与 v1 相异的顶点 v′, v′′ 与 v0 相邻。 v′, v′′ 必都在路 P 上，
否则会得到比 P 更长的路。无妨设 v′ = vi , v′′ = v j , (i < j) 。
证明： 必要性：设 C = v0v1 ⋯vk v0 是二部图 G = ( X ∪ Y , E) 的一个圈。无妨设 v0 ∈ X ， 由二部图的定义知， v1 ∈ Y ， v2 ∈ X ， ⋯，一般地， v2i ∈ X ， v2i+1 ∈Y ，（ i = 0,1,⋯）。 又因 v0 ∈ X ，故 vk ∈Y ，因而 k 是奇数。注意到圈 C 上共有 k + 1 条边，因此是偶圈。 充分性：设 G 不含奇圈。取 u ∈V (G) ，令
V1,V2 ,⋯,Vω ，使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图 G[Vi ] 为 图 G 的一个连通分支（ i = 1,2,⋯,ω ）。
注：（1）图 G 的连通分支是 G 的一个极大连通子图。
（2）图 G 连通当且仅当ω＝1。
例 1.1.5 设有 2n 个电话交换台，每个台与至少 n 个台有直通线路，则该交换系统中任二台均 可实现通话。 证明：构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线
路。问题化为：已知图 G 有 2n 个顶点，且δ (G) ≥ n ，求证 G 连通。
事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。在此连通分支中，
顶点的度至多是 n − 1 。这与δ (G) ≥ n 矛盾。证毕。
例 1.1.6 若图中只有两个奇度顶点，则它们必连通。 证明：用反证法。假如 u 与 v 不连通，则它们必分属于不同的连通分支。将每个分支看成一 个图时，其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。
三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。
6. 二部图 二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得任一条边都
有一个端点在 X 中，另一个端点在 Y 中，则称 G 为二部图（或偶图），记为 G＝ ( X ∪ Y , E) ， ( X ,Y ) 称为 G 的一个划分。
（12）正则图(regular graph)：每个顶点的度都相等的图。
（13）图的补图(complement)：设 G 是一个图，以V (G) 为顶点集，以{(x, y) | (x, y) ∉ E(G)} 为边集的图称为 G 的补图，记为 G 。
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
注： （1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。 （2）简单图 G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。
（3）对任意 x, y ∈V (G) ，从 x 到 y 的具有最小长度的路称为 x 到 y 的最短路（shortest path）， 其长度称为 x 到 y 的距离(distance)，记为 dG ( x, y) 。 （4）图 G 的直径(diameter): D = max{dG ( x, y) |∀x, y ∈V (G)} .
5. 路和圈
途径(walk)：图 G 中一个点边交替出现的序列 w = v e v e i0 i1 i1 i2 ⋯eik vik 。
迹(trail)：边不重的途径。 路(path): 顶点不重复的迹。
（注：简单图中的路可以完全用顶点来表示， P = v vi0 i1 ⋯vik ）
闭途径（closed walk）：起点和终点相同的途径。 闭迹(closed trail)：起点和终点相同的迹，也称为回路（circuit）. 圈(cycle): 起点和终点相同的路。
点导出子图(induced subgraph)：设V ′ ⊆ V (G) ，以V ′ 为顶点集，以两端点均在V ′ 中的边 的全体为边集所组成的子图，称为 G 的由顶点集V ′ 导出的子图，简称为 G 的点导出子图， 记为 G[V ′] .
边导出子图(edge-induced subgraph)：设 E′ ⊆ E(G) ，以 E′ 为顶点集，以两端点均在 E′ 中 的边的全体为边集所组成的子图，称为 G 的由边集 E′ 导出的子图，简称为 G 的边导出子图， 记为 G[E′].
图论与网络流理论
（Graph Theory and Network Flow Theory）
主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问 题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
内容提要
第一章 图的基本概念
图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。
第六章 图的着色问题
点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章 网络流理论
有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费 用流问题；最小费用最大流；网络流理论的应用。
主要参考书
[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [3] 蒋长浩，图论与网络流，中国林业出版社，2001。 [4] 田丰，马仲蕃，图与网络流理论，科学出版社，1987。 [5] 徐俊明，图论及其应用，中国科技大学出版社，1998。 [6] 王树禾，图论及其算法，中国科技大学出版社，1994。 [7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。 考核方式：平时成绩＋期末闭卷笔试
和 Y。
（2）否则，设 u′ 是 P 与 Q 的最后一个公共顶点，因 P 的 (u, u′) 段和 Q 的 (u, u′) 段都是 u 到 u′ 的最短路，故这两段长度相等。
假如 P，Q 的奇偶性相同，则 P 的 (u′, v1) 段和 Q 的 (u′, v2 ) 段奇偶性相同，这两段与边 e 构成一个奇圈，与定理条件矛盾。可见 P，Q 的奇偶性不同，从而 v1, v2 分属于 X 和 Y。
完全二部图(complete bipartite graph)：在二部图 G = ( X ∪ Y , E) 中，若 X 的每个顶点与 Y 的每个顶点有边连接，则称 G 为完全二部图；若 | X |= m ， | Y |= n ，则记此完全二部图为 Km,n 。
定理 1.1.2 一个图是二部图当且仅当它不含奇圈。
8. 图的同构
由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图
第二章 图的连通性
割点、割边和块；边连通与点连通；连通度；Whitney 定理；可靠通信网络的设计。
第三章 匹配问题
匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图
欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团
支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
X = {v ∈V (G) | d (u, v)＝odd} ，Y = {v ∈V (G) | d (u, v)＝even}。 任取一条边 e = v1v2 ，欲证 v1, v2 分属于 X 和 Y。设 P，Q 分别是 u 到 v1, v2 的最短路。 （1）如果 P = Q + v2v1 或 Q = P + v1v2 ，则 v1, v2 到 u 的距离奇偶性相反， v1, v2 分属于 X这便证明了 G 是一个二 Nhomakorabea图。 证毕。
7. 连通性 图中两点的连通：如果在图 G 中 u，v 两点有路相通，则称顶点 u，v 在图 G 中连通。 连通图（connected graph）：图 G 中任二顶点都连通。 图的连通分支（connected branch, component）：若图 G 的顶点集 V(G)可划分为若干非空子集
圈。证毕。
例 1.1.3 设 G 是简单图，若δ (G) ≥ 3 ,则 G 必有偶圈。
证明：设 P = v0v1 ⋯vk 是 G 的最长路。 因为 d (v0 ) ≥ 3 ， 所以存在两个与 v1 相异的顶点 v′, v′′ 与 v0 相邻。 v′, v′′ 必都在路 P 上，
否则会得到比 P 更长的路。无妨设 v′ = vi , v′′ = v j , (i < j) 。
证明： 必要性：设 C = v0v1 ⋯vk v0 是二部图 G = ( X ∪ Y , E) 的一个圈。无妨设 v0 ∈ X ， 由二部图的定义知， v1 ∈ Y ， v2 ∈ X ， ⋯，一般地， v2i ∈ X ， v2i+1 ∈Y ，（ i = 0,1,⋯）。 又因 v0 ∈ X ，故 vk ∈Y ，因而 k 是奇数。注意到圈 C 上共有 k + 1 条边，因此是偶圈。 充分性：设 G 不含奇圈。取 u ∈V (G) ，令
V1,V2 ,⋯,Vω ，使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图 G[Vi ] 为 图 G 的一个连通分支（ i = 1,2,⋯,ω ）。
注：（1）图 G 的连通分支是 G 的一个极大连通子图。
（2）图 G 连通当且仅当ω＝1。
例 1.1.5 设有 2n 个电话交换台，每个台与至少 n 个台有直通线路，则该交换系统中任二台均 可实现通话。 证明：构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线
路。问题化为：已知图 G 有 2n 个顶点，且δ (G) ≥ n ，求证 G 连通。
事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。在此连通分支中，
顶点的度至多是 n − 1 。这与δ (G) ≥ n 矛盾。证毕。
例 1.1.6 若图中只有两个奇度顶点，则它们必连通。 证明：用反证法。假如 u 与 v 不连通，则它们必分属于不同的连通分支。将每个分支看成一 个图时，其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。
三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。
6. 二部图 二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得任一条边都
有一个端点在 X 中，另一个端点在 Y 中，则称 G 为二部图（或偶图），记为 G＝ ( X ∪ Y , E) ， ( X ,Y ) 称为 G 的一个划分。
（12）正则图(regular graph)：每个顶点的度都相等的图。
（13）图的补图(complement)：设 G 是一个图，以V (G) 为顶点集，以{(x, y) | (x, y) ∉ E(G)} 为边集的图称为 G 的补图，记为 G 。