下载文档原格式
离散数学（微课版）第4章1. 引言在离散数学的第4章中，我们将讨论图论的基本概念和应用。
图论是研究图及其在现实生活中的应用的数学分支，它在计算机科学、网络设计、运筹学等领域中具有重要的应用价值。
本章将介绍图的定义、图的表示方法、图的遍历算法等内容。
2. 图的定义图由一组节点和一组节点之间的边构成。
节点通常表示现实世界中的对象，而边则表示对象之间的关系。
图可以用于描述各种问题，如社交网络中的用户关系、城市之间的交通网络等。
2.1 有向图和无向图图可以分为有向图和无向图两种类型。
在有向图中，边具有方向，表示节点之间的单向关系。
而在无向图中，边没有方向，表示节点之间的双向关系。
2.2 顶点和边图由顶点和边组成。
顶点是图的节点，用来表示对象。
边连接两个顶点，表示两个对象之间的关系。
2.3 路径和环路径是指在图中从一个顶点到另一个顶点的连接序列。
环是一条路径，其起点和终点相同。
3. 图的表示方法在计算机中，图可以用不同的数据结构来表示。
常见的表示方法包括：3.1 邻接矩阵邻接矩阵是用二维数组表示图的连接关系。
对于无向图，邻接矩阵是对称的，而对于有向图，则不对称。
A B CA010B101C010上述邻接矩阵表示了一个无向图，其中顶点A与顶点B相连，顶点B与顶点C相连。
3.2 邻接表邻接表是用链表表示图的连接关系。
对于每个顶点，邻接表保存了与其相连的其他顶点的信息。
A ->B -> NULLB -> A ->C -> NULLC -> B -> NULL上述邻接表表示了一个无向图，顶点A与顶点B相连，顶点B与顶点A、C相连，顶点C与顶点B相连。
4. 图的遍历算法图的遍历算法是指按照一定的方式访问图中的所有节点。
常见的图的遍历算法有深度优先搜索和广度优先搜索。
4.1 深度优先搜索深度优先搜索从起点开始，尽可能深地访问尚未访问的节点，直到无法继续深入为止，然后回溯到上一个节点，继续深入其他未访问的节点。
第四章代数代数又称为代数结构或代数系统，是用代数方法构造的数学模型。
代数系统对于研究各种数学问题和许多实际问题是很有用的，对计算机科学研究也有很大的实用意义，例如，在程序设计语言的语义研究中，数据结构的研究中，编码理论的研究中，系统生成与结构，语言代数，计算理论以及逻辑电路设计中均有重要的理论和实际意义。
§4.1 一般代数结构这一节开始讨论系统及系统的结构。
第一章与第二章着重讨论了一些集合，一般来讲，不论是什么系统，都是若干个集合按一定的条件构成。
构成的条件可以用列举法给出，更多的是由命题法和归纳法给出。
如果结出的若干个集合不是一些具体的集合，这些不具体的集合概念完全由命题来决定通用的概念，则这种构成系统的方法称为公理的方法。
所以这一节还有一个任务是向公理方法过渡。
4.1.1 代数运算关系是集合，函数是关系，函数是“单值”的关系也是集合。
下面定义的代数运算是一个特殊的函数。
定义4.1.1设X为非空集合，n∈I+，n→称为X上的n元运算，其中n为运算ω的阶(类型)，记为n ω。
①函数ω：X X②X中的每一个元素称为X上的0元运算。
当n ω＝1时，称ω为一元运算，例如实数集合R上的“负”运算；当n ω＝2时，称ω为二元运算，例如R上的“＋”和“*”运算。
二元运算在许多方面的研究中有着重要的意义，在后面二元运算用一个字母θ来表示。
实际上用的0元运算只是集合X中的某些特定的元素，例如R中的0和1。
在上一节中所定义的运算是一元运算。
由定义可以看出，所谓集合X上的n元运算，乃是指某种规则，对于X上的每一个n元序偶，规定了X中唯一的元素与之对应。
,,...,∈S，都有ω定义4.1.2设ω为X上的n元运算，S∈X，如果对于任意a a a n12,,...,‡)∈S，则称S关于ω封闭的。
(†a a a n12例如，考察自然数集合N上的加法运算“＋”，显然非负偶数集合关于“＋”是封闭的，但非负奇数关于“＋”是不封闭的。
第四章关系和有向图Relations and Digraphs关系是计算机科学和离散数学中的一个非常重要的概念，分为二元，多元关系，正如集合的运算一样，关系也有其相应的运算，在理论和应用上具有十分重要的意义。
其中，De Morgan和Russell做了很多工作。
4.1乘积集合和划分Product sets and Partions乘积集合Product sets 又称为卡氏积。
有序对，元素a1, a2,……a n根据一定的顺序排列的元素组合，又称为序偶，记为(a1, a2,……a n)。
其中，a1是第一元素, a2是第二元素，依次类推。
元素的有序性。
特别地， n=2,称为二元组，一般，称为n元组。
(a,b)=(x,y) if and only if a=x and b=y.平面直角坐标系，空间直角坐标系，n维空间。
下面，以n=2 为例。
A,B是两个非空集合，称A⨯B ={(a,b) | a∈A, b∈B}为A与B的乘积集合或笛卡尔乘积。
例如，A={a,b,c}, B={d,e},则A⨯B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}一般来说，我们可以用列表或矩阵的形式来表示。
反之，B⨯A={(d,a),(e,a),(d,b),(e,b),(d,c),(e,c)}考虑到元素的有序性，一般来说，A⨯B≠B⨯A当A，B是有限的非空集合时，则我们有| A⨯B|=|A|⨯|B|进一步，我们考虑一般情形，A1⨯A2⨯……⨯A n ={ (a1, a2,……a n)| 其中，a i∈A i,i=1,2,……,n}接下来，我们考虑乘积集合与集合运算∪，∩的性质A×(B∪C)=(A×B)∪(A×C)A×(B∩C)=(A×B)∩(A×C)(B∪C)×A=(B×A)∪(C×A)(B∩C)×A=(B×A)∩(C×A)注记：(A∪B)×(C∪D)≠(A×C)∪(B×D)(A∪B)×(C∪D)=(A×C)∪(B×C)∪(A×D)∪(B×D)数据库是n元组的一个重要应用。
划分或商集 Partion or Quotient set设A为一个非空集合，A的划分P指的是由A的非空子集所组成的一个集合，满足：A= A1∪A2∪……∪A n, A i≠∅ , A i∩A j=∅, i=1,2,……,n .记P= {A1, A2, ……,A n }，称P是A的一个划分。
.例如，A={a,b,c,d,e,f,g},若A1 ={a,b,c},A2={d,e},A3={f,g},则P={A1，A2，A3}是A的一个划分。
我们还可以有这样的划分，例如，A1 ={a,b},A2={c,d,e,f},A3={g},则P={A1，A2，A3}也是A的一个划分。
显然，划分不是唯一的。
对于一个集合来说，我们允许有多种划分。
HomeworkP114-115 17,264.2关系和有向图Relations and Digraphs关系指的是集合中元素之间的某种相关性。
很显然，两个元素之间的相关就称为二元关系，三个元素之间的相关就称为三元关系，n个元素之间的相关就称为n元关系。
对于关系，我们用符号R来表示。
关系R⊆A⨯B, R称为A到B上的关系, a Relation from A to B. 指的是A⨯B的一个子集。
R⊆A⨯A, R称为A上的关系, a Relation on A. 指的是A⨯A的一个子集.特殊情形，空关系R=Φ，全关系R=A⨯A。
(a,b)∈R,称a与b是R相关的，记作aRb；否则，(a,b)∉R ，称a与b不是R相关的，记作b Ra/.按照特征函数的记法，我们有R(a,b)=1或0例1设A={1,2,3,4}，I A ={(a,a)| a∈A}={(1,1),(2,2),(3,3),(4,4)}是A上的相等关系。
例2 设A={1,2,3,4},Q={(1,2), (1,3),(1,4),(2,3),(2,4),(3,4)} Q是A上的小于关系。
例3 P= I A∪{(1,2), (1,3), (1,4), (2,4)}, P是A上的整除关系。
类似于，集合可以由特征函数来刻画一样。
显然，关系也可以由关系矩阵来刻画。
矩阵中的元素是1或0，满足关系为1，不满足关系为0。
由关系派生的集合Sets Arising from Relations定义域Dom(R) domain of R假定关系R⊆A⨯B，Dom(R)={x| ∃y∈B, (x,y) ∈R}，即，关系R中所有有序对的第一个元素组成的集合；Dom(I A)={1,2,3,4}=A Dom(Q)={1,2,3}=A-{4} Dom(P)={1,2,3,4}=A值域Ran(R) range of RRan(R)= {y∈B|∃x∈A, (x,y) ∈R}，即，关系R中所有有序对的第二个元素组成的集合。
Ran(I A)={1,2,3,4}=A Ran(Q)={2,3,4}=A-{1} Ran(P)={1,2,3,4}=A设R 是A 到B 的一个关系，R ⊆A ⨯B ，A 1⊆A ，则A 1关于关系R 的像集R(A 1)为 R(A 1)={y ∈B| ∃x ∈ A 1, (x,y) ∈R}, the R-relative set of A 1. 特别地，R(x)={y ∈B| (x,y)∈R}, 称为x 关于关系R 的像集。
定理1假定关系R ⊆A ⨯B,A 1⊆A, A 2⊆A, 则 (a) If A 1⊆A 2, then R(A 1)⊆R(A 2). (b) R(A 1∪A 2)=R(A 1)∪R(A 2). (c) R(A 1∩A 2)⊆R(A 1)∩R(A 2).定理2 假定关系R ⊆A ⨯B, S ⊆A ⨯B. 如果∀a ∈A,R(a)=S(a), 则R=S.关系矩阵M R The Matrix of a Relation ，由关系R 诱导的矩阵，称为关系矩阵M R 。
设},,,,{},,,,,{321321n m b b b b B a a a a A ==关系R ⊆A ⨯B, 关系R 可以用矩阵M R =[m ij ]来表示，⎩⎨⎧=01ij mR b a R b a j i j i ∉∈),(),( ⎪⎪⎪⎪⎪⎭⎫⎝⎛=100010000100001AI M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000100011001110Q M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010010101111p M 反之，给定一个矩阵M ，我们可以得到一个关系,记为R M 。
例如，设},,,{},,,{4321321b b b b B a a a A ==⎪⎪⎪⎪⎪⎭⎫⎝⎛=010*********M 则，)},(),,(),,(),,(),,(),,(),,{(33422241312111b a b a b a b a b a b a b a R =关系有向图The Digraph of a Relation设A 是一个有限集合，R 是A 上的一个关系，关系R ⊆A ⨯A ，我们可以使用图形来表达。
G=(V,E),其中，V 表示顶点集合，E 表示边集合（顶点之间的连线，称之为边）。
如果顶点之间的连线具有方向性，故，该图称为有向图。
例如，A={1,2,3,4}，R={(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)}则，我们可以得到如下的关系矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0001100011110011R M其图形见书120页图4.4。
关于顶点的入度，指的是以顶点为终点的边数；关于顶点的出度，指的是离开该顶点的边数。
关于图的详细了解，我们将在第七章讲述。
由关系可以确定矩阵和图由矩阵可以确定关系和图由图可以确定关系和矩阵HomeworkP122-123 18,22,24,284.3关系和图的路径Paths in Relations and Digraphs假定R是集合A上的一个关系，从a到b的长度为n的路径a path of length n 是一个序列π：a,x1,x2,……,x n-1,ba为起点，b为终点，且满足aRx1, x1Rx2,……, x n-1Rb它们将构成一条链，其间包含n+1个元素，当然n+1个元素不是必要条件。
例如，见书上124页的例1。
1,2,5,4,3是长度为4的路径；1,2,5,1是长度为3的路径。
特别地，起点和终点为同一个顶点的路径称之为环。
如上例中的1,2,5,1.由R出发，我们可以定义,,,,32nRRR其中2(2)1,()nij ik kj k R R R r r r ===∧∨R R R n n 1-=Ryx Rx x Rx x xRx x x x y xR Ry x xRx x y xR n n n1322111211112,,,,,,,,,,--∃⇔∃⇔特别地，我们有：R ∞关联关系 connectivity relation for Rx R ∞y 表示在R 中存在从x 到y 的某条路径。
例如，A={a,b,c,d,e},R={(a,a),(a,b),(b,c), (c,d), (c,e), (d,e)}，其图如下。
一方面，我们可以从图中来寻找路径。
因为aRa 和aRa,所以a aR 2, 因为aRa 和aRb,所以b aR 2,因为aRb 和bRc,所以c aR 2, 因为bRc 和cRd,所以d bR 2,因为bRc 和cRe,所以e bR 2, 因为cRd 和dRe,所以e cR 2. 于是，我们有，2R ={(a,a),(a,b),(a,c), (b,d),(b,e),(c,e)}另一方面，我们也可以通过计算来得到。
我们知道，关系R 可以由矩阵M R 来表示,简单来说，我们仍然用R 表示。
⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=0100000000110000010000011R ，2(2)1,()nijik kj k R R R rr r ===∧∨ ，⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=00000000001000011000001112R ， 于是，我们有，2R ={(a,a),(a,b),(a,c), (b,d),(b,e),(c,e)}显然，计算方法相对来说，更好一些。
因为有时图形复杂，容易出现错误。
因此，我们有n n R R ∞=∞=1假定R 是集合A 上的关系，*R 是R 的可达关系，x *R y 指的是x=y 或x R ∞y ，即，x=y或存在从x 到y 的某条路径。
