当前位置：文档库 › 图论第四次作业答案

图论第四次作业答案

4.19

n*n 方阵中两两不同行不同列的n 个氧元素的集合成为一个对角线，对角线的权指它的n 个元素之和，试求下列矩阵A 的最小权的对角线：

458

10117

65748512966

61310745798?? ? ? ? ? ? ??? 解答：

问题转化为求K 5,5的最佳匹配，用KM 算法：

其K5,5的权矩阵是45810117

65748512966

61310745798-----?? ?----- ? ?----- ?----- ? ?-----?

?，结果是445105810117657812966613745798?? ? ? ? ? ? ???，权值为30，或5810117

674812966

61310457845579?? ? ? ? ? ? ???

，权值也是30.

5.1

求n 顶轮的边色数。

解答：1）在n 顶轮G 中，Δ(G)=n-1 χ’(G)≥n-1

2）现可构造一个n-1的边正常着色如下：

用n-1种颜色对与n 顶轮中心顶点关联的边着色

n 顶轮的不与V 0关联的边V k V k+1着色为V k+2V 0的颜色一致,V n-1V 1着色与V 2V 0相同

5.2

给出二分图正常Δ边着色的算法

解答：先构造出Δ次正则二分图，然后逐次求其完备匹配。

PS ：如果直接求其最大匹配并染色，可能得不到正常Δ边着色.见下图：

第一次的匹配是红色线条的话，就需要三种颜色，而Δ(G)=2.

5.8

有7个老师x 1，x 2…x 7，12个班y 1，y 2….y 12，矩阵A 的a ij 号元素是教师x i 对y j 班一周上课的节数，

32331

36050552424?? ? ? ? ???

计算一天应分几节课？若每天8节课，需要几间教室？解答：Δ(G)=16, ε(G)=48 如果一周上课5天，每天应上()G 5????

???= 4节课. 若每天8节课，一周为40节课，需要教室()40G ε??????

=2间. 5.11

求证：χ’(G *K 2) =Δ(G*K 2) .

证明：根据P 110中图的积定义可知在H=G*K 2中的顶点(v i 1,v j 2)的顶点的度为2*d(v i 1) +1 所以Δ(H)=2*Δ(G )+1，所以题目等价于证明χ’(G *K 2) =2*Δ(G )+1

根据Vizing 定理，χ’(G) ∈ {Δ(G),Δ(G)+1}

假设χ’(G)=Δ(G)，构造一个2*Δ(G )+1边正常着色。首先对于由顶点(v i 1,v 02)构成的子图H 1可以Δ(G)边正常着色，对于由顶点(v i 1,v 12)构成的子图H 2也可以Δ(G)边正常着色，然后将H 1和H 2之间的边用剩下的Δ(G)+1着色。

假设χ’(G)=Δ(G)+1，和上一情况相似，也构造一个2*Δ(G )+1边正常着色。

5.12

试叙述一个单图的Δ+1正常顶着色算法。

解答：依次从度最高的顶点开始染色就可以了.

5.13若δ是单图G 顶的最小次数，证明δ>1则存在δ-1边着色，使与每顶关联的边中有δ-1种颜色.

方法一：

证明：设图G 的最小度数为n ，我们要将边着色。

首先我们要利用如下的一个定理：

如果图H 的最大度数为n ，那么H 可(n+1)边着色，并且使得有公共顶点的边拥有不同的颜色。

为此，我们先构造图H 。图H 由图G 演化而来，目的是要将G 中顶点的度数统统变为n 。为此，需要添加一些新的顶点。我们将会看到，新的顶点的度数统统为1。具体步骤如下：

（1）在G中任选一个度数大于n的顶点v，比如：v的度数是n+x。然后，构造x个新的顶点。再从与v相连的边中任选x条，将它们分别改为与这x个新的顶点相连。这一步过后，v的度数就变成了n，而新加的顶点度数都为1。

（2）重复步骤1。也就是说，看看当前图中还有没有度数大于n的顶点，如果有，则按照步骤1的方式去处理。直到没有了。

此时，我们观察一下这个新的图，也就是图H。先观察一下图H：

（1）图H中，原图G中的顶点的度数统统变为n，新加的顶点的度数全都是1。

（2）图H中的边与图G中的边一一对应，也就是说，给出任意一条图H中的边，我们都能把它还原成图G中的边。

