离散数学图的基本概论.pptVIP

(2) 在n阶图中，如果从vi到vj (vi?vj)存在通路，则必存在从vi到vj 的长度小于等于 n–1的基本通路。 (3) 在n阶图中，如果存在从vi到自身的回路，则从vi 到自身存在长度等于n的回路。 (4) 在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度等于n的初级回路。 两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。 连 通 图：G 中任何两个顶点是连通的；否则是分离图。 三、图的连通性 连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。 (1) 自反性：由于规定任何顶点到自身总是连通的； 证明： (2) 对称性：无向图中顶点之间的连通是相互的； (3) 传递性：由连通性的定义可知。 连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G) = 1为连通图。 点割集：无向图G = V,E 为连通图，如果V?V，且在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V中任何真子集中的顶点时，所得子图仍连通，则V是G的点割集。 如果点割集中只有一个顶点，该点为割点。 四、连通图的连通度 点连通度：G为无向连通图，记k(G) = min{|V| V是G的点割集}，称k(G)为G的点连通度。 由定义知，点连通度即使G不连通的需删除顶点的最少数目。 完全图Kn的连通度k(G) = n–1。 存在割点的连通图连通度为1， 分离图的连通度为0； 边割集：设无向图G = V,E 连通，边集E?E，在G中删除E中所有边后所得子图不连通，而删除E中的任何子集中的边后，所得子图仍连通，则E为G的边割集。 如果边割集中只有一边时，该边为割边(或桥) 边连通度：设G为无向连通图，记?(G) = min{| E | E是G的边割集}， ?(G)为G的边连通度。 连通度的性质：k(G) ? ?(G) ? ? (G) 五、有向图的连通性： (1) 如果有向图 D = V,E 中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。 (2) u,v?V，如果存在u到v的一条通路，则说u可达v。 (3) 弱连通图 V,E 中， 任何一对顶点之间，至少有一顶点可达另一个顶点，则 V,E 是单向连通的； 任何两个顶点之间互相可达，称 V,E 强连通。 有向连通图的性质： (1) 强连通一定单向连通，单向连通一定弱连通。反过来都不成立。 (2) 有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。 (充分性) 如果D中存在回路C，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，所以，D中任意两个顶点都是可达的，因而D是强连通的。 证明： 因为vi可达vi+1, i=1,2,…，n–1，让这些通路首尾相连， (2) 有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。 (必要性) D是强连通的，则D中任何两个顶点都是可达的。 则得一回路。显然每个顶点在回路中至少出现一次。 证明： 所以vi到vi+1存在通路， 不妨设D中的顶点 为v1,v2,…,vn， 且vn到v1也存在通路， 8.3 图的矩阵表示 邻接矩阵：设G = V,E 是一个简单图，它有n个顶点，V = {v1,v2,…,vn}，令 aij = 1 vi, vj ?E (或 (vi, vj)?E) 0 vi, vj ?E (或 (vi, vj)?E) 称A(G) = (aij) 为G的邻接矩阵。 一、邻接矩阵及其性质 邻接矩阵的特性：在无向图中： (1) 邻接阵是对称阵； (2) 同一行或者同一列的元素和为对应顶点的度数 (3) 矩阵中所有元素的和为边数的2倍 在有向图中： (1) 同一行的元素和为对应顶点的出度 (2) 同一列的元素和为对应顶点的入度 (3) ? ? aij = 2 m (边的数目) 邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi, vj)。 邻接阵多用于有向图。 关联矩阵： (1) 设G = V,E 为(n,m)无向图, V = {v1,v2,…,vn}, E = {e1, e2,…, em}, 令： mij = 1 0 称M(G) = (mij)nxm为G的关联矩阵。 vi 关联 ej vi 不关联 ej 二、关联矩阵及其性质 (2) 设D = V,E 是有向图且无环，令： mij = 1 0 则称M(D) = (mij)nxm为D的关联矩阵。 –1 D中 vi 是 ej 的始点 vi 与 ej 不关联 vi 是 ej 的终点 无向图的关联矩阵的性质： (握手定理) 有向图的关联矩阵的性