基本概念 在图的定义中,我们规定顶点集V为非空集,但在图的运算中 可能产生顶点集为空集的运算结果,为此规定顶点集为空集 的图为空图,并将空图记为 在将图的集合定义转化成图形表示之后,常用e表示无向边 vVy)或有向边vpy→)称顶点或边用字母标定的图为标定 图,否则,称为非标定图 将有向图各有向边改成无向边后的无向图称为原来图的基图
6 基本概念 ¾ 在图的定义中, 我们规定顶点集V为非空集, 但在图的运算中 可能产生顶点集为空集的运算结果, 为此规定顶点集为空集 的图为空图, 并将空图记为∅. ¾ 在将图的集合定义转化成图形表示之后, 常用ek表示无向边 (vi, vj)(或有向边<vi, vj>), 称顶点或边用字母标定的图为标定 图, 否则, 称为非标定图. ¾ 将有向图各有向边改成无向边后的无向图称为原来图的基图
基本概念 >设G=<VE>为无向图,ek=(vpv)∈E,则称vv为e的端 点,e与v或ek与v是彼此相关联的; 若v≠v则称ek与v或ek与v的关联次数为1若v=v1p则称 ek与v的关联次数为2,并称e为环;Ws∈V若vs≠V且vs≠ vp则称ek与v。的关联次数为0; 设D=V,E>为有向图,ek=vpvy>∈E,称vv为e的端点; 若v1=vp则称ek为D中的环; 无论在无向图中还是有向图中,无边关联的顶点称为孤立点
7 基本概念 ¾ 设G = <V, E>为无向图, ek = (vi, vj)∈E, 则称vi, vj为ek的端 点, ek与vi或ek与vj是彼此相关联的； ¾ 若vi ≠ vj, 则称ek与vi或ek与vj的关联次数为1; 若vi = vj, 则称 ek与vi的关联次数为2, 并称ek为环; ∀vs∈V, 若vs ≠ vi且vs ≠ vj, 则称ek与vs的关联次数为0; ¾ 设D = <V, E>为有向图, ek = <vi, vj>∈E, 称vi, vj为ek的端点; 若vi = vj, 则称ek为D中的环; ¾ 无论在无向图中还是有向图中, 无边关联的顶点称为孤立点
基本概念 >设无向图G=<V,E>,vyeV,eke∈E若彐e∈E,使得et= (vv少则称v与v是相邻的若ek与e。至少有一个公共端点,则 称ek与e是相邻的。 设有向图D=<M,E, Vi VEV,eke∈E.若e∈E,使得et=<Vp y>,则称v为e的始点,v为e的终点,并称v邻接到v1Y邻接于 v若ek的终点为e的始点,则称ek与e相邻
8 基本概念 ¾ 设无向图G = <V, E>, vi, vj∈V, ek, es∈E. 若∃et∈E, 使得 et = (vi, vj), 则称vi与vj是相邻的. 若ek与es至少有一个公共端点, 则 称ek与es是相邻的。 ¾ 设有向图D = <V, E>, vi, vj∈V, ek, es∈E. 若et∈E, 使得 et = <vi, vj>, 则称vi为et的始点, vj为et的终点, 并称vi邻接到vj, vj邻接于 vi. 若ek的终点为es的始点, 则称ek与es相邻
基本概念 设无向图G=<VE>,v∈V称{u|ueV∧(u,v)∈E∧u≠v} 为v的邻域,记做N(v);称N。(v)U{v}为v的闭邻域,记做N(); 称{e|e∈E∧e与v相关联}为v的关联集,记做(v) >设有向图D=<VE>,veV,称{u|ueVA<v,u>∈E∧u≠v} 为v的后继元集,记做r0(v)称{u|u∈V∧<uv>∈E∧u≠v} 为v的先驱元集,记做r(v);称r()Ur(v)为的邻域,记做 ND(v);称Nv)U{v}为v的闭邻域,记做ND()
9 基本概念 ¾ 设无向图G = <V, E>, ∀v∈V, 称 { u | u∈V∧(u, v)∈E∧u ≠ v } 为v的邻域, 记做NG(v); 称 NG(v)∪{ v }为v的闭邻域, 记做 ; 称 { e | e∈E∧e与v相关联 }为v的关联集, 记做IG(v) ¾ 设有向图D = <V, E>, ∀v∈V, 称 { u | u∈V∧<v, u>∈E∧u ≠ v } 为v的后继元集, 记做Γ+D(v); 称 { u | u∈V∧<u, v>∈E∧u ≠ v } 为v的先驱元集, 记做Γ-D(v); 称Γ+(v)∪Γ-(v)为v的邻域, 记做 ND(v); 称ND(v)∪{ v }为v的闭邻域, 记做 ( ) N v G ( ) N v D
平行边,多重图,简单图 定义: 在无向图中,若关联一对顶点的无向边多于1条,则称这些边为 平行边,平行边的条数称为重数 >在有向图中,若关联一对顶点的有向边多于1条,并且这些边的 起点与终点相同即边的方向相同)则称这些边为平行边 >含平行边的图称为多重图;既不含平行边,也不含环的图称为简 单图 10
10 平行边, 多重图, 简单图 定义: ¾ 在无向图中, 若关联一对顶点的无向边多于1条, 则称这些边为 平行边, 平行边的条数称为重数. ¾ 在有向图中, 若关联一对顶点的有向边多于1条, 并且这些边的 起点与终点相同(即边的方向相同), 则称这些边为平行边. ¾ 含平行边的图称为多重图; 既不含平行边, 也不含环的图称为简 单图