5
7.1.1 图的定义
邻接点:在无向图中,若存在一条边 (v
i
, v
j
) ,则称 v
i
和 v
j
互为邻接点。称边
(v
i
, v
j
) 依附于顶点 v
i
和 v
j
或称边 (v
i
, v
j
) 与顶点 v
i
和 v
j
相关联。
顶点的度:在无向图中,与顶点 v 相关联的边数称为顶点 v 的度,记作
TD(v) 。
在有向图中,顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以
顶点 v 为弧头的弧的数目,记作 ID(v) ;顶点的出度是指以顶点 v 为弧尾的弧
的数目,记作 OD(v) 。顶点 v 的度等于顶点 v 的入度和出度之和,即
TD(v)=ID(v)+OD(v) 。
推论 3 :对于无向图,其总度数是总边数的两倍。
推论 4 :对于有向图,其总入度、总出度和总边数相等。
第 4 页 / 共 50 页