下面，对图H应用那个定理。将图H进行(n+1)边着色，根据定理，每种颜色的边都不共点，也就是说，在每个顶点处，每种颜色的边只有1条或者0条。所以，对于原图G中的点，它们的度数为n，也就是说，它们与n条不同颜色的边相连，独缺1种颜色。

原题是要给出一个(n-1)边着色，下面，我们将保留前(n-1)种颜色，把最后2种颜色去掉。在图H中，我们把后2种颜色的边提取出来，记为E。看看由这些边组成的H的子图有什么性质。可以得出：在H中，每个顶点至多与2条E中的边相连。

对于H中一个原来G中的顶点，如果它不与E中的边相连，或者仅与1条E中的边相连，那么，即使去掉后2种颜色，它也已经有了(n-1)种不同的颜色。所以，关键是处理与E中2条边相连的那些顶点，把这些顶点记为U。

回想我们刚才的(n+1)边着色，每个G中的顶点都缺1种颜色。由于U中的顶点同时拥有了最后2种颜色，那么它们一定缺了前面的某一种颜色。当然，每个顶点缺的不一样。我们所要做的，就是将E中的边更改颜色，使得U中的每个点都有其中1条边改成了它缺的那种颜色。

再仔细看看H中由E中的边组成的子图，由于每个顶点至多与2条E中的边相连，所以这个子图的每一个连通分支，（1）或者是一条简单的路径；（2）或者是一个简单的回路。（上面这句话很显然，但需要想一下。）无论哪种情况，都可以给E中的边添加方向，使得每一个U中的点都有一个入边和一个出边。我们把每个U中点的入边改为该点所缺的颜色即可。

PS：此题反证法亦可证明。

集合论与图论试题A

本试卷满分90分（06级计算机、信息安全专业、实验学院）一、判断对错（本题满分10分，每小题各1分）（正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。（×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。（√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。（×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。（×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。（√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。（×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。（√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。（×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）

二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7．设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应，这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。

电大离散数学作业答案(图论部分)

离散数学作业5 离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2018年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f}． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点度数之和等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且等于出度． 5．设G=是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1，则在G 中存在一条汉密尔顿路． 6．若图G=中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为W(G-V1)≤∣V 1∣． 7．设完全图K n 有n 个结点(n ≥2)，m 条边，当n 为奇数时，K n 中存在欧拉回路． 8．结点数v 与边数e 满足e=v-1关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i =5．二、判断说明题（判断下列各题，并说明理由．） 1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回

北大集合论与图论往年考题.pdf

一、用真值表证明德*摩根律（证明其中一条即可）。二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题：一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。三、计算出右图中v1到v4长度为4的通路数（要写出计算过程的主要步骤），并写出一个最小支配集、一个最大团、一个最小边覆盖、一个最大匹配。四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j,<2,3>,<3,2>, <3,4>}. (1) 给出R的矩阵表示, 画出R的关系图; (2) 判断R具有哪些关系性质(自反,反自反,对称,反对称,传递); (3) 求出R的自反闭包r(R), 对称闭包s(R), 传递闭包t(R). (用关系图表示) 三、设X,Y,Z是任意集合, 构造下列集合对之间的双射, 并给出是双射的证明. (1) Z(X?Y)与(Z X)Y ; (2) P(X?Y) 与P(X)?P(Y). (假设X?Y=?) 四、已知对每个自然数n, 都存在唯一后继n+=n?{n}. 证明: 对于每个非零自然数n, 都存在唯一前驱n-, 满足n=(n-)+. 五、设f: A→B是单射, g: B→A是单射, 证明: 存在集合C,D,E,F, 使得A=C?D, C?D=?, B=E?F, E?F=?, 并且f(C)=E, g(F)=D.

图论及应用第一章完整作业

习题 1 1. 证明在n 阶连通图中（1）至少有n -1条边。（2）如果边数大于n -1，则至少有一条闭通道。（3）如恰有n -1条边，则至少有一个奇度点。证明 (1) 若对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,矛盾！若G 中有1度顶点，对顶点数n 作数学归纳。当n=2时，G 显然至少有一条边，结论成立。设当n=k 时，结论成立，当n=k+1时，设d(v)=1，则G-v 是k 阶连通图，因此至少有k-1条边，所以G 至少有k 条边。 (2) 考虑v 1→v 2→?→v n 的途径，若该途径是一条路，则长为n-1,但图G 的边数大于n-1,因此存在v i ,v j ,使得v i adgv j ,这样，v i →v i+1→?→v j 并上v i v j 构成一条闭通道；若该途径是一条非路，易知，图G 有闭通道。 (3) 若不然，对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,与已知矛盾！ 2. 设G 是n 阶完全图，试问（1）有多少条闭通道？（2）包含G 中某边e 的闭通道有多少？（3）任意两点间有多少条路？答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n -2)…1. 3. 证明图1-27中的两图不同构：证明容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图1-28中的两图是同构的证明将图1-28的两图顶点标号为如下的(a)与(b)图图 1-27 图1-28

