当前位置：文档之家 › 离散数学讲义-第14讲(7.1-7.2)

离散数学讲义-第14讲(7.1-7.2)

  • 格式：pdf
  • 大小：2.31 MB
  • 文档页数：84

下载文档原格式

  / 84

合集下载

《离散数学 》课件_第7章

《离散数学 》课件_第7章

图 7.2―6
图 7.2―7
7.3 特殊的格
7.3.1 分配格
任何格的元素都能满足分配不等式,但某些特殊格, 其所有元素都能满足分配律。
序关系≤可定义为细分,πi≤πj当且仅当πi中的每一块都在
πj的某一块中。
+分别是保交和
保联。所以〈π(S),≤〉是格。
例如S=｛a,b,c｝,则 π(S)=｛π1,π2,π3,π4,π5｝ π1=｛｛a,b,c｝｝,π2=｛｛a,b｝,｛c｝｝, π3=｛｛a,c｝,｛b｝｝, π4=｛｛a｝,｛b,c｝｝ π5=｛｛a｝,｛b｝,｛c｝｝ 〈π(S),≤〉的哈斯图如图7.1―1(d)所示。 (e)图7.1―1(e)所示的哈斯图也是一个格。
(9) 吸收律的证明。
由公式(1′)有a≥a,由公式(4)有a≥a*b,因此,根据公式
(5′)得a≥a (a*b),但由公式(4′)有a (a*b)≥a,这样,根据 公式(2′)得a Fra biblioteka*b)=a。
(10)a≤b a*b=a a b=b的证明。
先证a≤b a*b=a,由公式1知a≤a,由假设a≤b,所以,由
由对偶原理得a*b=b*a。(下边都仅证两对偶恒等式 中的一个。)
(7) 结合律的证明。
设R=a (b c)和R′=(a b) c,由公式(4′)(加撇表示 右侧的公式,下同)得R≥a,R≥b c,根据公式(4′)和(3′)得 R≥b和R≥c。这样,根据公式(5′)得R≥a b;由R≥a b和R≥c 得R≥(a b) c=R′。类似地可证R′≥a (b c)=R。因此, 根据公式(2′)
(12) 保序性的证明。
公式(11)中d取为a即得。
(13)分配不等式的证明。

离散数学结构 第14章 图的基本概念

离散数学结构 第14章 图的基本概念

第十四章图的基本概念14.1 图 (2)一．无向图与有向图 (2)1．无序积与多重集 (2)2．无向图与有向图的定义及表示法 (2)二．简单图与多重图 (4)1．顶点的度数 (5)2．握手定理 (5)四．图的同构 (8)1．两图同构的定义 (8)2．图之间的同构关系是等价关系 (8)五．完全图与正则图 (9)1．完全图 (9)2．正则图 (9)六．子图与补图 (9)1．子图 (9)2．补图与自补图 (12)14.2 通路与回路 (15)一．通路与回路的定义 (15)二. n阶图中通路与回路的性质 (17)14.3 图的连通性 (17)一、无向图的连通性 (17)二、无向图中顶点之间的线程线及距离 (18)三、无向图的连通度 (18)四、有向图的连通性及其分类 (20)五、扩大路径法及极大路径 (21)六、二部图及判别定理 (22)14.4 图的矩阵表示 (26)一、无向图与有向图的关联矩阵 (26)二、有向图的邻接矩阵 (27)三、有向图的可达矩阵 (29)典型习题 (29)14.5 图的运算 (33)14.1 图主要内容无向图与有向图。

简单图与多重图。

顶点的度数与握手定理。

图的同构。

完全图与正则图。

子图与补图。

学习要求熟练掌握握手定理及其推论的内容及其应用。

掌握图同构的概念。

加深对简单图、完全图、正则图、子图、补图等概念的理解。

一．无向图与有向图1．无序积与多重集设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B.为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A.元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。

例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1.2．无向图与有向图的定义及表示法定义14.1一个无向图是一个有序的二元组<V，E>,记作G，其中（1）V≠称为顶点集，其元素称为顶点或结点。

离散数学第七章计数

