离散数学7.2-3

1,关系性质判别,2,等价关系的定义与实例,定义设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若R,称x等价于y,记做xy.实例设A=1,2,8,如下定义A上的关系R：R=|x,yAxy(mod3)其中xy(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.,3,等价关系的验证,验证模3相等关系R为A上的等价关系,因为xA,有xx(mod3)x,yA,若xy(mod3),则有yx(mod3)x,y,zA,若xy(mod3),yz(mod3),则有xz(mod3)自反性、对称性、传递性得到验证,4,A上模3等价关系的关系图,设A=1,2,8,R=|x,yAxy(mod3),5,等价类,定义设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,6,6,等价类的性质,定理1设R是非空集合A上的等价关系,则(1)xA,x是A的非空子集.(2)x,yA,如果xRy,则x=y.(3)x,yA,如果xy,则x与y不交.(4)x|xA=A，即所有等价类的并集就是A.,7,实例,A=1,2,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,8,8,7.2通路、回路与图的连通性,简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥),9,通路与回路,定义给定图G=（无向或有向的），设G中顶点与边的交替序列=v0e1v1e2elvl，(1)若i(1il),vi1和vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).,10,通路与回路,说明:在无向图中，环是长度为1的圈,两条平行边构成长度为2的圈.在有向图中，环是长度为1的圈,两条方向相反边构成长度为2的圈.在有向简单图中,所有圈的长度2.,11,通路与回路,定理在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.,12,无向图的连通性,设无向图G=,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R=|u,vV且uv是V上的等价关系连通图:平凡图,或者任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R=V1,V2,Vk,GV1,GV2,GVk是G的连通分支,其个数记作p(G)=k.G是连通图p(G)=1,13,短程线与距离,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)=0u=vd(u,v)=d(v,u)（对称性）d(u,v)+d(v,w)d(u,w)（三角不等式),14,点割集,记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义设无向图G=,如果存在顶点子集VV,使p(GV)p(G)，而且删除V的任何真子集V后（VV），p(GV)=p(G),则称V为G的点割集.若v为点割集,则称v为割点.,15,点割集,例v1,v4,v6是点割集吗？v6是割点吗？v2,v5是点割集吗？,16,边割集,定义设无向图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阶零图既无点割集，也无边割集.,17,有向图的连通性,设有向图D=u可达v:u到v有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通):基图为无向连通图D单向连通:u,vV，u可达v或v可达uD强连通:u,vV，u与v相互可达强连通单向连通弱连通,18,有向图的连通性,19,有向图的短程线与距离,u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=.性质：d0,且d=0u=vd+dd注意:没有对称性,20,7.3图的矩阵表示,无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵,21,无向图的关联矩阵,定义设无向图G=,V=v1,v2,vn,E=e1,e2,em,令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).性质,22,关联次数为可能取值为0，1，2,23,有向图的关联矩阵,定义设无环有向图D=,V=v1,v2,vn,E=e1,e2,em,令则称(mij)nm为D的关联矩阵，记为M(D).,24,性质:(4)平行边对应的列相同,25,定义设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点vi邻接到顶点vj边的条数，称()nn为D的邻接矩阵,记作A(D),简记为A.性质,有向图的邻接矩阵,26,27,D中的通路及回路数,定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.,28,D中的通路及回路数,例有向图D如图所示,求A,A2,A3,A4,并回答问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？,推论设Bl=A+A2+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.,29,例,长度通路回路,合计508,1,81,2,113,3,141,4,173,30,有向图的可达矩阵,定义设D=为有向图,V=v1,v2,vn,令称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.,31,有向图的可达矩阵,例右图所示的有向图D的可达矩阵为,32,7.4最短路径及关键路径对于有向图或无向图G的每条边，附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的实数，称为带权图.设带权图G=,G中每条边的权都大于等于0.u,v为G中任意两个顶点，从u到v的所有通路中带权最小的通路称为u到v的最短路径.求给定两个顶点之间的最短路径，称为最短路径问题.,33,算法：Dijkstra(标号法),34,例：求图中v0与v5的最短路径,35,v0,v1,v2,v4,v3,36,2.关键路径问题,定义：PERT图设D=是n阶有向带权图D是简单图D中无环路有一个顶点出度为0，称为发点；有一个顶点入度为0，称为收点记边的权为wij,它常常表示时间,37,1.最早完成时间：自发点v1开始，沿最长路径（权）到达vi所需时间，称为vi的最早完成时间，记为TE（vi），i=1,2,n,38,2.最晚完成时间：在保证收点vn的最早完成时间不增加的条件下，自发点v1最迟到达vi所需时间