一些定义 豪 (5)称顶点或边用字母标定的图为标定图,否则成 为非标定图。另外,将有向边改为无向边后的图 称为原图的基图。 (6)设G=<V,E>为无向图,e=v)∈E,则称vv 为e的端点,e与v或e导v是彼此关联的。 若v,则称e与v或e与v的关联次数为1 若v=v1,则称e与v的关联次数为2,并称为环 任意的vV,着A且v,则称e与v的关联次 数为0。 12
12 一些定义 （5）称顶点或边用字母标定的图为标定图，否则成 为非标定图。另外，将有向边改为无向边后的图 称为原图的基图。 （6）设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，并称为环。 任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次 数为0
一些定义 豪 (7)设无向图G=<V,E>,vv;∈V,ese∈E。若 存在e∈E,使得e=(vv),则称v与v;是相邻的。 若e与至少有一个公共端点,则称e与是相邻 的 有向图D=<VE>,v1v∈V,e1∈E。若存在 e∈E,使得《vY,则称v为e的始点,v为 e的终点,并称v邻接到v,v邻接于v,若e的 终点为e的始点,则称e与e相邻。 13
13 一些定义 （7）设无向图G=<V,E>，vi ,vj∈V， ek ,el∈E。若 存在et∈E，使得et=(vi ,vj )，则称vi与vj是相邻的。 若ek与el至少有一个公共端点，则称ek与el是相邻 的。 有向图D=<V,E>，vi ,vj∈V，ek ,el∈E 。若存在 et∈E，使得et=<vi ,vj>，则称vi为et的始点，vj为 et的终点，并称vi邻接到vj，vj邻接于vi，若ek的 终点为el的始点，则称ek与el相邻
些定义 豪 (8)设无向图G=<V,E>,对所有的v∈V称 {|u∈∧(,)∈E∧≠v} 为v的邻域,记为N(v), 并称N(v)∪wv}为v的闭邻城,记为N) 称{ele∈E∧e与v相关联}为v的关联集,记为』V)。 设有向图G=<V,E>,对所有的v∈V,称 {∈V∧<v,>∈E∧u≠v} 为v的后继元素。称 {|∈<l,v>∈E∧≠v} 为v的先驱元素。称两者之并为的邻域,记为ND)。 称NUwv},v的闭邻域。 14
14 一些定义 （8）设无向图G=<V,E>，对所有的v∈V称 为v的邻域，记为NG(v)， 并称NG(v) ∪{v}为v的闭邻域，记为 。 称 为v的关联集，记为IG(v) 。 设有向图G=<V,E>，对所有的v∈V，称 为v的后继元素。称 为v的先驱元素。称两者之并为v的邻域，记为ND(v) 。 称ND(v) ∪{v}，v的闭邻域。 { | ( , ) } u u V u v E u v N (v) G { | } e e E e v 与 相关联 { | V , } u u v u E u v { | , } u u V u v E u v
些定义 豪 定义143在无向图中,关联一对顶点的无向边如果多 于一条,则称这些边为平行边,平行边的条数称为 重数。 在有向图中,关联一对顶点的有向边如果多于一条, 并且这些边的始点和终点相同,则称这些边为平行 边 含平行边的图称为多重图,即不含平行边也不含环 的图称为简单图。 15
15 一些定义 定义14.3 在无向图中，关联一对顶点的无向边如果多 于一条，则称这些边为平行边，平行边的条数称为 重数。 在有向图中，关联一对顶点的有向边如果多于一条， 并且这些边的始点和终点相同，则称这些边为平行 边。 含平行边的图称为多重图，即不含平行边也不含环 的图称为简单图
些定义 豪 非多重图称为线图。 由定义可见,简单图是没有环和平行边的图。 线图 简单图 16
16 一些定义 非多重图称为线图。 由定义可见，简单图是没有环和平行边的图