第八章 一些特殊的图
- 格式：ppt
- 大小：617.00 KB
- 文档页数：49
下载文档原格式
合集下载
第八章界面现象-1
一般T ,液体的 — 这是由于因T升
高，物质体积膨胀，分子间距离增加，分子
间相互作用减弱，表面张力也减小。
非极性非缔合的有机液体与T有如下
线性经验关系式：
MB
B
2/ 3
k ' Tc
T
6K
MB，B——液体的摩尔质量及体积质量；
Tc——临界温度；k´——经验常数。
29
4、溶液组成的影响
溶液中加入溶质后,溶液的表面张力将发生变化. 表面活性物质:显著降低
36
p = pl - pg = 2 /r
附加压力 p 总是指向球面的球心 （或曲面的曲心)。
若为液泡（肥皂泡）：则泡内气体的 压力比泡外气体的压力大，其差值为
p =4 / r
因为液膜内外两个面，其半径几乎相 等。
37
3、实例：冶金熔池中的气泡
如图8-6，气泡内的总压力p为： 钢
p = pex+gh+p
溶液
高分散度固体颗粒
r2
r1
r0
正常固体颗粒
c0 c1 c2
c
溶液的化学势与浓度的关系
49
四、微小气泡的产生与液体的过热现象
ΔT称为过热度 ΔT=T1 - T0 或ΔT=T2 - T0
沸石或玻璃 毛细管
p
正常沸腾的气泡
r0
微小
r1
气泡
p0
S0
S1
r2
S2
p1
p2
ΔT
T0 T1 T2 T
微小气泡的蒸气压与液体的过热
液体的过冷现象: 在一定压力下，当液体的温度已低于该压力 下液体的凝固点，而液体仍不凝固的现象。
上述过饱和蒸气、过饱和溶液、过热液体、
药理学 第八章抗高血压药 图文
高血压患者中，原发性高血压约占90-95%， 继发性高血压约占5-10% 。
原发性高血压
原发性高血压病因不明，目前认为是 在一定遗传背景下由于多种后天因素（ 血 压调节异常、RAS 异常、高钠、精神神经 因素、血管内皮的功能异常、胰岛素抵抗、 肥胖、吸烟、大量饮酒等）使血压的正常 调节机制失代偿所致。
2. 遗传学说
至今尚未发现有特殊的血压调节基因组合，也未发 现有早期检出高血压致病的遗传标志。据统计双亲均有 高血压的正常血压子女，以后发生高血压的比例增高。 自发性高血压大鼠（SHR）就是通过动物实验筛选出的 遗传性高血压大鼠株。
在人群研究中发现，盐敏感者中具有高血压家族史 的比例是盐不敏感者的215倍，盐敏感者长期高盐饮食可 导致高血压。可以认为高血压的易感性基因可能被遗传。
主要成分
利血平、双克、双肼屈嗪、异丙嗪 可乐定、双克 利血平、双克、双肼屈嗪、氨苯蝶啶 双肼屈嗪、胍乙啶、双克
第二节 常用抗高血压药
一、肾素-血管紧张素系统抑制药 肾素-血管紧张素系统（RAS）及其功能
1、RAS的构成与分布
血管紧张素原
ACE抑制剂
肾素
缓激肽（BK）
血管紧张素Ⅰ
降解产物
ACE 血管紧张素Ⅱ 血管紧张素Ⅲ
肾素抑制剂
血管紧张素Ⅳ
AT4
AT1阻断剂
血管紧张素Ⅱ受体（AT1）
心血管效应 醛固酮释放
2、局部组织RAS
（1）肾脏 RAS RAS首先在肾脏发现。肾素产生于肾小球，主要分
布在入球和出球小动脉、叶间小动脉。 肾内局部RAS对肾脏血流动力学起调节作用。位于
近曲小管的ACE将AngІ转化为AngⅡ，通过增加Na+-H+交 换及其它可能的机制促进Na+在近曲小管的吸收。
原发性高血压
原发性高血压病因不明，目前认为是 在一定遗传背景下由于多种后天因素（ 血 压调节异常、RAS 异常、高钠、精神神经 因素、血管内皮的功能异常、胰岛素抵抗、 肥胖、吸烟、大量饮酒等）使血压的正常 调节机制失代偿所致。
2. 遗传学说
至今尚未发现有特殊的血压调节基因组合，也未发 现有早期检出高血压致病的遗传标志。据统计双亲均有 高血压的正常血压子女，以后发生高血压的比例增高。 自发性高血压大鼠（SHR）就是通过动物实验筛选出的 遗传性高血压大鼠株。
在人群研究中发现，盐敏感者中具有高血压家族史 的比例是盐不敏感者的215倍，盐敏感者长期高盐饮食可 导致高血压。可以认为高血压的易感性基因可能被遗传。
主要成分
利血平、双克、双肼屈嗪、异丙嗪 可乐定、双克 利血平、双克、双肼屈嗪、氨苯蝶啶 双肼屈嗪、胍乙啶、双克
第二节 常用抗高血压药
一、肾素-血管紧张素系统抑制药 肾素-血管紧张素系统（RAS）及其功能
1、RAS的构成与分布
血管紧张素原
ACE抑制剂
肾素
缓激肽（BK）
血管紧张素Ⅰ
降解产物
ACE 血管紧张素Ⅱ 血管紧张素Ⅲ
肾素抑制剂
血管紧张素Ⅳ
AT4
AT1阻断剂
血管紧张素Ⅱ受体（AT1）
心血管效应 醛固酮释放
2、局部组织RAS
（1）肾脏 RAS RAS首先在肾脏发现。肾素产生于肾小球，主要分
布在入球和出球小动脉、叶间小动脉。 肾内局部RAS对肾脏血流动力学起调节作用。位于
近曲小管的ACE将AngІ转化为AngⅡ，通过增加Na+-H+交 换及其它可能的机制促进Na+在近曲小管的吸收。
第八章泌尿
图8-1 肾单位示意图
第一节 肾脏的解剖和血流特点
肾单位的组成
肾单 位
肾小 体
肾小 管
肾小 肾球小 近囊球 小管 髓袢 细段 远球 小管
近髓曲袢 小降髓管支袢 粗降髓段支袢 细升髓段支袢 细升远段支曲 粗段
第一节 肾脏的解剖和血流特点
皮质肾单位和近髓肾单位：
◎肾单位按其在肾脏中的位置不同分为： –皮质肾单位： 分布于外皮质和中皮质层，约占肾单位总数的80%～90%； 肾小体相对较小，髓袢较短，只达外髓质层，有的甚至不到
图8-4 有效滤过压示意图
第二节 肾小球的滤过作用
影响肾小球滤过的因素：
◎肾小球有效滤过压改变 –肾小球毛细血管血压 –血浆胶体渗透压 –囊内压
◎肾血流量
◎肾小球滤过膜通透性改变 –滤过面积 –滤过膜通透性
第三节 肾小管和集合管的重吸收与分泌作用
肾小管和集合管的物质转运方式：
◎被动转运（passive transport）
◎由骶荐神经丛发出的阴部神经属于躯体神经，兴奋时可使外括约肌 （又称尿道括约肌）收缩，以阻止膀胱内尿液的排出–房室交界。
第六节 排 尿
排尿反射：
◎大脑皮层就发出兴奋冲动，下行传 至脊髓，引起低级排尿中枢兴奋，继 而产生两种效应：一是兴奋盆神经， 二是抑制腹下神经和阴部神经。在这 两种效应的协同作用下，膀胱逼尿肌 发生收缩，内外括约肌发生舒张松弛， 尿液就由膀胱经尿道被排出体外。
肾小球其所带的电荷
图8-3 滤过膜示意图
第二节 肾小球的滤过作用
有效滤过压：滤过膜两侧促使肾小球
滤过作用发生的压力差
◎有效滤过压=肾小球毛细血管压－（血浆 胶体渗透压＋囊内压）
◎肾小球毛细血管不同部位的有效滤过压 是不同的，越靠近入球小动脉，有效滤过 压越大。
第八章 图 (可平面图)讲解
EULER’S FORMULA Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then
15
8.7 可平面图 Planar Graphs
COROLLARY If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
COROLLARY If a connected planar simple graph has e edges and v vertices with v≥3 and no circuits of length three, then e≤2v-4.
r=e-v+2.
7
8.7 可平面图 Planar Graphs
证明：用数学归纳法 ①归纳基础： 面数r=1，r=e-v+2成立。 面 数 r=2 ， G 为 一 多 边 形 ， 且 e=v=3 （e=v=4…）， 得e-v+2=3-3+2=r成立， 或e-v+2=4-4+2=r成立…；
8
8.7 可平面图 Planar Graphs
8.7 可平面图 Planar Graphs
Example: Determine whether the following graph is planar
20
8.7 可平面图 Planar Graphs
Example:
21
8.7 可平面图 Planar Graphs
15
8.7 可平面图 Planar Graphs
COROLLARY If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.
COROLLARY If a connected planar simple graph has e edges and v vertices with v≥3 and no circuits of length three, then e≤2v-4.
r=e-v+2.
7
8.7 可平面图 Planar Graphs
证明：用数学归纳法 ①归纳基础： 面数r=1，r=e-v+2成立。 面 数 r=2 ， G 为 一 多 边 形 ， 且 e=v=3 （e=v=4…）， 得e-v+2=3-3+2=r成立， 或e-v+2=4-4+2=r成立…；
8
8.7 可平面图 Planar Graphs
8.7 可平面图 Planar Graphs
Example: Determine whether the following graph is planar
20
8.7 可平面图 Planar Graphs
Example:
21
8.7 可平面图 Planar Graphs
第八章图论
3. 图的结点与边之间的关系 定义 如果边e={vi,vj}是G的边, 则称结点vi 和vj邻接的, 边e和结点vi ，边e和结点vj称为关联的。 没有与边关联的结点称为孤立点。 关联于同一结点的相异边称为邻接的。 不与任何边邻接的边称为孤立边。
例1
在上图中显然e1和e2, e1与e4是邻接的, 结点v1和v2,v2和v4等是邻接的, 没有孤立点和孤立边。
例2.如下图中:
图(a)是伪图。图(b)是有向多重 图。 最右第三个图是简单图有权图。
三、结点的度
1.定义 图G中关联于结点vi的边的总数称为 结点vi的度, 用deg(vi)表示。
2.定理1(握手定理) 图G的所有结点的度的总和为边数 的二倍。即若G为具有n结点的(n,m)图, 则有： n deg(vi ) 2m
例8 如下图
(a)是连通图。 (b)是一个具有三个分图 的非连通图。 结论： (1)一个图的分图必是连通的； (2)一个连通图一定只能有一个分图。
例11 对于图的连通性，常常由于删除了 图中的结点和边而影响了图的连通性。
在连通图(a)中删除边e后, 则变成了不连通 的图(b)。
8.2 图的矩阵表示
2. 有向图的定义 定义 设G=(V,E), V是一个有限非空集合, E是V中不同元素的有序对偶的集合, 则称G是一有向图。在有向图G中 若vi≠vj,则(vi,vj)和(vj,vi)表示两条 不同的边,且用一个从结点vi指向vj 的箭头表示边(vi,vj)。
定义 具有n个结点和m条边的图称为(n,m)图。 (n,0)图称为零图。(1,0)图称为平凡图。
三、边割集、点割集 定义3 设图G=<V,E>是连通图,若有E的子集S, 使得在图G中删去了S的所有边后, 得到的子图G-S变成具有两个分图的不连通图, 删去了S的任一真子集后所得子图仍是连通图， 则称S是G的一个边割集。 注：割边是边割集的一个特例。
第八章 三元相图
第八章三元相图三元合金系（ternery system）中含有三个组元，因此三元相图是表示在恒压下以温度变量为纵轴，两个成分变量为横轴的三维空间图形。
由一系列空间区面及平面将三元图相分隔成许多相区。
第一节三元相图的基础知识三元相图的基本特点：(1) 完整的三元相图是三维的立体模型；(2) 三元系中可以发生四相平衡转变。
四相平衡区是恒温水平面；(3) 三元相图中有单相区、两相区、三相区和四相区。
除四相平衡区外，一、二、三相平衡区均占有一定空间，是变温转变。
一、三元相图成分表示方法三元相图成分通常用浓度(或成分)三角形（concentration/composition triangle）表示。
常用的成分三角形有等边成分三角形、等腰成分三角形或直角成分三角形。
(一) 等边成分三角形－图形1. 等边成分三角形图形在等边成分三角形中，三角形的三个顶点分别代表三个组元A、B、C，三角形的三个边的长度定为0～100%，分别表示三个二元系(A—B系、B—C系、C—A系)的成分坐标，则三角形内任一点都代表三元系的某一成分。
其成分确定方法如下：由浓度三角形所给定点S，分别向A、B、C顶点所对应的边BC、CA、AB 作平行线(sa、sb、sc)，相交于三边的c、a、b点，则A、B、C组元的浓度为：WA = sc = Ca WB = sa= AbWC = sb= Bc•注：sa+ sb+ sc = 1 Ca + Ab+ Bc= 12. 等边成分三角形中特殊线(1) 平行等边成分三角形某一边的直线。
凡成分点位于该线上的各三元相，它们所含与此线对应顶角代表的组元的质量分数(浓度)均相等。
(2) 通过等边成分三角形某一顶点的直线位于该线上的所有三元系，所含另外两顶点所代表的的组元质量分数(浓度)比值为恒定值。
(二) 成分的其它表示法1.等腰成分三角形当三元系中某一组元B含量较少，而另外两组元(A、C)含量较多，合金点成分点必然落在先靠近成分三角形的某一边(如AC)附近的狭长地带内。
第八章细胞骨架
2、简述中心粒、纤毛和鞭毛的亚微结构及其功能。
3、分别有哪些因素影响微管、微丝的组装和去组 装？
图7-22 细胞质动力蛋白的结构与运输作用
图7-23 轴突运输
图7-24 色素颗粒的运输
纤毛与鞭毛的运动
❖ 纤毛和鞭毛都是某些细胞表面的特化结构, 具有运动功能。 ❖ 鞭毛和纤毛均由基体和鞭杆两部分构成，鞭毛中的微管为
9+2结构，即由9个二联微管和一对中央微管构成，其中二 联微管由AB两个管组成，A管由13条原纤维组成，B管由 10条原纤维组成 。 ❖ 纤毛和鞭毛的运动是依靠动力蛋白（dynein）水解ATP， 使相邻的二联微管相互滑动。
中间纤维的结构
图7-27 中间纤维的装配模型
三、中间纤维的功能
❖为细胞提供机械强度支持 ❖参与细胞连接 ❖中间纤维维持细胞核膜稳定
单体 结合核苷酸
表7-1 胞质骨架三种组分的比较
微丝
微管
球蛋白
αβ球蛋白
ATP
GTP
中间纤维 杆状蛋白 无
纤维直径 结构
极性 组织特异性
7nm 双链螺旋
有 无
25nm 13根原纤维组成中 空管状纤维 有
微丝是由肌动蛋白组成的直径约7nm的骨架纤维，又称肌动 蛋白纤维。
一、微丝成分
二、微丝的装配
三、微丝的动态性质
四、微丝特异性药物
五、微丝结合蛋白
六、微丝的功能
一、微丝成分
❖ 肌动蛋白（actin）是微丝的结构成分 ，呈哑铃形。 ❖ 肌动蛋白有3种异构体即α、β和γ，其中4种α-肌动蛋白，
分别为横纹肌、心肌、血管平滑肌和肠道平滑肌所特有， β和γ分布于肌细胞和非肌细胞中。 ❖ 肌动蛋白的单体称为G-actin，它们形成的多聚体称为Factin。 ❖ 微丝是由两条线性排列的肌动蛋白链形成的螺旋，状如 双线捻成的绳子。
3、分别有哪些因素影响微管、微丝的组装和去组 装？
图7-22 细胞质动力蛋白的结构与运输作用
图7-23 轴突运输
图7-24 色素颗粒的运输
纤毛与鞭毛的运动
❖ 纤毛和鞭毛都是某些细胞表面的特化结构, 具有运动功能。 ❖ 鞭毛和纤毛均由基体和鞭杆两部分构成，鞭毛中的微管为
9+2结构，即由9个二联微管和一对中央微管构成，其中二 联微管由AB两个管组成，A管由13条原纤维组成，B管由 10条原纤维组成 。 ❖ 纤毛和鞭毛的运动是依靠动力蛋白（dynein）水解ATP， 使相邻的二联微管相互滑动。
中间纤维的结构
图7-27 中间纤维的装配模型
三、中间纤维的功能
❖为细胞提供机械强度支持 ❖参与细胞连接 ❖中间纤维维持细胞核膜稳定
单体 结合核苷酸
表7-1 胞质骨架三种组分的比较
微丝
微管
球蛋白
αβ球蛋白
ATP
GTP
中间纤维 杆状蛋白 无
纤维直径 结构
极性 组织特异性
7nm 双链螺旋
有 无
25nm 13根原纤维组成中 空管状纤维 有
微丝是由肌动蛋白组成的直径约7nm的骨架纤维，又称肌动 蛋白纤维。
一、微丝成分
二、微丝的装配
三、微丝的动态性质
四、微丝特异性药物
五、微丝结合蛋白
六、微丝的功能
一、微丝成分
❖ 肌动蛋白（actin）是微丝的结构成分 ，呈哑铃形。 ❖ 肌动蛋白有3种异构体即α、β和γ，其中4种α-肌动蛋白，
分别为横纹肌、心肌、血管平滑肌和肠道平滑肌所特有， β和γ分布于肌细胞和非肌细胞中。 ❖ 肌动蛋白的单体称为G-actin，它们形成的多聚体称为Factin。 ❖ 微丝是由两条线性排列的肌动蛋白链形成的螺旋，状如 双线捻成的绳子。
第八章 对映异构
间接的方法：先人为确定一个旋光方向化合物的构型，然后 通过化学关联法，就可以确定其它化合物的构型。
CHO H OH CH2OH HO CHO H CH2OH
(+)
CHO COOH
(-)
COOH COOH
HgO
H OH CH2OH H OH CH2OH
NOBr
H CH2Br OH
Na-Hg
H CH3 OH
H Cl C a H C CH3 H3C H b Cl C H CH3 Cl2 b H Cl C C Cl H H C a Cl H CH3 CH3 CH3 H Cl CH3 Cl H CH3
S,S-
29%
CH3 Cl 71% Cl CH3
S,R-
[构象分析] 中间体自由基构象能
Cl CH3 H (主)
COOH C CH3 (R )-
(S)-
(S)-
(R)-
基团大小顺序：OH > COOH > CH3 > H
CH3 C HO H CH2CH3 HO
CH3 C CH2CH3 H HO
CH2CH3 C H CH3
S
R
R
COOH H OH CH3 H
CHO OH CH2OH
CHO H OH HO H H OH CH2OH
CH3 OH OH HO HO CH3 CH3 CH3
2. 对映体：互为镜像而又不能重合的两种构型的分子，互为对 映异构体，这种异构称为对映异构。
COOH C CH3 H OH
COOH H C CH3 HO R-(-)-乳酸
[]D20= -3.8o(水)
对 映 体
S-(+)-乳酸
离散数学离散数学第8章 一些特殊的图 PPT课件
在23岁时，他发表了他还是一个17岁的孩子时作出的“奇怪的发 现”，…即《光线系统理论》第一部分，这是一篇伟大的杰作，它对于 光学，就象拉格朗日的《分析力学》之于力学。
哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地
相信，四元数是解决物质宇宙的数学关键。…从来没有一个伟大的数学
家这样毫无希望地错误过。
2
1
3
4
(2) 有限面与无限面：面积有限的区域称为有 限面(或内部面)，否则为无限面(或外部面) 。 上图中，面4是无限面。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
24
(3) 面的次数等于面边界的边数(注意：悬挂边算2 次)，记为deg(R).
(4) 平面图中面的次数之和等于边数m的两倍，即
d(u)+d(v)≥n-1 则G是半哈密尔顿图。
注意:
此定理条件显然不是必要条件，如n≥6的n边形，对于 任意不相邻的顶点u, v, d(u)+d(v)=4，4<n-1，而n边形显 然有哈密尔顿通路。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
18
哈密尔顿图的充分条件
❖ 设G是n(n≥3)阶无向简单图，若G中 任意不相邻的顶点对u,v均满足： d(u)+d(v)≥n 则G是哈密尔顿图。
a
bc
d
e
f g
h
i j
k
l
ba
d
g
e j
f
l
b
a
c
d
g
j
i
e
h
f
k
7/1/2020 9:05 PM
第八章_基本光刻工艺流程-表面准备到曝光
第八章基本光刻工艺流程-表面准备到曝光概述最重要的光刻工艺是在晶圆表面建立图形。
这一章是从解释基本光刻工艺十步法和讨论光刻胶的化学性质开始的。
我们会按照顺序来介绍前四步（表面准备到对准和曝光）的目的和执行方法。
目的完成本章后您将能够：1．勾画出基本的光刻工艺十步法制程的晶圆截面。
2．解释正胶和负胶对光的反应。
3．解释在晶圆表面建立空穴和凸起所需要的正确的光刻胶和掩膜版的极性。
4．列出基本光刻十步法每一步的主要工艺选项。
5．从目的4的列表中选出恰当的工艺来建立微米和亚微米的图形。
6．解释双重光刻，多层光刻胶工艺和平整化技术的工艺需求。
7．描述在小尺寸图形光刻过程中，防反射涂胶工艺和对比增强工艺的应用。
8．列出用于对准和曝光的光学方法和非光学方法。
9．比较每一种对准和曝光设备的优点。
介绍光刻工艺是一种用来去掉晶圆表面层上的所规定的特定区域的基本操作（图8.1）。
Photolithography是用来定义这个基本操作的术语。
还有其它术语为Photomasking, Masking, Oxide或者Metal Removal （OR,MR）和Microlithography。
光刻工艺是半导体工艺过程中非常重要的一道工序，它是用来在不同的器件和电路表面上建立图形（水平的）工艺过程。
这个工艺过程的目标有两个。
首先是在晶圆表面建立尽可能接近设计规则中所要求尺寸的图形。
这个目标被称为晶圆的分辨率（resolution）。
图形尺寸被称为电路的特征图形尺寸（feature size）或是图像尺寸（image size）。
第二个目标是在晶圆表面正确定位图形（称为Alignment或者Registration）。
整个电路图形必须被正确地定位于晶圆表面，电路图形上单独的每一部分之间的相对位置也必须是正确的（图8.2）。
请记住，最终的图形是用多个掩膜版按照特定的顺序在晶圆表面一层一层叠加建立起来的。
图形定位的的要求就好像是一幢建筑物每一层之间所要求的正确的对准。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(4)
(5)
6
定义8.2 设 G = < V, E >为无向图, E*E, 若E*中任意两 条边均不相邻, 则子集E*称为G中的匹配(或边独 立集), 并把E*中的边所关联的两个结点称为在 E*下是匹配的。 e1
e1 e2 e3 e4 e6
e2
e7 e4
(1)
e6
e5
e7
(2)
e5
e3
在图(1)中，{e1}, {e1, e7 }, {e5}, {e4 , e6 }等都是图中 的匹配。在图(2)中找出匹配。 7 2016/3/10离散数学
第八章 一些特殊的图
内容导读: 二部图 欧拉图 哈密顿图 平面图
难点:各种图的判别定理
2016/3/10离散数学
1
C A D
B
2016/3/10离散数学
2
设无向图 G = < V, E > 有两个V的子集V1,V2, 它们具有满足： V1∪V2= V V1∩V2= 图G中的每一边 e 均具有 e = ( v i , vj ) 其中： vi ∈ V1 , vj∈ V2 则称G是一个二部图，
2016/3/10离散数学
(1)
(2)
3
定义8.1 若一个图G的结点集V能划分为两个子 集V1和V2，使得G的每一条边{vi,vj}满足vi∈V1, vj∈V2 , 则称G是一个二部图， V1和V2称为G的 互补结点子集。此时可将G记成 G = < V1,V2, E > 若V1中任一结点与V2中每一结点均有边相连 接, 则称二部图为完全二部图。若|V1|=n, |V2 |=m 则记完全二部图G为Kn, m。
G1
e2
e1
G2
e2
e3
e1
G3
e2
e3
在上图中, {e1, e2 }为G1中的最大匹配, G1中不存在完备 匹配, 更无完美匹配。 G2中{e1, e2 , e3}为完备匹配, 但G2 中无完美匹配。 G3中{e1,e2, e3}为完备匹配, 同时也是完 美匹配。 11 2016/3/10离散数学
v2
v6
v3
v4
定理8.1 一个无向图 G = < V, E >是二部图当且 仅当G中无奇数长度的回路。 下图所示前3个图中, 均无奇数长度的回路, 所以它们都是二部图, 其中图(2)所示为K2, 3, 图(3) 所示为K3, 3, 它们分别与图(4)和(5)同构。
(1)
(2)
(3)
2016/3/10离散数学
8
e1 e6 e2
(2)
e5
e7
e4
e3
在图(2)中, {e2, e5 }, {e3 , e6 },{e1 , e7 , e4 }都是极大 匹配, 其中{e1, e7, e4 }是最大匹配。
2016/3/10离散数学 9
今后常用M表示匹配，设M为G中一个匹配， vV(G), 若存在M中的边与v关联，则称v为M 饱和点，否则v为M非饱和点，若G中每个顶点 都是饱和点，则称M为G中完美匹配。
e22
e’01
e’12
2016/3/10离散数学
8.3 哈密顿图
几个问题 在一个大城市，有很多取款机，那么，如何制定出一个 最优的路线，使运钞车过每个提款机一次就能运送完钱 钞？ 货郎担问题 旅行商人问题 (Traveling Salesman Problem ,TSP) 优化算法——近似解演化算法
26
定理 8.6 —— 必要条件 设无向图G=<V,E>是哈密顿图,对于任意V1 V 且V1 ≠, 均有 p(G-V1)≤| V1 |,其中p(G-V1)为G 中删除V1(删除V1中各顶点及关联的边)后所得图 的连通分支数。 证: 设C为G中任意一条哈密顿回路。 ① 若V1中的顶点在C上彼此相邻，则 p(C- V1)=1 ≤| V1 | ② 设V1中的顶点在C上存在 r( 2≤ r ≤ | V1 | )个 互不相邻，则 p(C- V1)=r ≤| V1 | 一般说来, V1中的顶点在C上既有相邻的,又有不相 邻的,因而总有 p(C- V1) ≤| V1 | ， 27 2016/3/10离散数学
e4 e3 e6 e5 e1
v2
v4
e2
v5
v3
2016/3/10离散数学
e729例 Fra bibliotek.13 利用定理8.6可判断某些图不是哈密顿图
2016/3/10离散数学 25
例8.10 指出下列各图是否哈密顿图,有无哈密顿 通路, 回路？ 解 (1) 容易判断, 存在哈密顿回路, 故是哈密顿图. (2) 只有哈密顿通路, 无哈密顿回路, 故不是哈 密顿图. (3) 无哈密顿通路，显然不是哈密顿图.
(1)
2016/3/10离散数学
(2)
(3)
若在E*中再加入任何一条边就都不是匹配了, 则称E*为极大匹配。边数最多的极大匹配称为 最大匹配，最大匹配中的元素(边)的个数称为G 的匹配数，记为1(G), 简记为1 。
e1 e1 e2 e3 e4 e6
e2
e7 e4
(1)
e6
e5
e7
(2)
e5
e3
2016/3/10离散数学
在图(1)中, {e5}, {e1, e7 }, {e4 , e6 } {e3, e7 }, {e2, e6 } 是极大匹配，后4个是最大匹配，匹配数1 =2。
2016/3/10离散数学 18
例 8.5 考察下图是否为欧拉图 或存在欧拉通路？ ∵ 存在两个奇度顶点 ∴ 根据定理8.4推论知 不是欧拉图. 存在一条欧拉通路
2016/3/10离散数学
19
定理 8.5 有向图D具有欧拉通路 D 是连通的,且除了 两个顶点外,其余顶点的入度均等于出度。在 这两个特殊的顶点中,一个顶点的入度比出度 大1,另一个顶点的入度比出度小1。 推论 一个有向图D是欧拉图 D是连通的，且所有 顶点的入度等于出度。 特别提醒：欧拉回路要求边不能重复，结点可 以重复. 笔不离开纸，不重复地走完所有的边， 回到原处. 就是所谓的一笔画.
2016/3/10离散数学
22
几个问题
1. 在一个大城市，有很多取款机，那么，如何制定出一个 最优的路线，使运钞车过每个提款机一次就能运送完钱 钞？ 货郎担问题旅行商人问题(TSP) 2. 考虑在七天内安排七门课程的考试，要求同一位教师所 任教的两门课程考试不安排在接连的两天里，如果教师 所担任的课程都不多于四门，则是否存在满足上述要求 的考试安排方案？ 时间表问题 3. 国际象棋的跳马是否可以遍历其棋盘，即从任一格出发 跳到每一格仅一次并最后回到出发的棋盘格子？ 4. 在一个至少有5人出席的圆桌会议上（会议需要举行多 次），为达到充分交流的目的，会议主持者希望每次会 议每人两侧的人均与前次不同，这是否可行？请应用图 论知识进行论证。 5. 周游世界问题
哈密尔顿给出了肯定回答，该问题的解是存在
的
哈密尔顿回路(圈)哈密尔顿图 运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题
2016/3/10离散数学 24
8.3 哈密顿图
定义 8.5 经过图（有向图或无向图）中所有顶 点一次且仅一次的通路称为哈密顿通路。 经过图中所有顶点一次且仅一次的回 路称为哈密顿回路。 具有哈密顿回路的图称为哈密顿图. 具有哈密顿通路但不具有哈密顿回路 的图称为半哈密顿图. 注:平凡图是哈密顿图。
2016/3/10离散数学 23
哈密尔顿图
问题 1859年爱尔兰数学家威廉· 哈密尔顿（Sir William Rowan Hamilton William Hamilton）发明了一个小游戏玩具：一 (1805-1865) 个木刻的正十二面体，每面系正五角形，三面交 于一角，共有20个角，每角标有世界上一个重要 城市。哈密尔顿提出一个问题：要求沿正十二面 体的边寻找一条路通过20个城市，而每个城市只 通过一次，最后返回原地。哈密尔顿将此问题称 为周游世界问题。游戏) 求解 抽象为图论问题
篮
排
足
张
2016/3/10离散数学
王
李 赵 陈
12
篮
排
足
篮
排
足
V1
V1
V2 张 篮 V1 王 李 排 赵 陈 足
V2 张 王 李 赵 陈
篮
V1
排
足
剩 下 的 匹 配 同 学 们 自 己 找
V2
2016/3/10离散数学
V2 王 李 赵 陈 张 王 李 赵 陈
13
张
8.2 欧拉图
几个问题 1 ―一笔画”问题 2 ―街道清扫车” 设某封闭式小区的路网结构如图 所示，请证明能否设计出一条路 线使得清洁车从小区大门出发清 扫每条道路恰好一次，且在清扫 完最后一条道路后正好返回小区 大门处。 3 七桥问题 A B
2016/3/10离散数学 20
例8.7 考察下图是欧拉通路或欧拉回路吗？ 三个顶点的度出度与入度相同 是欧拉回路！ ∵ 沿着边 e00, e01, e12, e22, e21, e10, e’01, e’12, e20 e20 回到出发点
e00 v0 e10 e01 v1 e21 e12 v2
21
e1 e1 e2 e3 e4 e6
e2
e7 e4
(1)
e6
e5
e7
(2)
e5
e3
2016/3/10离散数学
在图(1)中不存在完美匹配。在图(2)中, {e1, e7, e4 }是最大匹配，同时也是完美匹配。
10
定义8.3 设 G = < V1, V2, E >为二部图, M为G中一个最大 匹配, 若 |M| = min{ |V1|, |V2| }, 则称M为G中的一 个完备匹配, 此时若|V1|≤ |V2|, 则称M为V1到 V2的 一个完备匹配。如果|V1|= |V2| ,这时M为G中的完 美匹配。 e1