无向图与有向图(续) 定义有向图D=<V,E>,其中 (1)W同无向图的顶点集,元素也称为顶点 (2)E为×的多重子集,其元素 称为有向边,简称边 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图,试写出它的V和E 注意:图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的
6 无向图与有向图(续) 定义 有向图D=<V,E>, 其中 (1) V同无向图的顶点集,元素也称为顶点 (2) E为VV的多重子集，其元素 称为有向边，简称边. 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在 同构(待叙)的意义下是一一对应的
无向图与有向图(续) 通常用G表示无向图,D表示有向图,也常用G泛指 无向图和有向图,用e表示无向边或有向边 VO,E(G),V(D,E(D):G和D的顶点集,边集 n阶图:n个顶点的图 有限图:VE都是有穷集合的图 零图:E=⑦ 平凡图:1阶零图 空图:V=
7 无向图与有向图(续) 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E= 平凡图: 1 阶零图 空图: V=
顶点和边的关联与相邻 定义设k=(v以是无向图G=<VE的一条边称vv为a的端 点,与(以关联.若v≠则称e与v()的关联次数为1 若n=v则称为环,此时称a与n的关联次数为2;若不 是e端点,则称ek与v的关联次数为0.无边关联的顶点称作 孤立点 定义设无向图G=<E>,v"EV,kH∈E,若(v∈E,则称 相邻;若ek2至少有一个公共端点,则称eke7相邻 对有向图有类似定义.设e=(v》是有向图的一条边,又称v是 e的始点,v是e的终点,v邻接到vv邻接于1
8 顶点和边的关联与相邻 定义 设ek=(vi , vj )是无向图G=<V,E>的一条边, 称vi , vj为ek的端 点, ek与vi ( vj )关联. 若vi vj , 则称ek与vi ( vj )的关联次数为1; 若vi = vj , 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不 是ek端点, 则称ek与vi 的关联次数为0. 无边关联的顶点称作 孤立点. 定义 设无向图G=<V,E>, vi ,vjV, ek ,elE, 若(vi ,vj ) E, 则称 vi ,vj相邻; 若ek ,el至少有一个公共端点,则称ek ,el相邻. 对有向图有类似定义. 设ek=vi ,vj 是有向图的一条边,又称vi是 ek的始点, vj是ek的终点, vi邻接到vj , vj邻接于vi
邻域和关联集 设无向图G,v∈VG v的邻域N(v)={∈(∧(u,y)∈E(ONM≠-y} v的闭邻域N(v)=N()U{吵 v的关联集I(v)={ele∈E(O)∧e与v关联} 设有向图D,v∈VD) v的后继元集(v){u∈(D)入M>∈E(GM≠ v的先驱元集rn(v){uu∈(D)A,D>E(G)M≠v v的邻域ND(v)=Tb(v)∪I(v) v的闭邻域N2(v)=N2(叫)儿∪{v
9 邻域和关联集 N (v) (v) D + N (v) N (v) {v} D = D (v) D − N (v) (v) (v) D D D + − = 设无向图G, vV(G) v的邻域 N(v)={u|uV(G)(u,v)E(G)uv} v的闭邻域 = N(v)∪{v} v的关联集 I(v)={e|eE(G)e与v关联} 设有向图D, vV(D) v的后继元集 ={u|uV(D)<v,u>E(G)uv} v的先驱元集 ={u|uV(D)<u,v>E(G)uv} v的邻域 v的闭邻域