例:图8-1 无序对(v): 用连接顶点v、V的线段 表示,称为无向边; (a)有向图G1(b)无向图 图81(b)表示的是无向图G2,该图的顶点集和 边集分别为 V(G2)={1,V2,v3,V4,V5 E(G2)={(Ⅵ,V2),(v1,v3),(v1,V4), (v2,v3),(v2,v5),(v4,v5)
例：图8-1 v1 v2 v3 v4 v1 v2 v4 v5 v3 （a）有向图G1（b）无向图 G2图8.1（b）表示的是无向图G2，该图的顶点集和 边集分别为： V（G2）={v1，v2，v3，v4，v5 } E（G2）={（vl，v2），（v1，v3），（v1，v4）， （v2，v3），（v2，v5），（v4，v5）} 无序对(vi ,vj )： 用连接顶点vi、vj的线段 表示，称为无向边；
在以后的讨论中,我们约定 (1)一条边中涉及的两个顶点必须不相同,即: 若(v;,V)或<v1,W>是E(G)中的一条边,则要 求v; (2)一对顶点间不能有相同方向的两条有向边; (3)一对顶点间不能有两条无向边,即只讨论简 单的图
在以后的讨论中，我们约定： （1）一条边中涉及的两个顶点必须不相同，即： 若（vi，vj）或<vi，vj>是E（G）中的一条边，则要 求vi≠vj； （2）一对顶点间不能有相同方向的两条有向边； （3）一对顶点间不能有两条无向边，即只讨论简 单的图
完全图 若用n表示图中顶点的数目,用e表示图中边的 数目,按照上述规定,容易得到下述结论:对于 个具有n个顶点的无向图,其边数e小于等于n(n1) /2,边数恰好等于n(n-1)/2的无向图称为无向完 全图;对于一个具有n个顶点的有向图,其边数e小 于等于n(n-1),边数恰好等于n(n-1)的有向图 称为有向完全图。也就是说完全图具有最多的边数, 任意一对顶点间均有边相连
若用n表示图中顶点的数目，用e表示图中边的 数目，按照上述规定，容易得到下述结论：对于一 个具有n个顶点的无向图，其边数e小于等于n（n-1） /2，边数恰好等于n（n-1）/2的无向图称为无向完 全图；对于一个具有n个顶点的有向图，其边数e小 于等于n（n-1），边数恰好等于n（n-1）的有向图 称为有向完全图。也就是说完全图具有最多的边数， 任意一对顶点间均有边相连。 二、完全图
例:图8-2 (a)无向完全图G3(b)有向完全图G4 图8所示的G3与G分别是具有4个顶点的无向 完全图和有向完全图。图3共有4个顶点6条边;图 G共有4个顶点12条边。 若(w,)是一条无向边,则称顶点v和v互为 邻接点
例：图8-2 v1 v2 v3 v4 v1 v2 v3 v4 （a）无向完全图G3（b）有向完全图G4 图8.2所示的G3与G4分别是具有4个顶点的无向 完全图和有向完全图。图G3共有4个顶点6条边；图 G4共有4个顶点12条边。 若（vi，vj）是一条无向边，则称顶点vi和vj互为 邻接点
若<V,v>是一条有向边,则称v邻接到v,V邻 接于,并称有向边V,>关联于与v,或称有向 边,y>与顶点v和v相关联。 度、入度、出度 在图中,一个顶点的度就是与该顶点相关联的 边的数目,顶点v的度记为D(v)。例如在图82 (a)所示的无向图G3中,各顶点的度均为3 若G为有向图,则把以页点V终点的边的数目 称为顶点v的入度,记为D(ⅴ);把以顶点v为始 点的边的数目称为v的出度,记为OD(v),有向 图中顶点的度数等于顶点的入度与出度之和,即D (ⅴ)=|D(v)+OD(v)
若<vi，vj>是一条有向边，则称vi邻接到vj，vj邻 接于vi，并称有向边<vi，vj>关联于vi与vj，或称有向 边<vi，vj>与顶点vi和vj相关联。 三、度、入度、出度 在图中，一个顶点的度就是与该顶点相关联的 边的数目，顶点v的度记为D（v）。例如在图8.2 （a）所示的无向图G3中，各顶点的度均为3。 若G为有向图，则把以顶点v为终点的边的数目 称为顶点v的入度，记为ID（v）；把以顶点v为始 点的边的数目称为v的出度，记为OD（v），有向 图中顶点的度数等于顶点的入度与出度之和，即D （v）=ID（v）+OD（v）