离散数学第七章计数

离散数学第七章计数离散数学7.1基本计数原理1.加法原理2.乘法原理离散数学加法原理加法原理又称为和计数原理，也称和规则，存在三种表述形式，其本质是说，整体等于其部分之和。

①若集合某是不相交非空子集S1,S2,…,Sm的并，则|某|=m|Si1i|②若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1种方式，E2发生有e2种方式，…,Em发生有em种方式，则E1或E2或…或Em发生有e1+e2+…+em种方式。

应该指出的是，事件E1和E2互斥是说，E1和E2发生但两者不能同时发生。

离散数学③如果选择事物O1有n1种方法，选择事物O2有n2种方法，…,选择事物Om有nm种方法，并且选择诸事物方法不重叠，则选取O1或O2或…或Om有n1+n2+…+nm种方法。

离散数学加法原理例7.1.1一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。

如果该生对5门数学课和3门生物学课具有选课条件，试问该生有多少方式来选修课程？离散数学乘法原理乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。

①若S1,S2,…,Sm是非空集合，则笛卡尔m积S1S2…Sm的元素个数是|Si|i1②若事件E1,E2,…,Em发生分别有e1,e2,…,em种方式，并且诸事件是独立的，则事件E1或E2或··m依次发生有e1e2…em·或E种方式。

离散数学乘法原理③如果选取事物O1,O2,…,Om分别有n1,n2,…,nm种方法，并且选取诸事物方法不重叠，则事物O1与O2与…与Om依次选取有n1n2…nm种方法。

离散数学乘法原理例7.1.2一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？离散数学乘法原理例7.1.3计数因特网地址。

在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。

离散数学(第十四章)

离散数学(第十四章)
8
实例
强连通
单连通
弱连通
二部图
定义14.23 设 G=<V,E>为一个无向图，若能将 V分成 V1和V2 (V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是 一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分 图、偶图等 )，称V1和V2为互补顶点子集，常将二部图G 记为<V1,V2,E>.
m 2 ( j 1,2,...,m ) ( 2) m d ( v ) ( i 1, 2,...,n) ( 3) m 2m
n i 1 m ij j 1 ij i ij i, j
(4) 平 行 边 的 列 相 同
13
无向图的关联矩阵
例如 M(G)=
211000 010111 000011 000000 001100
1. 删除顶点及删除边 Gv ——从G中将v及关联的边去掉 GV——从G中删除V中所有的顶点 Ge ——将e从G中去掉 GE——删除E中所有边 2. 点割集与边割集 点割集与割点 定义14.16 G=<V,E>, VV V为点割集——p(GV)>p(G)且有极小性 v为割点——{v}为点割集 定义14.17 G=<V,E>, EE E是边割集——p(GE)>p(G)且有极小性 e是割边（桥）——{e}为边割集
6
有向图的连通性
定义14.20 D=<V,E>为有向图 vi vj（vi 可达 vj）——vi 到vj 有通路 vi vj（vi 与vj 相互可达） 性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性 vi 到vj 的短程线与距离 类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,vj)，有向图中d<vi,vj>) 及 d<vi,vj>无对称性

第7章 特殊关系

