第17讲欧拉图北京大学计算机系离散数学讲义版

2020/10/7
W1 W2 W3 W4 W5 W11 W12 W13 W14 W15 W6 W7 W8 W9 W10
20
S10
方案的最优性
满足目标要求： 任取 10 个工作站. 如果恰好为 W1,W2,…,W10，Wi 访问 Si，i=1,…10, 满足要求; 如果 W1-W10 中只选中 k 个工作 站，不妨设为 W1--Wk, 剩下的 10-k 个选自 W11-W15. 那 么 Wi 访问 Si，i=1,…,k. 还剩下 10-k 个服务器空闲，恰好 分配给 10-k 个工作站.
保证这组工作站可以同时访问不同的服务器.
问题：达到这个目标需要的最少缆线数目 N 是多少？
方案 1：每个工作站都连到每个服务器，需要
1015=150
2020/10/7
根缆线，N 150.
例11的解决方案
方案 2 将工作站标记为 W1,W2, …, W15, 服务器标记为 S1,S2, …, S10. 对于 k=1,2,…,10，我们连接 Wk 到 Sk, 剩下 5 个工作站的每一个都连接到 10 个服务器 总共 60 条直接连线.
2020/10/7
简单Ramsey定理的推广
(1) R(p,q)的集合表述：
Kn 的顶点集 V
集合 S
Kn 的边集 E
S 的 2 元子集的集合 T
用 2 色涂色 Kn 的边 将 T 划分成 E1,E2
存在蓝色完全 p 边形 存在 S 的 p 子集，其所有 2 元子集E1
存在红色完全 q 边形 存在 S 的 q 子集，其所有 2 元子集E2
对于 K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形.
R(3,4)=9.
2020/10/7

2019/1/16 计算机学院 8/128
定理16.1(移项法则)设<R,+, *>是一个环， θ是加法幺元，对任意a，b，c R有: a+b=c a+b-c=θ
2019/1/16
计算机学院
9/128
定理16.2设<R,+, *>是一个环，θ是加法幺 元，对任意a，b，c R有: ① a*θ=θ*a=θ(加法幺元是乘法零元) ② (-a)*b=a*(-b)=-(a*b) ③ (-a) *(-b)=a*b ④ (b-c) *a=b*a-c*a ⑤ a* (b-c）=a*b-a*c
2019/1/16 计算机学院 7/128
例 16.2 设 Zk 表示整数集 Z 上的模 k 剩余类集 合，即: Zk={[0]，[1]，[2]，…，[k-1]} <Zk ，>是群（剩余类加群）， <Zk ，>是半群（剩余类乘半群）， ∵ 对 [i]，[j]，[k] Zk 有[i]（[j][k]）=[i(j+k)]=[ij+ik] =[ij][ik] =([i][j])([i][k]） ∴ <Zk ，，>是环，称为（模k）剩余类环。 特别， k=2时，称为布尔环。
2019/1/16 计算机学院 6/128
例 16.2 设 Zk 表示整数集 Z 上的模 k 剩余类集 合，即: Zk={[0]，[1]，[2]，…，[k-1]} <Zk ，>是群（剩余类加群）， <Zk ，>是半群（剩余类乘半群）， ∵ 对 [i]，[j]，[k] Zk 有[i]（[j][k]）=[i(j+k)]=[ij+ik] =[ij][ik] =([i][j])([i][k]） ∴ <Zk ，，>是环，称为（模k）剩余类环。 特别， k=2时，称为布尔环。

第三部分逻辑学第六章命题逻辑第一节命题演算6-1-1 命题1.什麽叫命题其结果能判断真假，但不能既真又假的陈述句，称为命题。

作为判断使用的句子都是陈述句。

2.作为命题的陈述句，不能分成更简单的陈述句，这样的命题叫原子命题。

即简单命题。

3.什麽叫命题的真值作为命题的陈述句的判断结果，即正确（对应着真命题）或错误（对应着假命题）的两个值。

4.为了研究方便，我们把简单命题符号化。

每一个简单命题用一个小写英文字母表示。

而命题真值也要符号化。

用 1 表示命题的结果是真，即真命题；用 0 表示命题的结果是假，即假命题。

联结词与复合命题及其真值1.我们称用联结词联结在一起的简单命题为复合命题。

（1）否定联结词与命题否定式：“﹁”是否定联结词。

通过他可以构成命题否定式。

例如：用 p 表示“4是素数”。

p 的真值显然是假，即真值为 0；¬ p 表示假命题 p 的否定式，¬ p 的真值自然为真，即为 1。

（2）合取联结词与命题的合取式：“∧”是合取联结词。

通过他可以构成命题的合取式。

例如：p∧q，即 p 与 q 同时为真，复合命题的值才为真，即0 ∧ 0 = 0；0 ∧ 1 = 0；1 ∧ 0 = 0；1 ∧ 1 = 1。

所以，在p，q取不同真值的4种情况下，命题的合取式只有一个真值。

（3）析取联结词与命题析取式：“∨”是析取联结词。

通过他可以构成命题的析取式。

例如：p∨q，只要 p 、q 中至少一个真值为真，其值便为真，即0 ∨ 0 = 0；0 ∨ 1 = 1；1 ∨ 0 = 1；1 ∨ 1 = 1。

所以，在 4 种情况下，只有一个情况是假命题，即简单命题同时为假时命题析取式真值为 0。

（4）蕴涵联结词与命题蕴涵式：“如果... 则...”被称为蕴涵联结词，采用蕴涵符号“→”。

在这类句型中，q 是 p 的必要条件；p 是 q 的充分条件；蕴涵式 p→q 只有一个假值，即p为真，q 为假时蕴涵式命题的真值为 0。

13
实例
在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？
14
无向哈密顿图的一个必要条件
定理15.6 设无向图G=<V,E>是哈密顿图，对于任意V1V且 V1，均有 p(GV1) |V1|
证 设C为G中一条哈密顿回路。
当V1顶点在C上均不相邻时， p(CV1)达到最大值|V1|，
求图中1所示带权图k29主要内容欧拉通路欧拉回路欧拉图半欧拉图及其判别法哈密顿通路哈密顿回路哈密顿图半哈密顿图带权图货郎担问题基本要求深刻理解欧拉图半欧拉图的定义及判别定理深刻理解哈密顿图半哈密顿图的定义
第十五章 欧拉图与哈密顿图
主要内容
➢ 欧拉图 ➢ 哈密顿图 ➢ 带权图与货郎担问题
1
15.1 欧拉图
大时，计算量惊人地大
27
例6 求图中(1) 所示带权图K4中最短哈密顿回路.
(1)
(2)
解 C1= a b c d a,
W(C1)=10
C2= a b d c a,
W(C2)=11
C3= a c b d a,
W(C3)=9
可见C3
(见图中(2))
是最短的，其权为9. 28
第十五章 习题课
主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题
点.
由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）. (1) m=1时，G为一个环，则G为欧拉图. (2) 设mk（k1）时结论为真，m=k+1时如下证明：
5
从以上证明不难看出：欧拉图是若干个边不重的圈之 并，见示意图3.