二、通路与回路的性质：(1)在一个n阶图中，如果从顶点vi到vj(vi?vj)存在通路，则从vi到vj存在长度小于或等于n–1的通路。如果Ln–1，则此通路的顶点数L+1n，从而必有顶点vs，它在序列中不止出现一次，即有序列vi…vs…vs…vj。证明：设vi…vk…vj为vi到vj的长度为L的一条通路，则序列中必有L+1个顶点。在路中去掉vs到vs的这些边，至少去掉一条边后仍是vi到vj的一条通路。此通路比原来如此重复下去，必可得到一条从vi到vj的不多于n–1条边的通路。通路的长度至少少1。第31页，共78页，星期日，2025年，2月5日(2)在n阶图中，如果从vi到vj(vi?vj)存在通路，则必存在从vi到vj的长度小于等于n–1的基本通路。(3)在n阶图中，如果存在从vi到自身的回路，则从vi到自身存在长度等于n的回路。(4)在n阶图中，如果从vi到自身存在一条简单回路，则从vi到自身存在长度等于n的初级回路。第32页，共78页，星期日，2025年，2月5日两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连通图：G中任何两个顶点是连通的；否则是分离图。三、图的连通性第33页，共78页，星期日，2025年，2月5日连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。(1)自反性：由于规定任何顶点到自身总是连通的；证明：(2)对称性：无向图中顶点之间的连通是相互的；(3)传递性：由连通性的定义可知。第34页，共78页，星期日，2025年，2月5日连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G)=1为连通图。第35页，共78页，星期日，2025年，2月5日点割集：无向图G=V,E为连通图，如果V?V，且在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V中任何真子集中的顶点时，所得子图仍连通，则V是G的点割集。如果点割集中只有一个顶点，该点为割点。四、连通图的连通度第36页，共78页，星期日，2025年，2月5日点连通度：G为无向连通图，记k(G)=min{|V|V是G的点割集}，称k(G)为G的点连通度。由定义知，点连通度即使G不连通的需删除顶点的最少数目。完全图Kn的连通度k(G)=n–1。存在割点的连通图连通度为1，分离图的连通度为0；第37页，共78页，星期日，2025年，2月5日边割集：设无向图G=V,E连通，边集E?E，在G中删除E中所有边后所得子图不连通，而删除E中的任何子集中的边后，所得子图仍连通，则E为G的边割集。如果边割集中只有一边时，该边为割边(或桥)第38页，共78页，星期日，2025年，2月5日边连通度：设G为无向连通图，记?(G)=min{|E|E是G的边割集}，?(G)为G的边连通度。连通度的性质：k(G)??(G)??(G)第39页，共78页，星期日，2025年，2月5日五、有向图的连通性：(1)如果有向图D=V,E中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。(2)u,v?V，如果存在u到v的一条通路，则说u可达v。(3)弱连通图V,E中，任何一对顶点之间，至少有一顶点可达另一个顶点，则V,E是单向连通的；任何两个顶点之间互相可达，称V,E强连通。第40页，共78页，星期日，2025年，2月5日有向连通图的性质：(1)强连通一定单向连通，单向连通一定弱连通。反过来都不成立。第41页，共78页，星期日，2025年，2月5日(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。(充分性)如果D中存在回路C，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，所以，D中任意两个顶点都是可达的，因而D是强连通的。证明：第42页，共78页，星期日，2025年，2月5日因为vi可达vi+1,i=1,2,…，n–1，让这些通路首尾相连，(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。(必要性)D是强连通的，则D中任何两个顶点都是可达的。则得一回路。显然每个顶点在回路中至少出现一次。证明：所以vi到vi+1存在通路，不妨设D中的顶点为v1,v2,…,vn，且vn到v1也存在通路，第43页，共78页，星期日，2025年，2月5日8.3图的矩阵表示邻接矩阵：设G=V,E是一个简单图，它有n个顶点，V={v1,v2,…,vn}，令aij