含平行边的图称为多重图; 既不含平行边也不含环的图称为简单图。 本书主要讨论简单图的相关结论
含平行边的图称为多重图； 既不含平行边也不含环的图称为简单图。 本书主要讨论简单图的相关结论
>设G=<VE>为无向图,e=vy∈E,则称 My为g的端点,e与或与是彼此关联的 >无边关联的顶点称为孤立点。若一条边所关 联的两个顶点重合,则称此边为环。 vv;,则称e与v或e与v的关联次数为1 若vv,则称e与v的关联次数为2;若v不是 e的端点,则称e与v的关联次数0
➢设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；若vi不是 ek的端点，则称ek与vi的关联次数0
设G=Ⅴ,E>为无向图,v1,v∈W,ek,e∈E, (1)若存在一条边e以vpv端点,即e=(vy测则称v 与v是彼此相邻的。简称相邻的 (2)若e与e至少有一个公共端点,则称e1与e是 彼此相邻的。简称相邻的。 设D=<V,E>为有向图,,v∈V,ek,e∈E若 ek=<vv≥,除称v,v是的端点外,还称v为ek 的起点,v为e的终点,并称v邻接到vp,y;邻 接于v
设G=<V,E>为无向图，vi ,vj∈V, ek ,el∈E, (1)若存在一条边e以vi ,vj端点，即e=(vi ,vj )则称vi 与vj是彼此相邻的。简称相邻的。 (2)若ek与el至少有一个公共端点，则称ek与el 是 彼此相邻的。简称相邻的。 设D=<V,E>为有向图,vi ,vj∈V,ek ,el∈E,若 ek=<vi ,vj>, 除称vi ,vj是ek的端点外，还称vi为ek 的起点，vj为ek的终点，并称vi邻接到vj ,vj 邻 接于vi
顶点的度 设G=<VE>为一无向图,v∈V,称v作为 边的端点的次数之和为v的度数,简称为度 记作deg(v)(或d(v))。 设D=ⅤE>为一有向图,v∈V,称v作为 边的始点的次数之和,为v的出度,记作d(v; 称vy作为边的终点的次数之和,为v的入度,记 作d(v);称(y)d(vy)为v的度数,记作d(v 称度数为1的顶点为悬挂顶页点它所对应的 边为悬挂边
顶点的度 设G=<V,E>为一无向图， vi∈V ,称vi作为 边的端点的次数之和为vi的度数，简称为度， 记作deg(vi ) （或d(vi ) ）。 设D=<V,E>为一有向图， vj∈V ,称vj作为 边的始点的次数之和, 为vj的出度，记作d + (vj ); 称vj作为边的终点的次数之和, 为vj的入度，记 作d - (vj );称d + (vj )+ d- (vj )为vj的度数，记作d(vj )。 称度数为1的顶点为悬挂顶点,它所对应的 边为悬挂边
2 5 5e7 5 8 6 (1) 例:在上图(1)中,d(v1)=4,d(v2)=4, a(V 在图(2)中,d+(v1)=2,d(v1)=1,d(v1)=3 dt(v2)=1,d(v2)=3,d(v2)=4
例： 在上图(1)中,d(v1 )=4, d(v2 )=4, d(v5 )=0,……, 在图(2)中, d+ (v1 )=2, d- (v1 )=1,d(v1 )=3 d + (v2 )=1,d- (v2 )=3,d(v2 )=4,…… v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 (1) v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 (2)