第7章 特殊关系
0 1 2 11
……
12 20102010-7-2 13 14 23 9292-8
离散数学课程组——国家精品课程, 离散数学课程组——国家精品课程,国家双语教学示范课程 ——国家精品课程
解 (续)
(x1. 对 任 意 x∈A , 有 (x-x) 被 12 所 整 除 , 所 以 <x,x>∈R, 是自反的. <x,x>∈R,即R是自反的. 任意x,y∈A x,y∈A, <x,y>∈R, (x-y)被12整除 整除, 2. 对任意x,y∈A,若<x,y>∈R,有(x-y)被12整除, (y-x)= (x-y)被12整除 所以,<y,x>∈R, 整除, 则(y-x)=-(x-y)被12整除,所以,<y,x>∈R, 是对称的. 即R是对称的. 任意x,y,z∈A x,y,z∈A, <x,y>∈R且 <y,z>∈R, 3. 对 任意 x,y,z∈A , 若 <x,y>∈R 且 <y,z>∈R , 有 (x-y)被12所整除且(y-z)被12所整除 所以(x 所整除且(y 所整除, (x(x-y)被12所整除且(y-z)被12所整除,所以(x(x(yz) = (x-y) + (y-z) 被 12 所 整 除 , 所 以 , <x,z>∈R, 是传递的. <x,z>∈R,即R是传递的. 由1,2,3知R是等价关系. 是等价关系.
一般掌握
了解 3 拟序, 1 拟序,全序 和良序关系的 相关性质. 相关性质.
2
拟序, 1 拟序,全序 和良序关系的 定义; 定义; 2拟序与偏序关 的联系 拟序,全序, 3 拟序,全序, 良序的联系. 良序的联系.

离散数学_无向图和有向图

离散数学_无向图和有向图
21
例2 (续)
(2)
(3)
不同构 入(出)度列不同
度数列相同 但不同构 为什么?
22
完全图
n阶无向完全图Kn: 每个顶点都与其余顶点相邻的n 阶无向简单图.
简单性质: 边数m=n(n-1)/2, ==n-1
n阶有向完全图: 每对顶点之间均有两条方向相反的 有向边的n阶有向简单图.
简单性质: 边数m=n(n-1), ==2(n-1), +=+=-=-=n-1
例 对上一页K4的所有非同构子图, 指出互为补图的 每一对子图, 并指出哪些是自补图.
27
5
无向图与有向图(续)
定义 有向图D=<V,E>, 其中 (1) V同无向图的顶点集, 元素也称为顶点 (2) 边集E为VV的多重子集，其
元素称为有向边，简称边. 用无向边代替D的所有有向边 所得到的无向图称作D的基图
右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的
V 中的所有边为边集的G的子图称作V 的导 出子图，记作 G[V ] (5) 设E E且E , 以E 为边集, 以E 中边关联的 所有顶点为顶点集的G的子图称作E 的导出子 图, 记作 G[E ]
25
子图(续)
例 画出K4的所有非同构的生成子图
26
补图
定义 设G=<V,E>为n阶无向简单图，以V为顶点集, 所有使G成为完全图Kn的添加边组成的集合为边集 的图，称为G的补图，记作 G . 若G G , 则称G是自补图.
12
握手定理(续)
推论 在任何无向图和有向图中，奇度顶点的个数必
为偶数.
证 设G=<V,E>为任意图，令

左孝凌离散数学7.1-7.3


是偶数,而2|E|是偶数，故
三、图的基本性质
例1 求解下列各题: (1)无向完全图Kn有28条边，则它的顶点数n为多少? (2)图G的度数列为2，2，3，5，6，则边数m为多少? (3)图G有12条边，度数为3的顶点有6个，余者度数均小于3
，问G至少由几个顶点？ 解：(1)∵无向完全图Kn的边数m=n(n-1)/2=28，∴n=8。
a
c
a
c
s
b
d
a
b
d
b
v1 v5
v2
v4 v3
v1 v5
点割集V1={v2}
v4 v3
(1)若G是平凡图则E1=，(G)=0 (2)若G存在割边，则(G)=1， (3)规定非连通图的边连通度为(G)=0
二、无向图的连通性
定理2 对于任何一个图 G ，有 k(G)≤λ(G)≤δ(G) 证明 若 G 不连通，则k(G)＝λ(G)＝0，故上式成立 若 G 连通， 1) 证明λ(G)≤δ(G)
i) 若 G 是平凡图，则 λ(G)＝0≤δ(G)， ii) 若G是非平凡图，则因每一结点的所有关联边必含 一个边割集， 故λ(G)≤δ(G) 。 2) 再证 k(G)≤λ(G) (a) 设λ(G)＝1，即G有一割边，即k(G)＝1，上式成立
二、无向图的连通性
(b) 设λ(G)≥2，则必可删去某λ(G)条边，使G不连通， 而删去其中λ(G)-1条边，它仍是连通的，且有一条桥e ＝(u，v)。 对λ(G)-1条边中的每一条边都选取一个不同于u，v的端 点，把这些端点删去，则必至少删去λ(G)-1条边。 若这样产生的图是不连通的，则 k(G)≤λ(G)-1＜λ(G)， 若这样产生的图是连通的，则e仍是桥，此时再删去u或 v，就必产生一个不连通图，即k(G)=λ(G) 故 k(G)≤λ(G)。 由 1) 和 2) 得 k(G)≤λ(G)≤δ(G)

