第八章 图论
第八章图论
1.名词解释
1．邻接点:
2．邻接边:
3．平行边:
2.名词解释
1．零图
2．平凡图
3．简单图:.
4．多重图:
3.填空：G是个无向图, v∈V(G), 结点v所关联边数，称之为( )。记作( )。
4.填空：G=
Δ(G) =( )，δ(G) =（）。
5. 简答题：无向图G=
6. 无向图中,奇数度的结点有多少个？为什么？
7.选择题：在一次集会中，与奇数个人握手的人数共有( )个。
供选择的答案：A；奇数；B：不能确定；C：偶数；D：不知道。
8. 下面哪些数的序列不是一个图的结点度数序列?为什么？如果可能是一个图的结点度数序列,请试画出它的图。哪些可能不是简单图的结点度序列?为什么？a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4)
d) (1,1,1,1,4) e) (1,2, 2,4,5)
9. .已知无向简单图G中，有10条边，,4个3度结点，其余结点的度均小于或等于2。问G中至少有多少个结点?为什么?
10. 无向图G中有16条边，每个结点都是2度结点。问G中有几个结点？为什么？
11.无向图G中有21条边，3个4度结点，其余都是3度结点。问G中有几个结点？为什么？
12. 无向简单图G中有10条边，各个结点的度数相同。问G中有几个结点？为什么？答案唯一吗？如果唯一，说明理由。如果不唯一，请列出所有可能的答案。
13. 在具有n个结点的无向简单图G中，δ(G) =n－1，问Δ(G) 应为多少？为什么？
14．构造简单图G使之分别满足：
1．k(G)=λ(G)=δ(G)
2．k(G)=λ(G)<δ(G)
3．k(G)<λ(G)=δ(G)
15.名词解释
G=
1．有向图结点v的出度：
2．有向图结点v的入度：
3．有向图结点v的度：
16. G=
17. 填空题：设G是有向简单图，其结点度数序列为(2,2,3,3)，入度序列为(0,0,2,3)。求它的出度序列( )。
18. 什么叫无向完全图？有n个结点的无向完全图记作什么？它有多少条边？
19. 有n个结点的无向完全图Kn有多少条边？为什么？
20 什么叫有向简单完全图？有n个结点的有向简单完全图它有多少条边？为什么？
21. 什么叫有向完全图？有n 个结点的有向完全图它有多少条边？为什么？
22. 证明任何有向简单完全图中，所有结点的入度平方之和等于所有结点出度平方之和。
23. 设G 是个具有n 个结点的有向简单图。G ’是G 的子图，且G ’中边’m’＝n(n －1)。问G 中边数m 为多少？要求有解题过程。
24. 什么叫生成子图（支撑子图）？
25. 什么叫图G 的补图？
26. 给定G 如下图所示，求G 的补图。
27. 画出下面图G 的补图G 。
28. 设G 是个有n 个结点的简单图，n 是个大于2的奇数，如果G 中有k 个奇数度的结点，那么G 的补图G 中有奇数度的结点也是k 个。此说法正确吗?为什么?
G
29. 什么叫做图的同构？
30. 填空：图之间的同构关系?满足( )性质，是( )关系。
31. 指出下面各个图中哪些是彼此同构的.
32.给定图的集合G={A,B,C,D,E,F,H,K,M,N,R,S,T,V ,W,X,Y},
其中各个图如下，?
是G 中图的同构关系，求商集G/?。
33. 具有1、2、3个结点的简单图各有多少种不同构的形式？试画出这些图形。
34.具有4个结点的简单图各有多少种不同构的形式？试画出这些图形。
a b
d f g h i c
e j
35. 画出K4的所有不同构的生成子图。
36. 什么叫做自补图？
37. 多于两个而少于或等于6个结点的简单图中，哪些图可能是自补图？对不是自补图的要说明原因。对有自补图的，要画出所有可能的自补图。
38. 下面哪些图同构？（只标出结点之间的对应关系即可。）
39. 下面哪些图同构？（只标出结点之间的对应关系即可。）
(a) (b) (c) (d)
a
b c
40. 给定图G=
41.名词解释：回路:
42.名词解释： 1．迹 2．闭迹
43.名词解释： 1．通路 2．圈
44. 请回答“什么是无向图的连通分支？什么叫做连通分支数？G 的连通分支数用什么表示？”
45. 什么叫做无向连通图？
46. 给定三个无向图G 1、G 2、G 3如下图所示，分别求它们的连通分支数。
47. 证明如果图G 是不连通的,则它的补图G 是连通的.
48. 说明：什么叫做点割集？什么叫做割点？
49. 什么叫做点连通度？用什么符号表示点连通度？它表示什么含义？
g
a
b
e
f
d
G 1
G 2
G 3
50. 说明：什么叫做边割集？什么叫做割边？割边也称之为什么？
51. 说明：什么叫做边连通度？用什么符号表示？它表示什么含义？
52. 填空：在有向图中，从u 到v 可达定义为( )。
53. 在有向图中，从u 到v 的距离是任何定义的？用什么符号表示？
54.填空：下面是讲述有向图结点的可达性时的几个结论。请在括号内填入适当的符号。
可达性的性质:（u,v,w 是有向图中的结点。） 1) d
3) d
4) 如果从u 到v 不可达,则d
5) 如从u 可达v ，从v 也可达u, d
55. 给定有向图如下：
在这个图中找出分别满足下面结论的结点。 1) d
3) 如从u 可达v ，从v 也可达u, d
56. 有向图G 的直径是如何定义的？下面的有向图的直径是多少？为什么？
d
c
a
b
d
c
a
b
57. 名词解释：
1．强连通 2．单侧连通 3．弱连通
58. 下面给出三个有向图，分别说出它们是哪种连通图。并说明原因。
59.求下面有向图G 的强分图,单侧分图和弱分图。
60. 求下面有向图G 的强分图,单侧分图和弱分图。
61. 给出有向图如图所示，分别指出它的强分图、单侧分图和弱分图。
5
1
4 6 2
3 e
d
h
a
d
c
a
c
a
c
a
(a)
(b)
(c)
e
62. 证明有向图中,每个结点必位于一个且只位于一个强分图中。
63从无向图的邻接矩阵能看出该图哪些特征？
64.从有向图的邻接矩阵能看出该图哪些特征？
65. 给定无向图G 如下图所示：
1．写出G 的邻接矩阵A 。
2. 求A 的平方A 2
。
3．在A 2
矩阵中的第3行，第4列元素为多少？对于这个数字在G 的图上
你能做何解释？对你的解释在图上明确表示出来。
66. 设G=
中的第 i 行第j 列元素m, 对此你在G 的图上做何解释。
67. 求下面图的邻接矩阵,可达矩阵和距离矩阵。
v 2
v 5
v 4
v 3 v 1
v 5
v 4
v 2 v 3
G
68. 设G=
69. 求下面无向图的完全关联矩阵。
70. 从无向图关联矩阵能够看到图的哪些特征？如何看出这些特征？
71.设G=
72. 求下面有向图的完全关联矩阵。
v
v
5
v 4 v 2
e 5
6
v 5
v 4
v 2
v 3
e 6
73. 从有向图关联矩阵能够看到图的哪些特征？如何看出这些特征？
74.名词解释
1．欧拉路：
2. 欧拉回路：
3．欧拉图：
75..有欧拉路的判定:
76. 无向图G具有欧拉回路,的判定
77. 构造一个欧拉图,使得结点数v和边数e满足:
a) v,e奇偶性一样. b) v,e奇偶性相反.
78. n取何值时,完全图Kn是个欧拉图？
79. 名词解释
1．汉密尔顿路：
2．汉密尔顿回路(H回路)：
3．汉密尔顿图(H图)：
80. a) 画一个有一条欧拉回路和一条汉密尔顿回路的图。
b) 画一个有一条欧拉回路但没有一条汉密尔顿回路的图。
c) 画一个没有一条欧拉回路但有一条汉密尔顿回路的图。
81. 首先判断下面命题的正误，然后说明原因。
“不是所有完全图Kn都是欧拉图，但是所以完全图Kn都是汉密尔顿图。”82. 填空：这是判定一个图有汉密尔顿路和汉密尔顿回路的定理。“设G是有n个
结点的简单无向图，若G 中每对结点度数之和大于或等于( )，则G 有一条汉密尔顿路。若G 中每对结点度数之和大于或等于 ( )，则G 有一条汉密尔顿回路。”
83. 填空：这是判定一个图有汉密尔顿回路的必要条件定理。“若图G=
用此定理判断下面图G 不是H 图。
85. 今有a,b,c,d,e,f,g 七个人,已知下列事实: a :会讲英语。 b :会讲英语和汉语。
c :会讲英语、意大利语和俄语。
d :会讲日语和汉语。
e :会讲德语和意大利语。
f :会讲法语、日语和俄语。
g :会讲法语和德语。
试问能否将这七个人适当安排座位,使得每个人都能与他两边的人直接交谈? 如果能,请给予安排；如果不能,说明原因。(用图论的理论求解。)
86. 给定图G 如图所示，G 是欧拉图还是汉米尔顿图，若是请写出一条相应的回路。如果不是，请说明理由。
87. 什么叫做平面图？什么叫做一个图是可以平面化的？
88. 说明:K 5和K 3,3不是平面图。
f
g
89. 名词解释
1．平面图的面
2．面的边界
3．面的次数
90.平面图的面分有限面与无限面，请问无限面的边界是由无数条边围成的吗？为什么？答
91.给定平面图如下，求各个面的边界，以及各个面的次数。
92.请说明欧拉公式。
93.说明叫做-在2度结点内同构(同胚)。
94.请画出两个图，使得它们不同构，但在2度结点内同构。
95.请说出判定一个平面图的充分且必要条件, 即Kuratowski(库拉托斯基)定理。
96. 用Kuratowski(库拉托斯基)定理说明下面彼得森(Petersen)图不是平面图。
97. 证明：在6个结点12条边的连通平面简单图中，每个面由3条边围成.
98. 证明：若G 是每一个面至少由k(k ≥3)条边围成的连通平面图，则2
)2(--≤
k v k e ,
这里v,e 分别是G 的结点数和边数。
99.给定定理：若G 是每一个面至少由k(k ≥3)条边围成的连通平面图，则
)2(-≤
v k e ,这里v,e 分别是G 的结点数和边数。用此定理说明K 5和K 3,3不是平面
图。
100. 如果可能, 把下面画成平面图,否则说明它包含一个与K 5或K 3,3在2度结点内同构子图。
v 1 v 6
v 2 v 5
v 8 v 9
v 3 v 4
v 7
v 10
101. 证明a) 对于K5中任何边e, K5 -e 是平面图。
b) .对于K3,3中任何边e, K3,3 -e 是平面图。
102.证明小于30条边的平面简单图G有一个结点度数小于等于4。
103. 设G是个有n (n 2)个连通分支的平面图，则G的结点数v，边数e，以及面数r之间是什么关系？并给予证明之。
104.填空：共5个空白，括号内分别标有1，2，3，4，5。
下面是对偶图(偶图)的定义：
给定平面图G=
⑴对于G的任意平面Fi 的内部有且仅有一个结点vi*∈( 1 )。
⑵对于图G的面Fi与Fj的公共边界e k,有且仅有一条边e k*∈E* ,使得
e k*=(vi*,vj*), 且e k*与e k（ 2 ）。(其中vi*在( 3 )内, vj*在( 4 )内。)
⑶当且仅当e k只是一个面Fi的边界时, v i*上有一个( 5 )e k* 与e k相交。则称图G*是G的对偶图。
105. 什么叫做自对偶图？请画一个图和它的自对偶图。
106.画出下面各图的对偶图。
107.画出下面各图的对偶图。
108. 判断真值，说明理由：
一个图的结点数少于或等于5，并且含有一个2度结点，它一定是平面图。109.G是个连通平面图，G与其对偶图同构(称之为自对偶图)。如果G有v个结点，则G有多少条边？为什么？
110.什么叫做图G的正常着色(简称着色)？什么叫做G的着色数？
111. 用韦尔奇.鲍威尔法,对下面各图着色. 求图的着色数.
112. 一个完全图K 6 的边涂上红色或者蓝色，证明对于任何一种随意涂边的方法，总有一个完全图K 3 的所有边被涂上红色，或者涂上蓝色。
113. 证明6个人的人群中,或者有3个人相互认识,或者有3个人彼此陌生.
114. 名词解释
1．树： 2．叶结点：
3．分支结点(内结点)： 4．森林：
115. T 是树，证明 e=v-1。其中e 是T 的边数，v 是T 的结点数。
116. T 是个无回路图，且e=v-1。其中e 是T 的边数，v 是T 的结点数。证明T 是树。
A
E
117. 设T是个连通图，且e=v-1。证明T无回路且任意添加一条新边则得到一条仅有的回路。
118. 设图T无回路，但在任意两个结点之间添加一条新边则得到一条仅有的回路。证明T是连通的。但删去任一条边，T便不连通。
119. 已知图T是连通的，但删去任一条边，T便不连通。证明每对结点之间有一条且仅有一条路。
120. 已知图T中每对结点之间有一条且仅有一条路，证明T是树。
121. 一棵树T有n2个结点度数为2，n3个结点度数为3，…n k个结点度数为k，问它有多少个度数为1的结点?
122. 一棵树T有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有多少个度数为1的结点?
123．一棵树有n个结点，其中所有分支结点的度数均为k, 问它有多少个叶结点？为什么？
124. 一棵树有7片树叶，3个3度结点，其余都是4度结点，问该树有多少4度结点？
125. 一棵树有2个4度结点，3个3度结点，其余都是树叶，问该树有多少片树叶？
126. 六个结点的不同构的无向树有多少棵？请分别画出这些树。
127. 画出8个结点所有不同构的树。
128. 有8个结点的无向树中，结点度序列为(11112233)的不同构的树有多少棵，请分别画出这些树。
129..请描述一切具有两个叶结点的树的特征。并对你的论点给予证明。
130.名词解释
1．G的生成树：
2．弦：
3．生成树的补：
131. 设G是有n个结点m条边的连通图, 问要删去多少条边，才得到一棵生成树? 132. 分别画出K6的所有非同构的生成树。
133. 给定无向图如下，请画出它的所有非同构的生成树。
134. 什么叫做赋权图的最小生成树？
135. 用Kruskal 算法画下面赋权图的最小生成树。
136. 给定图G 如下图所示,用Kruskal 算法,求G 的一棵最小生成树
v 1
v 5 v 4
v 2 v 3 v 8 v 6
v 7
1 2
2 3 1 7
7
2
4
8 6
6
5 3 4 4 3
离散数学第八章一些特殊的图知识点总结
图论部分 第八章、一些特殊的图 8.1 二部图 二部图：定义设无向图G=
设M为G中一个匹配 v i与v j被M匹配: (v i,v j)∈M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 定理(Hall定理) 设二部图G=
Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为t 条件. 满足t 条件的二部图一定满足相异性条件. 8.2 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.
哈工大年集合论与图论试卷
-- 本试卷满分90分 (计算机科学与技术学院0９级各专业) 一、填空（本题满分１0分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么？(A B ?) ２.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?（22-n ) ３．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则 最大元是什么? ( 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =） ５．设∑为一个有限字母表,∑上所有字(包括空字）之集记为*∑，则*∑是 否是可数集? （ 是 ) ６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ） 8. 如图所示图G ,回答下列问题： (１）图G 是否是偶图? ( 不是 ) (2）图G 是否是欧拉图? ( 不是 ） (3)图G 的色数为多少？ ( 4 ) 二、简答下列各题（本题满分40分） 1．设D C B A ,,,为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=??。 解:（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?，有,x A B y C D ∈∈，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?，从而()()A C B D ???()()A B C D ?。
图论与抽象代数复习
2013-2014二学期图论与抽象代数复习 第一部分 1.第三篇总复习题1，2，3题 2.第四篇总复习题1，4，6题 3.习题9 9.1题 4. *运算如下表所示，哪个能使({a,b},*)成为单元半群？（） 5. Q 是有理集，（Q，*）（其中*为普通乘法）不能构成（）。 A．群B．单元半群C．半群D．交换半群 6.设Z 是整数集，＋，·分别是普通加法和乘法，则（Z，＋，·）是（）。 A．域B．整环和域C．整环D．含零因子环 7. 在代数系统中，整环和域的关系为（）。 A．整环一定是域B．域不一定是整环 C．域一定是整环D．域一定不是整环 8. 设D =< V,E >为有向图，V = {a, b, c, d, e, f }，E = {( a,b),(b,c),(a, d), ( d, e),(f, e)}是（）。A．强连通图B．单向连通图C．弱连通图D．不连通图 9. 在有n 个结点的连通图中，其边数（）。 A．最多有n?1 条B．至少有n?1 条 C．最多有n 条D．至少有n 条 10设G = (n,m)为无向简单图，可构成邻接矩阵的数目为（）。 A．n! B．m! C．D． 11. 欧拉回路是（）。 A．通路B．简单回路 C．既是基本回路也是简单回路D．既非基本回路也非简单回路 12. 哈密尔顿回路是（）。 A．通路B．简单回路 C．既是基本回路也是简单回路D．既非基本回路也非简单回路 13. 下面哪一种图不一定是树?（） A．无回路的连通图B．有n 个结点n ?1条边的连通图 C．每对结点间都有通路的图D．连通但删去一条边则不连通的图 下述偏序集（见下图）中能构成格的是（） 下述偏序集中哪一个不构成格？（）
集合论与图论习题册
集合论与图论习题册 软件基础教研室 刘峰 2015.02
第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的，哪些为假 a)对每个集A ，A φ∈； b)对每个集A ，A φ?； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ?； f)对每个集A ，{}A A ?； g)对每个集A ，2A A ∈； h)对每个集A ，2A A ?； i)对每个集A ，{}2A A ?； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈； l)对每个集A ，2A φ?； m)对每个集A ，{}A A =； n) {}φφ=； o){}φ中没有任何元素； p)若A B ?，则22A B ? q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈?∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。 答案： 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ，试证：12n A A A === 。 4.设{,{}}S φφ=，试求2S ？ 5.设S 恰有n 个元素，证明2S 有2n 个元素。
16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合，试证A B A B φ=?=?。 9.设A ，B ，C 为集合，证明：\()(\)\A B C A B C = 。 10.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 11.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 12.设A ，B ，C 都是集合，若A B A C = 且A B B C = ，试证B=C 。 15.下列命题是否成立？说明理由（举例）。 (1)(\)\(\)A B C A B C = ；(2)(\)()\A B C A B C = ； (3)\()()\A B C A B B = 。（答案：都不正确）
集合论与图论
《集合论与图论》课程示范性教学设计 1 本课程教学方法 （一）教学方法 在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想： （1 ）启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。 （2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。 （3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性，也使学生增强了学习的目的性。 （4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。 （5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。 （5 ）适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。事实上，在每年教此课时，提一些问题确实有学生在思考。 （6 ）注意每个学科（内部）的美。如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。 （二）关于素质教育、培养创新精神的人才的思考 素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。在这里讨论这个题目不太合适，因为题太大。其实，在（五）中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 1 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联
《集合论与图论》课堂练习2
《集合论与图论》课堂练习3 （2013年12月18日 13:20-15:00 复旦大学计算机学院2012级） 学号姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否”）（40分，每题8分，是非判断4分，证明或反例4分） 1 存在7个结点的自补图。 （否） /*西安交通大学1999*/ 自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。 n≥的连通图。则G没有割点当且仅当G的剖分也没有割点。 2 设G是顶点数3 （真） 如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。 如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。 3 若G是简单连通图，边数为e，结点数为n。若e≥n，则G至少有3棵生成树。 （是） /*复旦大学1998*/ /*只需证明e=n时，命题成立*/ 若e=n-1，因为G是连通的，所以为一棵树；再添加一边时，因为G是简单图，所以图中必存在一个长度大于等于3的回路，则在这个回路上任意删除一条边就得到一棵树。 4 一个有向图D中仅有一个顶点的入度为0，其余顶点的入度均为1，则D是有根树。 （否） 一个自环和孤立点 /*北京大学1991*/ 5 设C是简单连通图G的回路，若删去C中任一边后所得到的路C’为G中的最长路，则C是图G的哈密顿回路。 （是） /*复旦大学1999*/ /*反证法证明*/ 令C的长度为m。若C不是哈密顿回路，则圈外必存在一点u，它与圈上一点v邻接（因为G是连通图）。圈上与v关联的一边为e，则C-e的长度为m-1；而C-e+uv的长度为m；得C-e不是最长路。矛盾。
集合论与图论答案 第四章习题
第四章 无穷集合及其基数习题 136P 1.设A 为由序列 12,,,,n a a a 的所有项组成的集合，则是否市可数的？为什么？ 解：因为序列是可以重复的，故 若A 是由有限个数组成的集合，则A 是有限的集合； 若A 是由无限个数组成的集合，则A 是可数的。 故本题A 是至多可数的。 2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。 证：在每个开区间中取一个有理数，则这些有理数构成的集合是整个有理数集合Q 的子集，因此是至多可数的。 3.证明：单调函数的不连续点的集合至多可数。 证：设A 是所有不连续点的集合，f 是一个单调函数，则00,x A x ?∈对应着一个区间0((0),(0))f x f x -+，于是由上题便得到证明。 4.任一可数集A 的所有有限子集构成的集族是可数集合。 证：设1212{,,,,},{,,,},n i i ik A a a a B a a a ==则B A ?且B k =<∞。 令{,}B B A B B =?<∞， 设:{0,1}A ?→，则?是Ａ的子集的特征函数。 ,()B B ??∈B =｛0，1的有穷序列｝ ，即i a A ?∈， 若i a B ∈，则对应1；若i a B ?则对应0。于是 ,()B B ??∈B 就对应着一个由0，1组成的有限序列0，1，1，0，…，0，1。此序列对应着一个二进制小数，而此小数是有理数。于是，可数集A 的所有有限子集B 对应着有理数的一个子集。 又121212,,,,B B B B B B ?∈B ≠对应的小数也不同，故?是单射。而可数集Ａ的所有有限子集B 是无穷的，故B 是可数的。
集合论与图论(下)教学大纲
集合论与图论（下）教学大纲 《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生提出问题、分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 课程概述 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。 本课程的目标是通过理论学习，使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系。引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。 本课程主要包含二部分内容：集合论与图论。集合论是整个数学的基础，也是计算机科学的基础，计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的有关术语来描述和论证，而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。 计算学科以抽象、理论、设计为其学科形态，以数学方法和系统方法为其学科方法，本课程的核心目标就是在抽象和理论的基础上提供数学方法，因此，本课程是整个专业的基础课程，是计算机专业最重要的课程之一。 《集合论与图论》（上）主要讲述集合论部分，《集合论与图论》（下）主要讲述图论部分。 授课目标 课程具体目标如下： 课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；
哈工大集合论与图论第六章作业题答案
第六章图的基本概念 P习题 206 1．画出具有4个顶点的所有无向图(同构的只算一个)。 11个 2．画出具有3个顶点的所有有向图(同构的只算一个)。 16个 3．画出具有4个、6个、8个顶点的三次图。 略 4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。 把实际问题转化为图论问题，然后用握手定理的推论。 P习题 209 1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G 中是否有圈？ 若u与v间有两条不同的通道，G中无圈 若u与v间有两条不同的迹，G中有圈 2．证明：一个连通的(p，q)图中q≥p-1。 数学归纳法 3．设G是一个（p，q）图，且2/)2 >p - q，则G是连通的。 p )( 1 (- 6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。证明：把实际问题转化为图论问题，就和下面的题一样了。 8．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。 这两个题和这个题一样的证明方法。
P习题 216 1．证明：若图G不是连通图，则G c 是连通图。 2．证明：每一个自补图有4n或4n+1个顶点。 P习题 228 1.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。 下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。
2．试求Kp中不同的哈密顿圈的个数。 (p-1)!/2 4．完全偶图Km，n为哈密顿图的充分必要条件是什么？ 10．证明具有奇数顶点的偶图不是哈密顿图。
《集合论与图论》课程教学大纲
《集合论与图论》课程教学大纲 一、课程基本信息 课程编号：CS31111 课程名称：集合论与图论 英文名称：SET THEORY AND GRAPH THEORY 课程学时：64；讲课学时： 48；实验学时：上机学时：习题学时：16; 课程学分：4.0 开课单位：计算机科学与技术学院 授课对象：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）、软件工程大类专业 开课学期： 1春 先修课程：工科数学分析、线性代数 二、课程目标 《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课程。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。 要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。 本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。 课程具体目标如下： 课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型； 课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想； 课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。 课程目标4：能够利用本课所学知识分析工程实际问题或针对某些应用背景探讨所学知识的局
集合论与图论2.2
2.3 关系的运算 *关系的运算有七种,分别列出如下: 定义7.6: 设R是二元关系. (1)R中所有有序对的第一个元素构成的集合称为R的定 义域, 记作domR. domR={x | ?y(
G F={<2,3>}. *左复合: F G={
《集合论与图论》课堂练习2 - 复旦大学精品课程
《集合论与图论》课堂练习2 （2012年12月5日 13:30-15:10 复旦大学计算机学院2011级） 学号姓名 注意：有关计数的答案可用P(n,k),C(n,r),n k,k!,及数字等表示 一、填空题（55分） 1．s（s≥1）个元素分成t个组，那么必存在一个组至少含有个元素。2．20000到70000间的偶数中由不同数字组成的5位数的个数共 有。3．5对夫妻出席一宴会，围一圆桌坐下。有种不同的方案。若要求夫妻相邻，有种不同的方案。 4．从1到300间任取3个不同的数，使得这3个数的和正好被3除尽，有种方案。 5．(x+y+z)10有_ __项。 6．(2x+y+z)8的展开式中的x3yz4系数是。7．排列字母ILLINOIS可以得到个不同的字符串； 如果要求某个I排在某个L之前，可以得到个不同的字符串。 8. 利用二项式定理展开(s-r)4。(s-r)4= 。 9．整除510510的正奇数有个。 二、综合题（45分，5?9分=45分） 1．证明：在任意给出的n+1（n≥2）个正整数中必有两个数，它们的差能被n整除。
证明： 2．矩形被分为3?7=21个正方形，每个正方形用红色或黑色着色。证明存在非简单子矩形（非1?k或k?1），4个角的正方形颜色相同。 解：
3．证明杨辉三角形定理: 对于任意的1≤ k≤ n，则C(n+1, k)=C(n, k)+C(n, k-1)。 4．某学生在37天里共做了60道数学题。已知他每天至少做1道题。求证：必存在连续的若干天，在这些天里该学生恰做了13道数学题。
5．设A含有n个元素的集合{x 1, x 2 , ……, x n }，证明|P(A)|=2n。
图论习题答案1
图论习题课作业1，3，6，8，10 By jgy
?作业1：第一章：1,2,4,12,20,29,35 ?作业3：第二章：14,28,30第三章：1,5,7,8?作业6：第五章：18,33 ?作业8：第六章：6,12,17 ?作业10：第七章10 第八章5,6,8
作业1 |E(G)|,2|E(G)|2G υυ?? ≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。
?1.20证明每顶皆二次的连通图是圈 ?证明：（思路）易证每顶皆二次的连通图中有圈。设图中最大圈为H，假设除H外还有其他顶点集U，任取u k，因为连通，u k 与H中任意顶均有一条道路，存在H中一顶h j与u k相邻，则h j为三次。 ?1.29 证明二分图的子图是二分图 ?方法一： ?定理1.2 图G是二分图当且仅当G中无奇圈 ?反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有 奇圈，则G中有奇圈，这与G是二分图矛盾。 ?方法二： ?（思路）定义：V(G) = X U Y, X n Y=空, 且X中任二顶不相邻，且Y中任二 顶不相邻。
?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,2 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= vi , 1≤ i≤ k}, ?v’’ = {v|v= vi , k< I ≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为
图论教案
第六章图论(Graph Theory) ◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路、最大流的概念、计算与应用；了解中国邮路问题与解法。 ◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。 ◎本章重点：最小树、最短路、最大流的计算与应用 ◎本章难点：最短路的应用、最大流的计算 引例：哥尼斯堡七桥问题 18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。 有关图论研究的热点问题。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。这就是哥尼斯堡七桥问题。L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。 当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Preg el的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。 Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成. 欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。 接下来，欧拉运用网络中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！
哈工大2010年集合论与图论试卷
哈工大 2010 年 春季学期 集合论与图论 试题 题号 一 二 三 四 总分 分数 学号 姓名 本试卷满分90分 （计算机科学与技术学院09级各专业） 一、填空(本题满分10分，每空各1分) 1．设B A ,为集合，则A B B A = )\(成立的充分必要条件是什么？（A B ?） 2．设}2,1{},,,2,1{==Y n X ，则从X 到Y 的满射的个数为多少？（22-n ） 3．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则最大元是什么？ （ 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系，使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。（{(,),(,),(,),(,)}R a a b c c b a c =） 5．设∑为一个有限字母表，∑上所有字（包括空字）之集记为*∑，则*∑是 否是可数集？ （ 是 ） 6．含5个顶点、3条边的不同构的无向图个数为多少？ （ 4 ） 7．若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ) 8. 如图所示图G ，回答下列问题： （1）图G 是否是偶图？ （ 不是 ） （2）图G 是否是欧拉图？ （ 不是 ） （3）图G 的色数为多少？ （ 4 ） 二、简答下列各题（本题满分40分） 1.设D C B A ,,,为任意集合，判断下列等式是否成立？若成立给出证明，若不 成立举出反例。（6分） （1）)()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=?? 。 解：（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ? ，有,x A B y C D ∈∈ ，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?，因此 (, )()()x y A C B D ∈?? ，从而()()A B C D ? ?()()A C B D ?? 。 反之，(,)x y ?∈()()A C B D ?? ，有,,,x A x B y C y D ∈∈∈∈。即
《集合论与图论》课堂练习1
《集合论与图论》课堂练习1 学号姓名成绩 一、填空题（30分，每格2分） 1．设A为一个集合，若A为有限集。 若，则称A为可列集。2．已知集合A和B，且|A|=n，|B|=m，由A到B有个不同的 关系，有个不同的函数。若n =5, 则A上有个全序关系。若n =m=3, 则从A到B可产生个不同的双射。 3．集合A的递归（归纳）定义由三部分组成： （1）_ _ _; （2）_ _ ; （3）_ _ _。 4．设A、B为集合，则A?B=B的充要条件是：； A⊕B=B的充要条件是_____。 5．函数f:N?N→N，f((x, y))=x2+y2。f-1({0})=。 6. 函数f: A→ B可逆的充要条件是。 7. A, B是集合，P(A), P(B)为其幂集，且A?B=?，则P(A)?P(B) =。 8. A, B是集合，?0=|B|<|A|=?，则|A-B|= 。 二、是非判断题（24分，每题6分，其中判断3分，论述3分） 1．设A, B, C, D是任意集合；f是从A到B的双射，g是从C到D的双射。h: A?C→B?D，其中对于任意的(a, c)∈A?C, h((a, c))=(f(a), g(c))成立。则h是双射。（）
2．设R是A上的二元关系，则t(s(R))=s(t(R))。 （） 3．设A, B是集合，若存在A到B的满射，则|B|≤|A|。 （） 4．设A是集合，R是A的幂集P(A)上的二元关系，对所有的S, T∈P(A)，(S, T)∈R。R是偏序关系当且仅当|S|≤|T|。
（） 三、综合题（46分） 1．设有双射f: A B，试构造从P(A)到P(B)的一个双射，并证明之。（15分，给出双射5分，证明10分） 2．某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，4，…)，称为可列集。 有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老
复旦大学《集合论与图论》课堂练习1(2017年11月6日)(参考答案)
《集合论与图论》课堂练习1 （2017年11月6日 13:30-15:10 复旦大学计算机学院） 学号姓名成绩 一、填空题（30分，每格2分） 1．设A为一个集合，若A为空集或与集合{0,1,2,…,n-1}的基数相同，则A为有限集。若存在从N到A的双射，则称A为可列集。 2．设R是A上的二元关系，定义R的自反（对称，传递）闭包记为R’，满足下列三个条件： （1）R’是自反的（对称的，传递的）； （2）R’?R； （3）对任一自反（对称，传递关系）R”，R?R”，则R’?R”。 3．集合A的递归（归纳）定义由三部分组成： （1）_基础: 某些元素属于我们正在定义的集合A中,说明集合A是非空的 _ _; （2）_递归（归纳）: 使用当前集合A中的现有元素来产生含在此集合中的更多元素, 即建立产生集合A中新元素的一种方法 _ ; （3）_闭合: 只有在集合A中的元素是通过有限次应用(1)和(2)得到的 _ _。 4．设A和B是两个任意集合，f 是从A到B的二元关系。若f 具有性质：（1）f 的定义域Dom f=A； （2）如果(a, b)，(a, b’)∈f，则b=b’。 则称关系f 是从A到B的函数，记为f:A?→B。 5．函数f:R?R→ R?R，f((x, y))=(x+y, x-y)。f的逆函数f-1是f-1((x, y))=((x+y)/2, (x-y)/2) 。 6. 设集合A={ x | (x∈R) and (x3-2x2-x+2=0) },则集合A的幂集P(A)= {?, {1},{-1}, {2}, {-1, 1}, {-1, 2}, {1. 2}, {-1, 1, 2} } 。
第六章 图论
第六章图论 §8.1 图论发展史 第一阶段：瑞士数学家欧拉（E. Euler）在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所谓“七桥难题”是指：18世纪的哥尼斯堡城中流过一条河，河上有七座桥连接着河的两岸和河中的两个小岛，如图8-1所示：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点；没有人想出这种走法，又无法说明走法不存在。欧拉将这个问题归结为如图8-2 所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。 图8-1 图8-2 第二阶段：1847年，数学家基尔霍夫（Kirchhoff）运用图论解决了电路理论中的求解联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，从此图论又有了新的发展。 第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。 第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。