有向图

若图中的每条边都是有方向的，则称为有向图。有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如<vi,vj>表示一条有向边，其中vi是边的始点，vj是边的终点。<vi,vj>和<vj,vi>代表两条不同的有向边。

相邻

• 若存在一条边e以vi, vj为端点,即e＝(vi, vj),则称vi, vj是彼此相邻的,简称相邻的．
• 若ek, el至少有一个公共端点,则称ek, el是彼此相邻的,简称相邻的

始点 终点

若ek ＝〈vi, vj〉,除称vi, vj是ek的端点外,还称vi是ek的始点, vj是ek的终点,vi邻接到vj,vj邻接于vi.

度

设D＝<V,E>为一有向图,vj∈V,称：

• vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；
• vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；
• vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj).

显然d(vj) = d + (vj) + d - (vj).

最大度和最小度

对于图G＝<V,E>,记

Δ(G)＝max{d(v)｜v∈V},

(G)＝min{d(v)｜v∈V},

分别称为G的最大度和最小度.

度数序列

设V＝{v1,v2,...,vn}为图G的顶点集,称(d(v1),d(v2),...,d(vn))为G的度数序列，任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.

平行边、重数、多重图、简单图

在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，且它们的始点与终点相同，则称这些边为有向平行边，简称平行边。

含平行边的图称为多重图。既不含平行边，也不含环的图称为简单图。

设D=<V,E>为n阶有向简单图，若对于任意的顶点u,v∈V(u≠v)，既有有向边又有<v,u>，则称D是n阶有向完全图。