左孝凌离散数学


第七章 图论 7.1 图的基本概念
图7.1.1
第七章 图论 7.1 图的基本概念
如果图7.1.1中的４个结点a，b，c，d分别表示４个人， 当某两个人互相认识时，则将其对应点之间用边连接起 来。这时的图又反映了这４个人之间的认识关系。
我们也可以点代表工厂,以连接两点的连线表示这两 工厂间有业务往来关系。这样便可用图形表示某一城市 中各工厂间的业务往来关系。这种用图形来表示事物之 间的某种关系的方法我们也曾经在第三章中使用过。对 于这种图形,我们的兴趣在于有多少个点和哪些点对间有 线连接,至于连线的长短曲直和点的位置都无关紧要。对 它们进行数学抽象我们就得到以下作为数学概念的图的 定义。
第七章 图论 7.1 图的基本概念
完全图：任意两个不同的结点都是邻接的简单图称为
完全图。n个结点的无向完全图记为Kn。
图7.1.5给出了K3和K4。从图中可以看出K3有３条边，
K4有６条边。容易证明Kn有条边。
n(n 1) 2
图7.1.5K3与K4示意图
图7.1.6
第七章 图论 7.1 图的基本概念
第七章 图论 7.1 图的基本概念
定义7.1.1一个图G是一个序偶〈V(G),E(G)〉，记 为G＝〈V(G),E(G)〉。其中V(G)是非空结点集合， E(G)是边集合，对E(G)中的每条边，有V(G)中的结 点的有序偶或无序偶与之对应。
若边e所对应的结点对是有序偶<a,b>,则称e是有向 边。a叫边e的始点,b叫边e的终点,统称为e的端点。若 边e所对应的结点对是无序偶(a,b),则称e是无向边。 这时统称e与两个结点a和b互相关联。我们将结点a、 b的无序结点对记为(a，b)，有序结点对记为<a，b〉。

离散数学第七章图的基本概念


4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

左孝凌离散数学ppt课件


第七章 图论 7.1 图的基本概念
完全图：任意两个不同的结点都是邻接的简单图称为
完全图。n个结点的无向完全图记为Kn。
图7.1.5给出了K3和K4。从图中可以看出K3有３条边，
K4有６条边。容易证明Kn有条边。
n(n 1) 2
图7.1.5K3与K4示意图
图7.1.6
第七章 图论 7.1 图的基本概念
一个图G可用一个图形来表示且表示是不唯一的。
第七章 图论 7.1 图的基本概念
【例7.1.2】设G=〈V(G),E(G)〉,其中
V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6,e7},e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b) 。
1)若e1，e2，…，ek都不相同， 则称路μ为迹；
2)若v0，v1，…，vk都不相同， 则称路μ为通路；
3)长度大于２的闭的通路（即 除v0＝vk外，其余结点均不相同的 路）μ称作圈。
图7.1.1
第七章 图论
7.2 路与回路
例如在图7.2.1中，有连接v5 到v3的路v5e8v4e5v2e6v5e7v3，这 也是一条迹；路v1e1v2e3v3是一 条通路；路v1e1v2e3v3e4v2e1v1是 一条回路，但不是圈；路 v1e1v2e3v3e2v1是一条回路，也是 圈。
定 义 7.2.1 给 定 图 G ＝ 〈V,E〉, 设 v0,v1,…,vk∈V ， e1 ， e2，…，ek∈E，其中ei是关联于结点vi-1和vi的边，称 交替序列v0e1v1e2…ekvk为连接v0到vk的路，v0和vk分别 称为路的起点与终点。路中边的数目k称作路的长度。 当v0=vk时,这条路称为回路。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。