图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 邻接矩阵—对于图G=(V,E),|VFn,|E|=m,有nxn阶 方矩阵A=(a)nxn,其中 an1=(k当且仅当v与v之间有条边时 0 其它 关联矩阵—对于图G=(V,E),|VFn,|E|=m,有mxn阶 矩阵M=(mn)mn,其中 2当且仅当v是边e的两个端点 1当且仅当v是边e1的一个端点 0其它
11 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 邻接矩阵——对于图G =（V，E），| V |=n， | E | =m，有nn 阶 方矩阵A =（aij）nn，其中 aij = k 当且仅当vi与vj之间有条边时 0 其它 关联矩阵——对于图G =（V，E），| V |=n， | E | =m，有mn 阶 矩阵M =（mij）mn，其中 mij = 2 当且仅当 vi是边ej 的两个端点 1 当且仅当 vi是边ej 的一个端点 0 其它
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 vI v2 V3 v4 v5 v6 V7 v8 010 图与矩阵 10 000 000 000 00 例 010 00000 11 00001 000 00 e e e 800201000 el e2 e3 e4 e5 e6 e7 e8 e9 el0 ell el2 vI v2 e 000 0100 0000011 000000 0 v4 00000 001 000000 0000 0 0 0 000000 00 000100110000 12
12 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 例 v1 v2 v3 v5 v4 v8 v6 v7 e1 e2 e3 e6 e4 e5 e7 e9 e12 e10 e11 e8 A=（aij） nn= 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 2 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 2 0 1 0 0 0 v1 v2 v3 v4 v5 v6 v7 v8 v1 v2 v3 v4 v5 v6 v7 v8 M=（mij）= 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 v1 v2 v3 v4 v5 v6 v7 v8 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12
图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树(Tree)和最小树 树是图论中一类重要的图,实际中有很多系统的结构都是树。 树—连通且不含圈的图,简记为T 下面的说法是等价的 T是一个树。◇T无圈,且m=n-1。分T连通,且m= n-1。分T无圈,但每加一条新的边即出现唯一一个圈。分T连 通,但每舍去一条边就不连通 T中任意两点,有唯一的一条 链相连。分>T是边数最少的连通图 13
13 图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树（Tree）和最小树 树是图论中一类重要的图，实际中有很多系统的结构都是树。 树——连通且不含圈的图，简记为 T 。 下面的说法是等价的： T 是一个树。 T 无圈，且 m = n-1。 T 连通，且 m = n-1。 T无圈，但每加一条新的边即出现唯一一个圈。 T连 通，但每舍去一条边就不连通。 T中任意两点，有唯一的一条 链相连。 T是边数最少的连通图
图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树(Tree)和最小树 图的生成树若G图的一个点生成子图是一个树,则称此树是G 图的一个生成树。 树的权—若Tk是加权图G的一棵树,则树T的全部边的权之和称 为树Tk的权,记为o(Tk)=o(e);Ve∈Tk 最小树—T*是加权图G的一棵最小树,即(T*)=min{o(Tk) 14
14 图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树（Tree）和最小树 图的生成树—— 若G图的一个点生成子图是一个树，则称此树是G 图的一个生成树。 树的权—— 若Tk是加权图G的一棵树，则树T的全部边的权之和称 为树Tk的权，记为 （ Tk ）= （e）； e Tk 最小树—— T*是加权图G的一棵最小树，即（ T* ）=min{ (Tk ) }
图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树(Tree)和最小树 生成树T 破圈法,避圈法求生成树: 图G 生成树T
15 图与网络分析 Graph Theory and Network Analysis 图的树与最小树问题 树（Tree）和最小树 破圈法，避圈法求生成树： 图G 生成树T 生成树T