离散数学第八章一些特殊的图知识点总结

图论部分第八章、一些特殊的图 8.1 二部图二部图：定义设无向图G=, 若能将V 划分成V1 和V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为, 称V1和V2为互补顶点子集. 完全二部图：又若G是简单图, 且V1中每个顶点都与V2中每个顶点相邻, 则称G为完全二部图, 记为K r,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图. 匹配：设G=, 匹配(边独立集): 任2条边均不相邻的边子集极大匹配: 添加任一条边后都不再是匹配的匹配最大匹配: 边数最多的匹配匹配数: 最大匹配中的边数, 记为β1 例下述3个图的匹配数依次为3, 3, 4.

设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=中，|V1|≤|V2|. G中存在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配. 定理设二部图G=中, 如果存在t≥1, 使得V1中每个顶点至少关联t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配.

Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为t 条件. 满足t 条件的二部图一定满足相异性条件. 8.2 欧拉图欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明：上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.

集合论与图论试卷2

哈工大 2007 年秋季学期本试卷满分90分（06级计算机、信息安全专业、实验学院）一、判断对错（本题满分10分，每小题各1分）（正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。（×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。（√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。（×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。（×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。（√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。（×） 8．设)(ij a A =是p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。（√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。（×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）

集合论与图论

集合论与图论习题册软件基础教研室刘峰 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 = 。（答案：都不正确）

哈工大年集合论与图论试卷

-- 本试卷满分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 ?。

图论1-3藏习题解答

学号：0441 姓名：张倩习题1 4．证明图1-28中的两图是同构的证明：将图1-28的两图顶点标号为如下的(a)与(b)图作映射f : f(v i )u i (1 i 10) 容易证明，对v i v j E((a)),有f(v i v j )u i u j E((b)) (1 i 10, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： (a) v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)

m=2：m=3：

m=4：m=5：m=6：

因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列；（6,6,5,4,3,3,1）是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---L L 是图序列（5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G 包含圈。证明只就连通图证明即可。设V(G)=｛v1,v2,…,vn ｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于 2，因此，对vin ，存在点vik 与之邻接，则vik vinvik 构成一个圈。 17.证明：若G 不连通，则G 连通。证明对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 18.证明：若()e E G ∈,则()()()1G G e G ωωω≤-≤+. 证明：若e 为G 的割边，则()()1G e G ωω-=+，若e 为G 的非割边，则 ()()G e G ωω-=，所以，若()e E G ∈，则有()()()1G G e G ωωω≤-≤+. 习题2 1.证明：每棵恰有两个1度顶点的树均是路。证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，

集合论与图论SG2017-期中试题-答案(1)

一、（20分）对于任意集合A和B，（1）证明：P(A)?P(B) = P(A?B)；（14分）对任意的x∈P(A)?P(B)，有x∈P(A)且x∈P(B)。即x?A并且x?B，则x?A?B。所以x∈P(A?B)。故P(A)?P(B)?P(A?B)。（7分）对任意的x∈P(A?B)，有x?A?B，即x?A并且x?B，所以x∈P(A)且x∈P(B)。因此P(A?B)?P(A)?P(B)。（7分）综上所述，P(A)?P(B)=P(A?B) （2）举例说明P(A)?P(B) ≠ P(A?B). （6分） A={1}, B={2}, A?B={1, 2}; P(A)={?, {1}}, P(B)={?, {2}}, P(A)?P(B)= {?, {1}, {2}}, P(A?B)= {?, {1}, {2}, {1, 2}}; 所以P(A)?P(B)≠P(A?B) 二、（20分）设R, S是A上的等价关系且R?S=S?R，证明： R?S是A上的等价关系. 自反性和对称性容易证明，略。（5分）传递性证明：对任意a, b, c∈A，如果(a, b)∈R?S, (b, c)∈R?S，要证明(a, c)∈R?S。因为R?S=S?R，则有(b, c)∈S?R，即存在e, f∈A，使(a, e)∈R，(e, b)∈S，(b, f)∈S，(f, c)∈R。因为S是传递的，(e, b)∈S，(b, f)∈S，所以(e, f)∈S；因为(a, e)∈R，所以(a, f)∈R?S；R?S是对称的，则(f, a)∈R?S；因为R是对称的，(f, c)∈R，则(c, f)∈R。因为(f, a)∈R?S，则存在g∈A，使得(f, g)∈R，(g, a)∈S；因为R是传递的，

电子科技大学-图论第二次作业

习题四： 3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下： (1)一个有Euler 闭迹和Hamilton圈的图； (2)一个有Euler闭迹但没有Hamilton圈的图； (3) 一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4.设n阶无向简单图G有m条边，证明:若,则是图。证明: G是H图。若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G 度弱于某个.于是有：

2,1()()(2)(1)(1)2 11 1(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ??≤= +---+-??-??=+------- ? ?? -??≤+ ??? 这与条件矛盾！所以G 是H 图。 8.证明：若G 有个奇点，则存在条边不重的迹 ,使得 . 证明：不失一般性，只就G 是连通图进行证明。设G=(n, m)是连通图。令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k): 12()() () ()k E G E Q E Q E Q = 10.证明：若：（1）不是二连通图，或者（2）是具有二分类的偶图，这里 , 则是非Hamilton 图。证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的相关定理：若是Hamilton 图，则对于的任意非空顶点集，有： ,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton 图 (2)因为是具有二分类的偶图，又因为，在这里假设 ,则有,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton 图。 11.证明：若有Hamilton 路，则对于V 的每个真子集S ，有 .

离散数学作业7答案(数理逻辑部分)

离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）．一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R ． 3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为?x ( P ( x) ∧Q ( x))． 5．设个体域D＝{a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b))． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ．三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式．解：

