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