图论：图的基本概念
- 格式：pdf
- 大小：464.22 KB
- 文档页数：6
下载文档原格式
合集下载
(图论)图的基本概念--第一章
证明 设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)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。
2.只有一个顶点而无边的图称为平凡图。
3.边集为空的图称为空图。
4.既没有环也没有重边的图称为简单图。
5.其他所有的图都称为复合图。
6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。
7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。
10. 图G 的顶点的最大度。
11. k-正则图: 每个点的度均为 k 的简单图。
例如,完全图和完全偶图Kn,n 均是正则图。
12. 推论1 任意图中，奇点的个数为偶数。
13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。
15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。
16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。
图论基础知识点
基本知识点：一、图的基本定义：平凡图：只有一个顶点无边的图。
非平凡图：其他所有图。
空图：边集合为空的图。
简单图：既没有环也没有重边的图。
复合图：其他所有的图。
同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。
标定图：给图的点和边标上符号。
非标定图：不标号。
非标定图代表一类相互同构的图。
完全图：每两个不同顶点之间都有一条边相连的简单图。
N 个顶点的完全图只有一个，记为n K 。
偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。
完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。
若,X m Y n ==，则这样额完全偶图记为：,m n K 。
k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。
完全图和完全偶图,n n K 均是正则图。
图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。
子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。
生成子图：点集合相等，边集合为原图子集的图。
导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的子图V ‘。
'[]G V 和G v -。
边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。
'[]G E 和{}G e -。
图的运算：并，交，差，对称差，联图，积图，合成图，极图路与图的联通性：途径：迹：边互不相同的途径。
路：边和点都互不相同的途径。
连通的：两个顶点之间存在路。
连通图：每一对顶点之间都有一条路。
连通分支：将V 划分为一些等价类12,,...k V V V 。
两个顶点u 和v 是连通的当且仅当他们属于同一个子集i V ，称子图()i G V 为连通分支。
图论（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效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。
图论-图的基本概念
若 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.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. 图的连通性连通图：如果图中任意两点之间都存在路径，则称该图是连通图。
强连通图：有向图中，任意两个顶点之间都存在方向相同的路径，称为强连通图。
弱连通图：有向图中，去掉每条边的方向之后，所得到的无向图是连通图，称为弱连通图。
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
五、顶点的度
推论：任何图（无向图或有向图）中，度为奇数的顶点个
图论算法介绍
if （a[i,k]=1）and (a[k,j]=1) then a[i,j]=1 (a[i,j]=1表示i可达j，a[i,j]=0表示i不可达j）。
var
link，longlink：array[1..20，1..20] of boolean；{ 无向图和无向图的传递闭包。其
中
l o n g l i n k[i,
例如：公路交通图，边以距离w为权。
例
2
2
1
3
1
3
有向完全图 例
245
无向完全图 5
1
例 1
3
6
图与子图
57
32
46
G2
顶点5的度：3 顶点2的度：4
3
6
例 245
1
3
6
G1
顶点2入度：1 出度：3 顶点4入度：1 出度：0
例
路径：1，2，3，5，6，3 路径长度：5
245
简单路径：1，2，3，5
❖ 图 G = (V, E)
V = 顶点集 E = 边集 = V V的子集
结点集V＝｛a， b， c， d｝ 边集E＝｛e1， e2， e3， e4， e5｝ 其中e1＝（a， b）， e2＝（a， c），
e3＝（a， d）， e4＝（b， c）， e5＝（c， d）。
(一)、计算无向图的传递闭包
v1→v2→v4→v8→v5 →v3→v6→v7
算法结构:
调用一次dfs(i)， 可按深度优先搜索 的顺序访问处理结 点i所在的连通分 支（或强连通分 支），dfs(i)的时 间复杂度为W(n2)。 整个图按深度优先 搜索顺序遍历的过 程如下：
显然，为了避免重复访问同一个顶点，必须 记住每个顶点是否被访问过。为此，可设置 一个布尔向量visited[1..n],它的初值为 false，一旦访问了顶点vi，便将visited[i] 置为ture。 图的深度优先搜索是一个递归过程，可以使 用栈来存储那些暂时不访问的邻接点.类似于 树的前序遍历，它的特点是尽可能先对纵深 方向进行搜索，故称之深度优先搜索。
图论--图的基本概念
图论--图的基本概念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之间有⼀条边连接，则称这两个顶点相邻。
图的基本概念与握手定理
9
二、 图旳类型
注意：完全图是 n-1 正则图
完全图旳每个结点都与其他 n-1 个结点相邻接,即与 n-1条边有关联,所以是n-1正则图,反之正则图不一定 是完全图。
1.完全图：
2.正则图：
是3正则图
完全图,
不是完全图
10
二、 图旳类型
子图：
设G=<V,E>, G`=<V`,E`>为两个图，满足V` V 且E` E，则称G`为G旳子图， G为G`旳母图，记 作G`G。 (1)G`为G旳真子图：若G` G且V` V或E` E。 (2)G`为G旳生成子图：若G` G且V` = V。 (3)V1导出旳导出子图：顶点集≠V1 V,边集为 两端点均在V1中旳全体边构成旳子图。 (4) E1导出旳导出子图：≠E1E,以E1中边关联旳 顶点旳全体为顶点集旳G旳子图。
定理2 设D=<V,E>为任意有向图，V={v1,v2,…,vn}, |E|=m, 则
n
n
n
d(vi ) 2m, 且
d (vi ) d (vi ) m
i 1
i 1
i 1
16
握手定理推论及应用
推论 任何图 (无向或有向) 中，奇度顶点旳个数是 偶数.
例1 无向图G有16条边，3个4度顶点，4个3度顶 点，其他顶点度数均不大于3，问G旳阶数n为几？
分别为D旳最大出度、最小出度、最大入度、最小 入度。简记作△、、 △+、+ 、 △- 、- 。
15
四、握手定理
定理1 设G=<V,E>为任意无向图，V={v1,v2,…,vn},
|E|=m, 则
n
边 (涉及环) 都有两个端点，所以在计算G中各顶点 度数之和时，每条边均提供2度，m 条边共提供 2m 度.
图论参考答案
图论参考答案图论参考答案图论作为一门数学分支，研究的是图的性质与关系。
图由节点（顶点）和连接节点的边组成，它可以用来解决许多实际问题，如网络规划、社交网络分析等。
本文将从图的基本概念、图的表示方法、图的遍历算法以及图的应用等方面进行探讨。
一、图的基本概念图由节点和边构成，节点表示对象，边表示节点之间的关系。
图可以分为有向图和无向图两种类型。
在有向图中，边有方向，表示从一个节点到另一个节点的箭头；而在无向图中，边没有方向，表示节点之间的双向关系。
图中的节点可以用来表示不同的实体，如人、地点、物品等。
而边则表示节点之间的关系，可以是实体之间的联系、交互或者依赖关系等。
图的度是指与节点相连的边的数量。
在无向图中，节点的度等于与之相连的边的数量；而在有向图中，节点的度分为入度和出度，入度表示指向该节点的边的数量，出度表示从该节点出发的边的数量。
二、图的表示方法图可以使用邻接矩阵和邻接表两种方式进行表示。
邻接矩阵是一个二维数组，其中的元素表示节点之间的关系。
如果节点i和节点j之间有边相连，则邻接矩阵中的第i行第j列的元素为1；否则为0。
邻接矩阵的优点是可以快速判断两个节点之间是否有边相连，但是对于稀疏图来说，会浪费大量的空间。
邻接表是一种链表的形式，其中每个节点都有一个指针指向与之相连的节点。
邻接表的优点是可以有效地节省空间，适用于稀疏图。
但是在判断两个节点之间是否有边相连时，需要遍历链表，效率较低。
三、图的遍历算法图的遍历算法是指以某个节点为起点，按照一定的规则依次访问图中的所有节点。
深度优先搜索（DFS）是一种常用的图遍历算法。
它的思想是从起始节点开始，沿着一条路径一直访问到最后一个节点，然后回溯到上一个节点，继续访问其他路径。
DFS可以用递归或者栈来实现。
广度优先搜索（BFS）是另一种常用的图遍历算法。
它的思想是从起始节点开始，先访问所有与起始节点直接相连的节点，然后再依次访问与这些节点相连的节点。
图论知识点总结笔记
图论知识点总结笔记一、图的基本概念1. 图的定义图是由节点（顶点）和连接节点的边构成的一种数据结构。
图可以用来表示各种关系和网络，在计算机科学、通信网络、社交网络等领域有着广泛的应用。
在图论中，通常将图记为G=(V, E)，其中V表示图中所有的节点的集合，E表示图中所有的边的集合。
2. 节点和边节点是图中的基本单位，通常用来表示实体或者对象。
边是节点之间的连接关系，用来表示节点之间的关联性。
根据边的方向，可以将图分为有向图和无向图，有向图的边是有方向的，而无向图的边是没有方向的。
3. 度度是图中节点的一个重要度量指标，表示与该节点相连的边的数量。
对于有向图来说，可以分为入度和出度，入度表示指向该节点的边的数量，出度表示由该节点指向其他节点的边的数量。
4. 路径路径是图中连接节点的顺序序列，根据路径的性质，可以将路径分为简单路径、环路等。
在图论中，一些问题的解决可以归结为寻找合适的路径，如最短路径问题、汉密尔顿路径问题等。
5. 连通性图的连通性是描述图中节点之间是否存在路径连接的一个重要特征。
若图中每一对节点都存在路径连接，则称图是连通的，否则称图是非连通的。
基于图的连通性，可以将图分为连通图和非连通图。
6. 子图子图是由图中一部分节点和边组成的图，通常用来描述图的某个特定属性。
子图可以是原图的结构副本，也可以是原图的子集。
二、图的表示1. 邻接矩阵邻接矩阵是一种常见的图表示方法，通过矩阵来表示节点之间的连接关系。
对于无向图来说，邻接矩阵是对称的，而对于有向图来说，邻接矩阵则不一定对称。
2. 邻接表邻接表是另一种常用的图表示方法，它通过数组和链表的组合来表示图的节点和边。
对于每一个节点，都维护一个邻接点的链表，通过链表来表示节点之间的连接关系。
3. 关联矩阵关联矩阵是另一种图的表示方法，通过矩阵来表示节点和边的关联关系。
关联矩阵可以用来表示有向图和无向图，是一种比较灵活的表示方法。
三、常见的图算法1. 深度优先搜索（DFS）深度优先搜索是一种常见的图遍历算法，通过递归或者栈的方式来遍历图中所有的节点。
3图论-图基本概念9-14
边集合E＝｛<v1,v2>,<v1,v2>,<v2,v3>,<v3,v2>,<v2,v2> ,<v1,v3>,<v3,v1>｝ 尖括号 （与前面的关系的图表示相当）
3、有关图的术语 1）用G表示无向图，D表示有向图。 有时用V(G)，E(G)分别表示G的顶点集和边集， 2）用 ｜V(G)｜ ，｜E(G)｜分别表示G的顶点数和边数(有向图类似） 若｜V(G)｜ ＝n，则称G为n阶图。对有向图可做类似规定。 3）在图G中，若边集E(G)＝ø ，则称G为零图 若G为n阶图，则称G为n阶零图，记作Nn，特别是称N1为平凡图 4) 常用ek表示无向边(vi，vj)( 或有向边<vi，vj> ) 设G＝<V，E> 为无向图，ek = (vi，vj)∈E， 则称vj，vj为ek的端点， ek与vi、vj是彼此相关联的． 起终点相同的边称为环 不与任何边关联的结点称为孤立点（包括有向向图) 5）邻接： 边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的 顶点的相邻： 若∃et∈E，使得et = < vi，vj>， 则称vi为et的始点，vj为et的终点， 并称vi邻接到vj，vj邻接于vi 两个结点为一条边的端点，则称两个结点互为邻接点， 也称边关联于这两个结点，或称两个结点邻接于此边。
二、图的同构 定义 设G1＝<Vl，E1> ，G2=<V2，E2>为两个无向图(两个有向图)， 若存在双射函数f：V1 → V2 顶点的一一对应 对于∀ vi，vj∈V1，(vi，vj) ∈E1 (<vi，vj>∈ E1) 当且仅当(f(vi)，f(vj))∈E2 (<f(vi)，f(vj)> ∈E2)， 边的对应 并且(vi，vj) (<vi,vj>)与(f(vi),f(vj))(<f(vi),f(vj)>)的重数相同， 则称G1与G2是同构的，记作Gl ≅ G2
3、有关图的术语 1）用G表示无向图，D表示有向图。 有时用V(G)，E(G)分别表示G的顶点集和边集， 2）用 ｜V(G)｜ ，｜E(G)｜分别表示G的顶点数和边数(有向图类似） 若｜V(G)｜ ＝n，则称G为n阶图。对有向图可做类似规定。 3）在图G中，若边集E(G)＝ø ，则称G为零图 若G为n阶图，则称G为n阶零图，记作Nn，特别是称N1为平凡图 4) 常用ek表示无向边(vi，vj)( 或有向边<vi，vj> ) 设G＝<V，E> 为无向图，ek = (vi，vj)∈E， 则称vj，vj为ek的端点， ek与vi、vj是彼此相关联的． 起终点相同的边称为环 不与任何边关联的结点称为孤立点（包括有向向图) 5）邻接： 边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的 顶点的相邻： 若∃et∈E，使得et = < vi，vj>， 则称vi为et的始点，vj为et的终点， 并称vi邻接到vj，vj邻接于vi 两个结点为一条边的端点，则称两个结点互为邻接点， 也称边关联于这两个结点，或称两个结点邻接于此边。
二、图的同构 定义 设G1＝<Vl，E1> ，G2=<V2，E2>为两个无向图(两个有向图)， 若存在双射函数f：V1 → V2 顶点的一一对应 对于∀ vi，vj∈V1，(vi，vj) ∈E1 (<vi，vj>∈ E1) 当且仅当(f(vi)，f(vj))∈E2 (<f(vi)，f(vj)> ∈E2)， 边的对应 并且(vi，vj) (<vi,vj>)与(f(vi),f(vj))(<f(vi),f(vj)>)的重数相同， 则称G1与G2是同构的，记作Gl ≅ G2
图论第一章 图的基本概念
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
图论及其应用
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
第一章 图的基本概念
本次课主要内容
图的概念与图论模型
(一)、图论课程简介
(二)、图的定义与图论模型 (三)、图的同构 (四)、完全图、偶图与补图 (五)、顶点的度与图的度序列
0.5
00
1 0.8
0.6 0.4 x 0.2
(四)、完全图、偶图与补图
1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 .
在同构意义下，n个顶点的完全图只有一个，记为 Kn
K2
K3
K5
容易求出： m(Kn )
1 2
n(n
1)
20
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
定理：若n阶图G是自补图( G G ),则有：
n 0,1(mod 4)
证明：n阶图G是自补图，则有：
22
H G 1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
m(G)
m(G)
m(Kn )
1 2
n(n
1)
所以：
m(G) 1 n(n 1) 4
由于n是正整数，所以：n 0,1(mod 4)
推论2 正则图的阶数和度数不同时为奇数 。
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
图论及其应用
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
第一章 图的基本概念
本次课主要内容
图的概念与图论模型
(一)、图论课程简介
(二)、图的定义与图论模型 (三)、图的同构 (四)、完全图、偶图与补图 (五)、顶点的度与图的度序列
0.5
00
1 0.8
0.6 0.4 x 0.2
(四)、完全图、偶图与补图
1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 .
在同构意义下，n个顶点的完全图只有一个，记为 Kn
K2
K3
K5
容易求出： m(Kn )
1 2
n(n
1)
20
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
定理：若n阶图G是自补图( G G ),则有：
n 0,1(mod 4)
证明：n阶图G是自补图，则有：
22
H G 1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
m(G)
m(G)
m(Kn )
1 2
n(n
1)
所以：
m(G) 1 n(n 1) 4
由于n是正整数，所以：n 0,1(mod 4)
推论2 正则图的阶数和度数不同时为奇数 。
图论基础：图的基本概念和应用
图论基础：图的基本概念和应用图论是数学中的一个分支领域，研究的是图的性质和图上的问题。
图被广泛应用于计算机科学、电子工程、运筹学、社交网络分析等领域。
本文将介绍图论的基本概念和一些常见的应用。
一、图的基本概念1. 顶点和边图是由顶点和边组成的，顶点代表图中的元素，边则代表元素之间的关系。
通常顶点表示为V，边表示为E。
2. 有向图和无向图图可以分为有向图和无向图。
在无向图中，边是没有方向的，顶点之间的关系是双向的；而在有向图中，边是有方向的，顶点之间的关系是单向的。
3. 权重在一些应用中，边可能具有权重。
权重可以表示顶点之间的距离、成本、时间等概念。
有权图是指带有边权重的图，而无权图则是指边没有权重的图。
4. 路径和环路径是指由一系列边连接的顶点序列，路径的长度是指路径上边的数量。
环是一种特殊的路径，它的起点和终点相同。
5. 度数在无向图中，顶点的度数是指与该顶点相关联的边的数量。
在有向图中分为出度和入度，出度是指从该顶点出去的边的数量，入度是指指向该顶点的边的数量。
二、图的应用1. 最短路径问题最短路径问题是图论中的一个经典问题，它研究如何在图中找到两个顶点之间的最短路径。
这个问题有许多实际应用，例如在导航系统中寻找最短驾驶路径，或者在电信网络中找到最短的通信路径。
2. 最小生成树最小生成树是指一个连接图中所有顶点的无环子图，并且具有最小的边权重之和。
这个概念在电力网络规划、通信网络优化等领域有广泛的应用。
3. 路由算法在计算机网络中，路由算法用于确定数据包在网络中的传输路径。
图论提供了许多解决路由问题的算法，如最短路径算法、Bellman-Ford 算法、Dijkstra算法等。
4. 社交网络分析图论在社交网络分析中起着重要的作用。
通过构建社交网络图，可以分析用户之间的关系、信息传播、社区发现等问题。
这些分析对于推荐系统、舆情监测等领域具有重要意义。
5. 电路设计图论在电路设计中也有应用。
通过将电路设计问题转化为图论问题，可以使用图论算法解决电路布线、最佳布局等问题。
总结-图论
生成树
设 T 为无向连通图 G 中一棵生成树，e 为 T 的任意一条弦，则 T ∪e 中含 G 中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈 也不同。
设 T 是连通图 G 的一棵生成树，e 为 T 的树枝，则G 中存在只含树 枝 e，其余边都是弦的割集，且不同的树枝对应的割集也不同。
r 叉完全正则树——树叶的层数均为树高的 r 叉正则树
r 叉完全正则有序树——r 叉完全正则树是有序的的
平面图
G 是可平面图或平面图——如果能将无向图 G 画在平面 上，使得除顶 点处外无边相交。
G 的平面嵌入——画出的无边相交的平面图。 非平面图——无平面嵌入的图。
K5 和 K3,3 都不是平面图。
平面图
(1)设 T 为根树，若将 T 中层数相同的顶点都标定次序，
则称 T 为有序树。 (2)分类：根据根树 T 中每个分支点儿子数以及是否有序 r 叉树——每个分支点至多有 r 个儿子
r 叉有序树——r 叉树是有序的
r 叉正则树——每个分支点恰有 r 个儿子 r 叉正则有序树——r 叉正则树是有序的
T 是 n (n≥2) 阶有向树， (1) T 为根树— T 中有一个顶点入度为 0， 其余顶点的入度均为 1
(2) 树根——入度为 0 的顶点
(3) 树叶——入度为 1，出度为 0 的顶点 (4) 内点——入度为 1，出度不为 0 的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T 中层数最大顶点的层数 (8) 根树——平凡树(规定)
d
i 1
n
i
0( mod 2)
图的基本概念
图同构、子图、生成子图、导出子图等。
图论 第1章 图的基本概念
G
G[{e1 , e4 , e5 , e6 }]
G − {e5 , e7 }
G + {e8 }
图G1，G2的关系
设 G1 ⊆ G, G2 ⊆ G. 若 V (G1 ) V (G2 ) = φ x-disjoint） 若 E (G1 ) E (G2 ) = φ ,则称G1和G2是边不交的 （edge-disjoint） G1和G2的并, G1 G2 其中 V (G1 G2 ) = V (G1 ) V (G2 )
连通性
设 u, v 是图G的两个顶点，若G中存在一条 (u, v)
≡ v表示顶点 u 和v是连通的。 如果图G中每对不同的顶点 u , v都有一条 (u , v)
以 u
道路，则称顶点 u和 v是连通的(connected)。
道路，则称图G是连通的。
连通图
连通图
图G的每个连通子图称为G的连通分支，简
证明：G中含奇数个 1 (n − 1) 度点。 2 | Vo | 为 证明 V (G ) = Vo Ve 由推论1.3.2知， 偶数。因为 n ≡ 1(mod 4) ，所以n为奇数个。 因此，| Ve | 为奇数个。 n ≡ 1(mod 4) ， 1 2 ( n − 1) 为偶数。 1 1 d ( x ) = n − 1 − d ( x ) ≠ (n − 1) 设 x ∈Ve。若 d ( x) ≠ 2 (n − 1)，则 且 2 为偶数。由 G ≅ G c ，存在y，使得 d ( y) = d ( x) 为偶数。即 y ∈Ve 且 d ( y) ≠ 1 (n − 1) 。Ve 中度不为 2 1 (n − 1) 的点是成对的出现的。 2
G
G[{v1 , v2 , v3 }]
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
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 欧拉图
包含图的所有顶点和所有边的闭迹称为欧拉闭迹,存在一条欧拉闭迹的图称为欧拉 图 Tips:
注意：是欧拉图包含一条欧拉闭迹 (1)判定
图 G 是欧拉图当且仅当 G 是连通的且每个顶点的度都是偶数(注意偶图 的充要条件)
于是，度数都是偶数的连通图由 n 个圈构成 (2)性质
设 v 为图 G=(V,E)的任一顶点,G 中与 v 关联的边的数目称为顶点 v 的度,记为
degv.
(1)性质
1.设 G=(V,E)是一个具有 p 个顶点 q 条边的图,则 G 中各顶点度的和等于
边的条数 q 的两倍,即
∑
������
∈
������������������������
������
=
1.显然，两个顶点 u 与 v 在 Gc 中邻接,当且仅当 u 与 v 在 G 中不邻接 2.对任一有 6 个顶点的图 G,G 中或 Gc 中有一个三角形，即：在任何 6 个人的 团体中,存在 3 个互相认识的人或三个互不认识的人(P65) (2)偶图 如果 G 的顶点集 V 有一个二划分{V1,V2}；使得 G 的任一条边的两个端点一个 在 V1 中,另一个在 V2 中, 那么 G=(V,E)称为偶图，有时记为((V1,V2),E) 如果uV1,vV2 均有 uvE,则这个偶图称为完全偶图,并记为 K(m,n)或 Km,n, 其中V1=m,V2=n； 显然的，完全偶图有 m×n 条边 1.偶图又称为二分图、二部图、双图、双色图(之后会说明) 2.性质
(1)性质 (1)具有 n 个定点的有向图有 2n+1 个(?)
(2)基本术语 1.弧,对称弧---->边: 有向图的边也叫做弧。如果 x=(u,v)与 y=(v,u)均为 A 的弧,则称 x 与 y 为一对对称弧 2.弧的起点和终点---->边的端点 如果 x=(u,v)是有向图的一条边，则称弧 x 为起于顶点 u 终于顶点 v 的弧,或从 u 到 v 的弧，u 称为 x 的起点,v 为终点 3.定向图---->None 不含对称弧的 有向图称为定向图
G-S 是从 G 中去掉 S 中那些顶点后所得到的图
第六章 图的基本概念 6.2 无向图的基本定义
设 V 是一个非空集合,EP2(V), 二元组(V,E)称为一个无向图,V 中元素称为无向图 的顶点，V 为顶点集；E 的元素称为图的边，E 称为边集。(P(V)是 V 的子集) 1.基本术语
(1)简单图 如果一个图的： 1.每个顶点都没有圈 2.任意两个顶点间最多只有一条边
若 x 与 y 是图 G 的两条边,并且仅有一个公共端点,即 x∩y=1,则称边 x 与 y 邻接 (7)图的关系表示
一个无向图 G 就是一个非空集合 V 上定义的一个反自反且对称的二元关 系 E 和 V 构成的系统 (8)伪图 1.带环图
联结一个顶点与其自身的边称为环，允许有环存在的图称为带环图 2.多重边图
������������
2.任一图中,度为奇数的顶点的数目必为偶数(总度数是偶数)
3.显然,对(p,q)图的每个顶点 v,有 0≤degv≤p-1，记
������(������) = ������������������{������������������ ������}
������ ∈ ������
G+uv,它是在 G 的图解中,把 u 与 v 间联一条线而得到的图
(3)极大子图
设 G 的子图 H 具有某种性质,若 G 中不存在与 H 不同的具有此性质且包
含 H 的真子图,则称 H 是具有此性质的极大子图
Tips:
极大子图必须指明时什么性质
极大子图必须是子图
(4)导出子图
设 S 为图 G=(V,E)的顶点集 V 的非空子集,则 G 的以 S 为顶点集的极大子
图 G 的极大连通子图称为 G 的一个支(指定性质：连通)
(1)等价关系与图
复习：等价：自反/传递/对称
设 G=(V,E)是一个图,在 V 上定义二元关系 R 如下:u,vV, uRv 当且
仅当 u 与 v 之间有一条路，则 R 是 V 上的等价关系，G 的支就是关于 R
的每个等价类的导出子图(P51)
(2)如果图 G 中的两个不同顶点 u 与 v 间有两条不同路联结，则 G
中有圈
(3)设 G 是一个(p, q)连通图,则 q≥p-1
6.4 补图、偶图
(1)补图和自补图
设 G=(V,E)是一个图,图 Gc=(V, P2(V)\E)称为 G 的补图。如果 G 与其补 Gc 同 构,则称 G 是自补图
n(n ‒ 1)
显然的，Kn 有 2 条边
2.有向图简介 设 V 为一个非空有限集：A VV\{ (u,u) V }, 二元组 D=(V, A)称为一个有
向图,V 中的元素称为 D 的顶点,A 中元素(u,v)称为 D 的从 u 到 v 的弧或有向边 Tips: (1)有向图不做要求 (2)有向图中不能有自己指向自己的圈
������(������) = ������������������{������������������ ������}
������ ∈ ������
由此，定义 r 度正则图当(G)=(G)=r 4.每个三次图均有偶数个顶点。 5.度为零的顶点称为孤立顶点,0 度正则图就是零图 6.3 路、圈、连通图 1.通道，闭通道； ->迹，闭迹； ->路，回路 --------------------------------------------------------
(7)定义图的两点之间的距离：
u 和 v 是 G 的顶点。联结 u 和 v 的最短路的长称为 u 与 v
之间的距离,并记为 d(u,v)；同时，如果 u 与 v 之间没有路,则定
义 d(u,v)=∞
2.连通图
设 G=(V,E)是图,如果 G 中任两个不同顶点间至少有一条路联结,则称 G 是一
个连通图
6.6 哈密顿图 G 的生成路就是包含 G 的所有顶点的路 图 G 的一条生成路称为 G 的哈密顿路。G 的一个包含所有顶点的圈称为 G 的一个
哈密顿圈。 具有哈密顿圈的图称为哈密顿图 (1)判定 设 G 是一个有 p 个顶点的图,p≥3.如果(G)≥p/2,则 G 是一个哈密顿图 (P108) (2)性质 定义图 G-S 的支数为(G-S) 设 G=(V,E)是哈密顿图,则对 V 的每个非空子集 S,均有(G-S)≤S，其中
的图解
4.图的同构
设 G=(V,E),H=(U,F)是两个无向图.如果存在一个一一对应:VU,使得 uvE
当且仅当(u)(v)F,则称 G 与 H 同构,记为 GH
仅考虑图的几何表示，则同构的图可以在变换后重合
乌拉姆猜想
设 G=(V,E),H=(U,F)是两个图，V={v1,v2,...,vp}，U={u1,u2,...,up},p≥3. 如果对每个 i,G-viH-ui,则 GH 5.顶点的度(这是一个非常重要的概念，就像矩阵的秩一样)
������ = ������
k(������ ‒ ������)
(先从 p 个顶点中选出 k 个(k>0),一个 Kk 有 ������ 条边，于是，每条边的
去留就构成选择，由乘法原理得出)(?)
(1)真子图
G1 是图 G 的两个子图，如果 G1G,则称 G1 是 G 的真子图 (2)生成子图
设 G=(V,E)是一个图, 如果 FE,则称 G 的子图 H=(V, F)为 G 的生成子图
(2)判定
设 G=(V,E)是一个有 p 个顶点的图,若对 G 的任两个不邻接的顶点 u
和 v:degu+degv≥p-1,则 G 是连通的(P54)
(3)性质
(1)设 G=(V,E)是至少有一个顶点不是孤立顶点的图,如果uV,degu
为偶数,则 G 中有圈(简记：有边偶度就有圈)(证明：最长路)(P56)
--------------------------------------------------------
空子集且 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 欧拉图
包含图的所有顶点和所有边的闭迹称为欧拉闭迹,存在一条欧拉闭迹的图称为欧拉 图 Tips:
注意：是欧拉图包含一条欧拉闭迹 (1)判定
图 G 是欧拉图当且仅当 G 是连通的且每个顶点的度都是偶数(注意偶图 的充要条件)
于是，度数都是偶数的连通图由 n 个圈构成 (2)性质
设 v 为图 G=(V,E)的任一顶点,G 中与 v 关联的边的数目称为顶点 v 的度,记为
degv.
(1)性质
1.设 G=(V,E)是一个具有 p 个顶点 q 条边的图,则 G 中各顶点度的和等于
边的条数 q 的两倍,即
∑
������
∈
������������������������
������
=
1.显然，两个顶点 u 与 v 在 Gc 中邻接,当且仅当 u 与 v 在 G 中不邻接 2.对任一有 6 个顶点的图 G,G 中或 Gc 中有一个三角形，即：在任何 6 个人的 团体中,存在 3 个互相认识的人或三个互不认识的人(P65) (2)偶图 如果 G 的顶点集 V 有一个二划分{V1,V2}；使得 G 的任一条边的两个端点一个 在 V1 中,另一个在 V2 中, 那么 G=(V,E)称为偶图，有时记为((V1,V2),E) 如果uV1,vV2 均有 uvE,则这个偶图称为完全偶图,并记为 K(m,n)或 Km,n, 其中V1=m,V2=n； 显然的，完全偶图有 m×n 条边 1.偶图又称为二分图、二部图、双图、双色图(之后会说明) 2.性质
(1)性质 (1)具有 n 个定点的有向图有 2n+1 个(?)
(2)基本术语 1.弧,对称弧---->边: 有向图的边也叫做弧。如果 x=(u,v)与 y=(v,u)均为 A 的弧,则称 x 与 y 为一对对称弧 2.弧的起点和终点---->边的端点 如果 x=(u,v)是有向图的一条边，则称弧 x 为起于顶点 u 终于顶点 v 的弧,或从 u 到 v 的弧，u 称为 x 的起点,v 为终点 3.定向图---->None 不含对称弧的 有向图称为定向图
G-S 是从 G 中去掉 S 中那些顶点后所得到的图
第六章 图的基本概念 6.2 无向图的基本定义
设 V 是一个非空集合,EP2(V), 二元组(V,E)称为一个无向图,V 中元素称为无向图 的顶点，V 为顶点集；E 的元素称为图的边，E 称为边集。(P(V)是 V 的子集) 1.基本术语
(1)简单图 如果一个图的： 1.每个顶点都没有圈 2.任意两个顶点间最多只有一条边
若 x 与 y 是图 G 的两条边,并且仅有一个公共端点,即 x∩y=1,则称边 x 与 y 邻接 (7)图的关系表示
一个无向图 G 就是一个非空集合 V 上定义的一个反自反且对称的二元关 系 E 和 V 构成的系统 (8)伪图 1.带环图
联结一个顶点与其自身的边称为环，允许有环存在的图称为带环图 2.多重边图
������������
2.任一图中,度为奇数的顶点的数目必为偶数(总度数是偶数)
3.显然,对(p,q)图的每个顶点 v,有 0≤degv≤p-1，记
������(������) = ������������������{������������������ ������}
������ ∈ ������
G+uv,它是在 G 的图解中,把 u 与 v 间联一条线而得到的图
(3)极大子图
设 G 的子图 H 具有某种性质,若 G 中不存在与 H 不同的具有此性质且包
含 H 的真子图,则称 H 是具有此性质的极大子图
Tips:
极大子图必须指明时什么性质
极大子图必须是子图
(4)导出子图
设 S 为图 G=(V,E)的顶点集 V 的非空子集,则 G 的以 S 为顶点集的极大子
图 G 的极大连通子图称为 G 的一个支(指定性质：连通)
(1)等价关系与图
复习：等价：自反/传递/对称
设 G=(V,E)是一个图,在 V 上定义二元关系 R 如下:u,vV, uRv 当且
仅当 u 与 v 之间有一条路，则 R 是 V 上的等价关系，G 的支就是关于 R
的每个等价类的导出子图(P51)
(2)如果图 G 中的两个不同顶点 u 与 v 间有两条不同路联结，则 G
中有圈
(3)设 G 是一个(p, q)连通图,则 q≥p-1
6.4 补图、偶图
(1)补图和自补图
设 G=(V,E)是一个图,图 Gc=(V, P2(V)\E)称为 G 的补图。如果 G 与其补 Gc 同 构,则称 G 是自补图
n(n ‒ 1)
显然的，Kn 有 2 条边
2.有向图简介 设 V 为一个非空有限集：A VV\{ (u,u) V }, 二元组 D=(V, A)称为一个有
向图,V 中的元素称为 D 的顶点,A 中元素(u,v)称为 D 的从 u 到 v 的弧或有向边 Tips: (1)有向图不做要求 (2)有向图中不能有自己指向自己的圈
������(������) = ������������������{������������������ ������}
������ ∈ ������
由此，定义 r 度正则图当(G)=(G)=r 4.每个三次图均有偶数个顶点。 5.度为零的顶点称为孤立顶点,0 度正则图就是零图 6.3 路、圈、连通图 1.通道，闭通道； ->迹，闭迹； ->路，回路 --------------------------------------------------------
(7)定义图的两点之间的距离：
u 和 v 是 G 的顶点。联结 u 和 v 的最短路的长称为 u 与 v
之间的距离,并记为 d(u,v)；同时，如果 u 与 v 之间没有路,则定
义 d(u,v)=∞
2.连通图
设 G=(V,E)是图,如果 G 中任两个不同顶点间至少有一条路联结,则称 G 是一
个连通图
6.6 哈密顿图 G 的生成路就是包含 G 的所有顶点的路 图 G 的一条生成路称为 G 的哈密顿路。G 的一个包含所有顶点的圈称为 G 的一个
哈密顿圈。 具有哈密顿圈的图称为哈密顿图 (1)判定 设 G 是一个有 p 个顶点的图,p≥3.如果(G)≥p/2,则 G 是一个哈密顿图 (P108) (2)性质 定义图 G-S 的支数为(G-S) 设 G=(V,E)是哈密顿图,则对 V 的每个非空子集 S,均有(G-S)≤S，其中
的图解
4.图的同构
设 G=(V,E),H=(U,F)是两个无向图.如果存在一个一一对应:VU,使得 uvE
当且仅当(u)(v)F,则称 G 与 H 同构,记为 GH
仅考虑图的几何表示，则同构的图可以在变换后重合
乌拉姆猜想
设 G=(V,E),H=(U,F)是两个图，V={v1,v2,...,vp}，U={u1,u2,...,up},p≥3. 如果对每个 i,G-viH-ui,则 GH 5.顶点的度(这是一个非常重要的概念，就像矩阵的秩一样)
������ = ������
k(������ ‒ ������)
(先从 p 个顶点中选出 k 个(k>0),一个 Kk 有 ������ 条边，于是，每条边的
去留就构成选择，由乘法原理得出)(?)
(1)真子图
G1 是图 G 的两个子图，如果 G1G,则称 G1 是 G 的真子图 (2)生成子图
设 G=(V,E)是一个图, 如果 FE,则称 G 的子图 H=(V, F)为 G 的生成子图
(2)判定
设 G=(V,E)是一个有 p 个顶点的图,若对 G 的任两个不邻接的顶点 u
和 v:degu+degv≥p-1,则 G 是连通的(P54)
(3)性质
(1)设 G=(V,E)是至少有一个顶点不是孤立顶点的图,如果uV,degu
为偶数,则 G 中有圈(简记：有边偶度就有圈)(证明：最长路)(P56)
--------------------------------------------------------