11、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。V5
11、图中任意两点之间均至少有一条通路，则称此图 为连通图，否则称为不连通图。 v 1 v 5 v 4 v 3 v 2 v 6 v 1 v 2 v 3 v 4 v 5
（二）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边(y,v)有权w，，构造矩阵A=(aj)nn，其中:Wij(vi,v,)eEaii0(vi,y,)@ E称矩阵A为网络G的权矩阵。设图G=（V，E）中顶点的个数为n，构造一个矩阵A=(aj)nxn ，其中:(vi,v,)e E(Vi,v,)@E称矩阵A为网络G的邻接矩阵
（二）、 图的矩阵表示 对于网络（赋权图）G= （ V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。 ),( ji vv w ji ⎪⎩ ⎪ ⎨ ⎧ ∉ ∈ = Evv Evvw a ji jiji ji ),(0 ),( nnji = aA × )( nnji = aA × )( ⎪⎩ ⎪ ⎨ ⎧ ∉ ∈ = Evv Evv a ji ji ji ),(0 ),(1 设图G= （ V，E）中顶点的个数为 n，构造一个 矩阵 ，其中： 称矩阵A为网络G的邻接矩阵
V412例2S73232V4V's权矩阵为：邻接矩阵为：0110103V11440640011002700IV2V2410011030502V30VB =A=00111015072V40V400011002031Vs4Vs00011v[100]0333VVVsV1V2, V4VV2V3V1VAV'sV6
654321 6 5 4 3 2 1 010101 101001 010111 101010 001101 111010 vvvvvv v v v v v v B ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡ = 例 权矩阵为： 邻接矩阵为： v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321 6 5 4 3 2 1 030303 302004 020576 305020 007204 346040 vvvvvv v v v v v v A ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡ =
自回路简单图环矩阵表示边数q重合顶点数pA邻接矩阵不含关联边端点B关联矩阵C权矩阵多重边边e=[u,v]G-(V,E)L圈矩阵含平行边M可达矩阵多于1条边多重图D距离矩阵点的次不含边子图偶数0奇数空图点边关系真子图支撑子图孤立点奇点偶点悬挂点各种链的概念悬挂边
空 图 不含边 G=(V,E) 矩阵表示 A 邻接矩阵 B 关联矩阵 C 权矩阵 L 圈矩阵 M 可达矩阵 D 距离矩阵 边e=[u,v] 关联边 端点 重 合 环 自 回 路 多重边 平行边 多于1条边 简单图 不含 多重图 含 点的次 0 1 奇数 偶数 子图 真 子 图 支 撑 子 图 孤 立 点 悬 挂 点 奇 点 偶 点 悬挂边 顶点数 p 边数 q 点边关系 各种链的概念
第二节树已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短V江1、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点
第二节 树 已知有六个城市，它们之间 要架设电话线，要求任意 两个城市均可以互相通话，并且电话线的总长度最短。 v1 v2 v3 v4 v5 v6 1、一个连通的无圈的无向图叫做树。 树中次为1的点称为树叶，次大于1的点称为分支点