第二章 道路与回路1.pptx

第二章 道路与回路;主要内容;道路与回路;P=(e1,e2,e4,e6,e5)每边首尾相接P= (e1,e2,e3,e8,e5,e4) 有向回路P=(e8,e5,e4) 简单有向回路 初级; 无向图定义2.1.2： G=(V,E)中，若点边交替序列P=(Vi1,ei1,Vi2,ei2,..eiq-1,Viq) 中Vik与Vik+1是eik的两个端点，则称P是G中的一条链或道路。 若Vi1=Viq则称P是G中一个圈或回路。 若P中没有重复出现的边，则为简单道路或简单回路。 若P中没有重复的结点，则称为初级道路或初级回路。;;设C是简单图G中含结点数大于3的一个初级回路,若结点Vi和Vj在回路C中不相邻，而边(Vi,Vj)是G的一条边，则称C为一条弦。;1;证明:在G中构造一条最长初级道路(结点不重复) P=(e1,e2,…,em)，记P的起点v0, e1=(v0,v1). 由于P是最长的初级道路，所以与V0有边相连的结点都在路P上。若不在P上，则以该邻接点为起点，构造一条较P多一个点与边的新路，与P是最长的矛盾。 因deg(Vo)?3，故V0至少有3个邻点，它们在P中的出现顺序,如图示不妨依次记为V1,Vj, Vk。在P中V0与V1直接相连，与Vi,Vj不直接相连, 作为V0的邻 点，当然V0与这3个邻点均有边直接相连, 故存在回路{V0,…,V1,…,Vj,…, Vk, V0} 而V0与Vj在回路上不相邻,故边(V0,Vi)为弦。 ;二分图;定理：如果二分图中有回路，则它们必由偶数边组成。 证明：记回路为C ，构造法。 先将回路C的所有边去掉再加,记C的起点x0所在点集为X,另一端点所在集为Y。 从x0出发添上边e1，e1另一个端点x1肯定在Y中(因为二分图)，再从x1出发添边e2，e2另一端点x2肯定在X中(因为二分图).每回到X一次需要占用回路C的边2条。 按此方案来回添边，每回到X一次添加2条边，设最后回到x0完成回路C的构造时，来回的次数为K，则共添加了2k条边。即该回路由偶数条边组成。;连通图与非连通图;例题： 设G是简单图无向图，证明当边数m(n-1)(n-2)/2时，图G是连通图。 证明： 假设G是非连通图，则至少分成2个连通分支，记为G1=(V1,E1),G2=(V2,E2)，其中1?|V1|=n1?n-1， 1?|V2|=n2?n-1，即点数至少为1，最多为n-1。 由于G1是简单图(无重边与环)，因此 m1=|E1|?n1(n1-1)/2，n1 ? n-1 比总点数少1 m2=|E2|?n2(n2-1)/2 n2? n-1 比总点数少1 边数和=m=|E1|+|E2|?n1(n1-1)/2+ n2(n2-1)/2 ?(n-1)(n1-1)/2+(n-1)(n2-1)/2 =(n-1)(n1+n2-2)/2=(n-1)(n-2)/2，与假设矛盾。 ;;树;主要内容;2.2道路与回路的判定;;基于邻接矩阵的判定方法（1）;;而ai1× a1j+ai2× a2j +…+ain× anj 是 ;A=;??;基于邻接矩阵的判定方法（6）;A=;基于邻接矩阵的判定方法（8）;基于邻接矩阵的判定方法（9）;?;WarShall算法;;;;有哪些信誉好的足球投注网站法--判断是否有路;1;基于正向表-判断是否有路 ;例;Thank you！