《离散数学7.2-3》由会员分享，可在线阅读，更多相关《离散数学7.2-3（39页珍藏版）》请在金锄头文库上搜索。
1、关系性质判别自反反自反对称反对称传递 表达式 IARRIA=R=R1 RR1 IA RRR 关系 矩阵主对 角线 元素 全是1主对角 线元素 全是0矩阵是对称 矩阵若rij1, 且 ij, 则rji 0对M2中1 所在位置, M中相应 位置都是1 关系图 每个 顶点 都有 环每个顶 点都没 有环如果两个顶 点之间有边, 是一对方向 相反的边( 无单边)如果两点 之间有边, 是一条有 向边(无双 向边)如果顶点 xi 连通到 xk , 则从 xi 到 xk 有边 1等价关系的定义与实例定义 设 R 为非空集合上的关系. 如果 R 是自反的、 对称的和传递的, 则称 R 为 A 上的等价关系. 设
2、 R 是一个等价关系, 若R, 称 x 等价于y, 记 做 xy. 实例 设 A=1,2,8, 如下定义A上的关系 R： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的 余数与 y 除以3的余数相等. 2等价关系的验证验证模 3 相等关系 R 为 A上的等价关系, 因为xA, 有x x(mod 3)x, yA, 若 x y(mod 3), 则有 y x(mod 3)x, y, zA, 若x y(mod 3), y z(mod 3), 则有 xz(mod 3)自反性、对称性、传递性得到验证3A上模3等价关系的关系图设 A=1,2,
3、8, R= | x,yAxy(mod 3) 4等价类定义 设R为非空集合A上的等价关系, xA，令 xR = y | yAxRy 称 xR 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,65等价类的性质定理1 设R是非空集合A上的等价关系, 则(1) xA, x 是A的非空子集.(2) x, yA, 如果 x R y, 则 x=y.(3) x, yA, 如果 x y, 则 x与y不交.(4) x | xA=A，即所有等价类的并集就 是A. 6实例A= 1, 2,
4、 , 8 上模 3 等价关系的等价类：1=4=7=1,4,7，2=5=8=2,5,8，3=6=3,6以上3 类两两不交， 1,4,72,5,83,6 = 1,2, ,877.2 通路、回路与图的连通性 简单通(回)路, 初级通(回)路, 复杂通(回)路 无向连通图, 连通分支 弱连通图, 单向连通图, 强连通图 点割集与割点 边割集与割边(桥) 8通路与回路 定义 给定图G=（无向或有向的），设G中顶点与边 的交替序列=v0e1v1e2elvl，(1) 若i(1il), vi1 和 vi是ei的端点(对于有向图, 要求vi1是 始点, vi是终点), 则称为通路, v0是通路的起点, vl是通
5、路 的终点, l为通路的长度. 又若v0=vl，则称为回路.(2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称 为初级通路(初级回路).初级通路又称作路径, 初级回路 又称作圈.(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).9通路与回路说明:n在无向图中，环是长度为1的圈, 两条平行边构成长 度为2的圈.n在有向图中，环是长度为1的圈, 两条方向相反边构 成长度为2的圈.n在有向简单图中, 所有圈的长度2. 10通路与回路 定理 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n1的通
6、路. 推论 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n1的初级通路.定理 在一个n阶图G中，若存在vi到自身的回路， 则 一定存在vi到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在vi到自身的简单回 路，则一定存在长度小于等于n的初级回路. 11无向图的连通性 设无向图G=,u与v连通: 若u与v之间有通路. 规定u与自身总连通 .连通关系 R=| u,v V且uv是V上的等价关系连通图: 平凡图, 或者任意两点都连通的图连通分支: V关于R的等价类的导出子图设V/R=V1,V2,Vk, GV1, GV2, ,GVk是G 的连通分支,
7、 其个数记作p(G)=k.G是连通图 p(G)=112短程线与距离u与v之间的短程线: u与v之间长度最短的通路(u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=.性质：d(u,v)0, 且d(u,v)=0 u=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)d(u,w) （三角不等式)13点割集 记 Gv: 从G中删除v及关联的边GV: 从G中删除V中所有的顶点及关联的边Ge : 从G中删除eGE: 从G中删除E中所有边定义 设无向图G=, 如果存在顶点子集VV, 使 p(GV)p(G)，而且删除V的任何真子集V后（
8、VV） ，p(GV)=p(G), 则称V为G的点割集. 若v为点割集, 则称v 为割点.14点割集例 v1,v4, v6是点割集吗？ v6是割点吗？ v2,v5是点割集吗？ 15边割集定义 设无向图G=, EE, 若p(GE)p(G)且EE, p(GE)=p(G), 则称E为G的边割集. 若e为边割集, 则称e 为割边或桥. 在上一页的图中，e1,e2，e1,e3,e5,e6，e8等是边割集， e8是桥，e7,e9,e5,e6是边割集吗？几点说明： Kn无点割集 n阶零图既无点割集，也无边割集.16有向图的连通性 设有向图D= u可达v: u到v有通路. 规定u到自身总是可达的.可达具有自反性
9、和传递性D弱连通(连通): 基图为无向连通图 D单向连通: u,vV，u可达v 或v可达u D强连通: u,vV，u与v相互可达强连通单向连通弱连通 17有向图的连通性 (1)(2)(3)例 下图(1)强连通, (2)单连通, (3) 弱连通18有向图的短程线与距离u到v的短程线: u到v长度最短的通路 (u可达v) u与v之间的距离d: u到v的短程线的长度 若u不可达v, 规定d=.性质：d0, 且d=0 u=vd+d d 注意: 没有对称性197.3 图的矩阵表示 无向图的关联矩阵 有向图的关联矩阵 有向图的邻接矩阵 有向图的可达矩阵 20无向图的关联矩阵定义 设无向图G=, V=v1,
10、 v2, , vn, E=e1, e2, , em, 令mij为vi与ej的关联次数，称(mij)nm为G的关 联矩阵，记为M(G). 性质21v1v2v4v3e1e2e3e4e5关联次数为可能取值为0，1，222有向图的关联矩阵定义 设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令则称(mij)nm为D的关联矩阵，记为M(D).23v4v1v2 v3e1e2e3e4e5性质: (4) 平行边对应的列相同24定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数，称( )nn为D的邻接矩阵
11、, 记作A(D), 简记为A. 性质有向图的邻接矩阵25v2v1v4v326D中的通路及回路数定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中元素为D中vi到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为D中长度为 l 的通路总数，为D中长度为 l 的回路总数. 27D中的通路及回路数例 有向图D如图所示, 求A, A2, A3, A4, 并回答问题： (1) D中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？ (2) D中长度小于或等于4的通路为多少条？其中有多少条回路？ 推论 设Bl=A+A2+Al(l1), 则Bl中元素为D中长度小于或等于l 的
12、通路数，为D中长度小于或等于l 的回路数.28例长度 通路 回路 合计 50 818 1 211 3 314 1 417 329有向图的可达矩阵定义 设D=为有向图, V=v1, v2, , vn, 令称(pij)nn为D的可达矩阵, 记作P(D), 简记为P. 性质:P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1.30有向图的可达矩阵例 右图所示的有向图D的可达矩阵为317.4 最短路径及关键路径对于有向图或无向图G的每条边，附加一个实数w(e)，则称 w(e)为边e上的权.G连同附加在各边上的实数，称为带权图.设带权图G=,G中每条边的权都大于等于0.u,v为G中
13、任意两个顶点，从u到v的所有通路中带权最小的通路称为u 到v的最短路径.求给定两个顶点之间的最短路径，称为最短路径问题.32算法：Dijkstra(标号法)33v2v0v1v3v4v5141762253例：求图中v0与v5的最短路径34vi kv0v1v2v3v4v500 141138623 843741047959013749v0v1v2v4v3352.关键路径问题定义：PERT图设D=是n阶有向带权图1. D是简单图2. D中无环路3. 有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点4. 记边的权为wij,它常常表示时间36v2v7v1v8v5v4v3v612023441344
14、161. 最早完成时间：自发点v1开始，沿最长路径（权）到达vi所需时间，称 为vi的最早完成时间，记为TE（vi） ，i=1,2,n37v2v7v1v8v5v4v3v612023441344162. 最晚完成时间：在保证收点vn的最早完成时间不增加的条件下，自发 点v1最迟到达vi所需时间，称为vi的最晚完成时间，记为TL（vi）.38v2v7v1v8v5v4v3v612023441344163. 缓冲时间：TS(vi)=TL(vi)- TE(vi)TS(v1)= TS(v3)= TS(v7)= TS(v8)=0TS(v2)=2-1=1;TS(v4)=6-4=2;TS(v5)=10-8=2;TS(v6)=11-9=2若G连通，E为边割集，则p(GE)=2 若G连通，V为点割集，则p(GV)2 39