图论与抽象代数复习

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．连通但删去一条边则不连通的图下述偏序集（见下图）中能构成格的是（）下述偏序集中哪一个不构成格？（）

集合论与图论

《集合论与图论》课程示范性教学设计 1 本课程教学方法（一）教学方法在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想：（1 ）启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。（2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。（3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性，也使学生增强了学习的目的性。（4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。（5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。（5 ）适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。事实上，在每年教此课时，提一些问题确实有学生在思考。（6 ）注意每个学科（内部）的美。如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。（二）关于素质教育、培养创新精神的人才的思考素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。在这里讨论这个题目不太合适，因为题太大。其实，在（五）中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 1 ）教会学生如何进行逻辑推理，如何进行正确地思维，如何在纷繁的事物中抓住主要的联

图论王树禾答案

图论第一次作业 By byh

|E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题略 1.2 证明其中是单图证明：（思路）根据单图无环无重边的特点，所以最大的情形为任意两个顶点间有一条边相连，即极端情况为。

?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边：

1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G

1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4

?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为

集合论图论期中考试试题及答案

08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={|x,y∈A∧x≡y(mod 5)}.证明:R为A上的等价关系. 并求商集A/R. (15分) 5.给出下列偏序集的哈斯图,并指出A的最大元,最小元,极大元和极小元. A={a,b,c,d,e},?A= I A∪{,, ,,,,} (15分) 6.设g:A→B, f:B→C.已知g f是单射且g是满射,证明:f 是单射. (10分) 7.设S={0,1}A, 其中A={a1,a2,…,a n}.证明:P(A)与S等势. (10分) 8.证明:任何一组人中都存在两个人,他们在组内认识的人数恰好相等(假设,若a认识b,则a与b互相认识). (10分)

期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ?, ∈R∪R-1 ?∈R∨∈R-1 ?∈R-1∨∈R ?∈R-1∪R ?∈R∪R-1

图论习题参考答案

二、应用题题0：（1996年全国数学联赛）有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。注：[n /2]表示不超过n /2的最大整数。证明将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有（1）对每个顶点x ， )(x N G ≥[n /2]；（2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有两个顶点相邻。需要证明G 中有三个顶点两两相邻。反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , , , } 试作图G 和图D ，写出各结点的度数，回答图G 、图D 是简单图还是多重图？解： a d a d b c b c 图G 图D 例2图