图论期末复习题(16年)ppt课件

目录第一章图的基本概念 (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积图。

图论及其应用总复习第1章图的基本概念•§1.1 图论发展史•§1.2 图的定义•§1.3 顶点的度•§1.4 子图与图的运算•§1.5一些特殊的图•§1.6 图的矩阵表示•§1.7 有向图1、图的定义图--图G=<V(G)，E(G)，ψ)>是有序三元组，其中V(G)是一个非空有限集合，E(G)与是V(G)不相交的有限集合，ψ)使E(G)中每一个元素对应于V(G)中的一个无序元素对.顶点--V(G)中的元素称为G的顶点，p(G)=|V(G)|称为G的点数.边--E(G)中的元素称为G的边，q(G)=|E(G)|称为G的边数.环--两个端点重合为一个顶点的边。

重边（平行边)--关联于同一对顶点的若干条边。

关联--如果ψ)e =uv ，则称边e 连接顶点u 和v ，u 和v 是e 的端点，u (或v )与e 关联。

相邻--点的相邻：两点间有边边的相邻：两条边有公共端点简单图--不含环和重边的图.有限图--一个图的顶点集和边集都是有限集的图.平凡图--只有一个顶点所构成的图称为平凡图.2、图的同构3、顶点的度最大度Δ(G)=max{d(v)|v∈V}最小度δ(G)=min{d(v)|v∈V}孤立顶点--度为0的顶点。

k-正则图--如果一个图中每个顶点的度是某一个固定整数k，则称该图是k-正则图。

握手定理顶点的度序列4、子图完全图--若图G 中的每一对不同顶点之间恰有一条边连接，则称图G 为完全图，记作K ;.4K 5K 3K 2K 1K 5、特殊图二分图−−G=(V>,V@;E)通常写出G=(X,Y;E),即它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中。

完全二分图--是指具有二分类（X,Y）的简单二部图，其中X 的每个顶点与Y的每个顶点相连，若|X|=p，|Y|=q，则这样的偶图记为K p,q.关联矩阵设图G=(V,E),V=v>,v@,⋯,v;,E=e>,e@,⋯,e G，则称B(G)=(b JK);×G为G的关联矩阵，其中b JK=0v J与e K不关联1v J与e K关联1次2v J与e K关联2次(即e K是以v J为端点的环)6、矩阵表示邻接矩阵设图G=(V,E),V=v>,v@,⋯,v;,用a JK表示G中顶点v J与v K之间的边数，则称M(G)=(a JK);×;为G的邻接矩阵。

离散数学图论部分期末复习辅导一、单项选择题 1．设图G ＝<V , E >，v V ，则下列结论成立的是 ( ) ．A ．deg(v )=2EB ．deg(v )=EC ．deg()2||v Vv E ∈=∑ D ．deg()||v Vv E ∈=∑解 根据握手定理（图中所有结点的度数之和等于边数的两倍）知，答案C 成立。

答 C2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110， 则G 的边数为( )．A ．6B ．5C ．4D ．3解 由邻接矩阵的定义知，无向图的邻接矩阵是对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有10个1，故有102=5条边。

答 B3．已知无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111110101110001000111010，则G 有（ ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边解 由邻接矩阵的定义知，矩阵是5阶方阵，所以图G 有5个结点，矩阵元素有14个1，14÷2=7，图G 有7条边。

答 D4．如图一所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d, e)}是边割集定义3.2.9 设无向图G =<V ,E >为连通图，若有边集E 1ÌE ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图仍是连通图，则称E 1是G 的一个边割集．若边割集为单元集{e }，则称边e 为割边（或桥）．解 割边首先是一条边，因为答案A 中的是边集，不可能是割边，因此答案A 是错误的．删除答案B 或C 中的边后，得到的图是还是连通图，因此答案B 、C 也是错误的．在图一中，删去(d , e )边，图就不连通了，所以答案D 正确． 答 D注：如果该题只给出图的结点和边，没有图示，大家也应该会做．如：若图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ) , (a , e ) , (b , c ) , (b , e ) , (c , e ) , (e , d )}，则该图中的割边是什么？5．图G 如图二所示，以下说法正确的是 ( )． A ．a 是割点 B ．{b, c}是点割集 C ．{b , d }是点割集 D ．{c }是点割集定义3.2.7 设无向图G =<V ,E >为连通图，若有点集V 1ÌV ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图仍是连通图，则称V 1是G 的一个点割集．若点割集为单元集{v }，则称结点v 为割点．οοο ο a bc d图一 οe ο οο a b c d图二ο解 在图二中，删去结点a 或删去结点c 或删去结点b 和d 图还是连通的，所以答案A 、C 、D 是错误的．在图二中删除结点b 和c ，得到的子图是不连通图，而只删除结点b 或结点c ，得到的子图仍然是连通的，由定义可以知道，{b, c }是点割集．所以答案B 是正确的． 答 B6．图G 如图三所示，以下说法正确的是 ( ) ． A ．{(a, d )}是割边 B ．{(a, d )}是边割集C ．{(a, d) ,(b, d)}是边割集D ．{(b , d )}是边割集解 割边首先是一条边，{(a, d )}是边集，不可能是割边．在图三中，删除答案B 或D 中的边后，得到的图是还是连通图．因此答案A 、B 、D 是错误的．在图三中，删去(a,d )边和(b, d )边，图就不连通了，而只是删除(a, d )边或(b, d )边，图还是连通的，所以答案C 正确．7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的复习：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；若图G 的底图，即在图G 中略去边的方向，得到的无向图是连通的，则称图G 是弱连ο ο ο a bcd图三ο通的．显然，强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不真．定理3.2.1一个有向图是强连通的，当且仅当G中有一个回路，其至少包含每个结点一次．单侧连通图判别法：若有向图G中存在一条经过每个结点至少一次的路，则G是单侧连通的。

《图论》期末考试模拟题（答案） ⼀、选择题 1、给定⽆向图如图所⽰，下⾯给出的顶点集⼦集中，是点割集的为（A,B,C,D）。

A. {b, d} B. {d} C. {a, c} D. {g, e} bf 内容需要下载⽂档才能查看 2、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（ A ）。

A. {,,,,} B. {,,,,} C. {,,,,} {,,,,} 3、⼀个连通的⽆向图G，如果它的所有结点的度数都是偶数，那么它具有⼀条（ B ）。

A. 哈密尔顿回路 B. 欧拉回路 C. 哈密尔顿通路 D. 欧拉通路 4、如图所⽰各图，其中存在哈密顿回路的图是（ A, C ）。

内容需要下载⽂档才能查看 第 1 页共 5 页 图论期末考试题⽬参考 《图论》 5. 下图中既是欧拉图，⼜是哈密尔顿图的有（D）。

5、设G是有5个顶点的完全图，则G（ B ）。

D. ⽆哈密尔顿路 E. 可以⼀笔画出 F. 不能⼀笔画出 G. 是平⾯图 6、设G是连通简单平⾯图，G中有11个顶点5个⾯，则G中的边是（ D ）。

A. 10 B. 12 C. 16 D. 14 ⼆、填空题 1、完全图K8具有（ 28 ）条边。

2、图G如图所⽰， ab fc 那么图G的割点是（ a, f ）。

e d 3、⽆向图G为欧拉图，当且仅当G是连通的，且G中⽆（奇数度）结点。

第 2 页共 5 页 图论期末考试题⽬参考 《图论》 4、连通有向图D含有欧拉回路的充分必要条件是（ D中每个结点的⼊度＝出度）。

5、 n个结点、m条边的⽆向连通图是树当且仅当m=__（3）___。

(1) n+1 (2) n (3) n-1 (4)2n-1 三、 1、设图G=(P,E) 中有12条边，6个度数为3的顶点，其余顶点的度数均⼩于3，求G⾄少有多少个顶点。

解答：设G有n个顶点，由定理1， ∑d i=1nG(vi)=2m=24 (|E|=m) 由题设 24<3×6+3(n?6) ∴ 3n>24 即 n>8 因此，G中⾄少有9个顶点。

图论期末考试题库及答案一、单项选择题1. 图论的创始人是（）。

A. 欧拉B. 莱布尼茨C. 牛顿D. 高斯答案：A2. 在图论中，一个图的顶点集合为空，但边集合不为空的图称为（）。

A. 空图B. 完全图C. 树D. 多重图答案：A3. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

A. 连通图B. 强连通图C. 弱连通图D. 无环图答案：A4. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树答案：C5. 图论中，一个图的边的集合可以划分为若干个不相交的回路，使得图中的每个顶点恰好属于其中一条回路，这样的图称为（）。

A. 欧拉图B. 哈密顿图C. 树D. 环答案：A二、多项选择题1. 下列哪些是图论中的基本术语（）。

A. 顶点B. 边D. 权重答案：ABCD2. 在图论中，以下哪些图是无向图（）。

A. 完全图B. 树C. 多重图D. 有向图答案：ABC3. 图论中，以下哪些图是连通图（）。

A. 完全图B. 树C. 多重图D. 空图答案：ABC三、填空题1. 图论中，一个图的顶点集合为V，边集合为E，那么图可以表示为G=（）。

答案：(V, E)2. 如果一个图的任意两个顶点之间都存在一条路径，则称该图为（）。

答案：连通图3. 在图论中，一个图的边的集合可以划分为若干个不相交的路径，使得图中的每个顶点恰好属于其中一条路径，这样的图称为（）。

答案：树四、简答题1. 请解释什么是图论中的“完全图”？答案：完全图是指图中每一对不同的顶点之间都恰好有一条边相连的图。

在完全图Kn中，n个顶点两两相连，共有n(n-1)/2条边。

2. 请解释什么是图论中的“欧拉路径”和“欧拉回路”？答案：欧拉路径是指图中存在一条路径，该路径恰好经过每条边一次。

欧拉回路是指图中存在一条回路，该回路恰好经过每条边一次。

五、计算题1. 给定一个图G=(V, E)，其中V={A, B, C, D, E}，E={(A, B), (B, C), (C, D), (D, E), (E, A), (A, C)}，请判断该图是否为连通图，并说明理由。