入度是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和。

如果则称 a 为从 u 到 v 的弧(arc)，u和 v 为 a 的端点，称 u 是 a 的尾(tail)，v 是 a 的头(head)。

顶点 v 的入度是指以 v 为头的弧的数目；顶点v的出度(outdegree) 是指以 v 为尾的弧的数目。

当入度为 0 时，指有向图中的点不作为任何边的终点，也就是说，这一点所连接的边都把这一点作为起点。

在有向图的拓扑排序中，每次都选取入度为 0 的点加入拓扑队列中，再删除与这一点连接的所有边。

定理1

无向图中所有顶点的度之和等于边数的 2 倍，有向图中所有顶点的入度之和等于所有顶点的出度之和。

定理2

任意一个无向图一定有偶数个（或0个）奇点（度为奇数的顶点）。

定理3

无论无向图还是有向图，顶点数 n ，边数 e 和度之间又如下关系：E=(d[v1]+d[v2]+…+d[vn])/2。

[directed graph,digraph]

有向图 D 是指一个有序三元组 (V(D),A(D),ψD) ，其中 V(D) 是非空的顶点集， A(D) 是与 V(D) 不交的弧集， ψD是关联函数，它使 D 的每条弧对应于 D 的一个有序顶点对(不必相异)。

对应于每个有向图 D，可以在相同顶点集上构造一个新图 G，使得对于 D 的每条弧，G 有一条相同端点的边与之对应。这样的图 G 称为有向图 D 的基础图(underlying graph)，换言之，将 D 中所有边的方向去掉所得到的无向图即为 D 的基础图。

反之，对应于每个无向图G ，可以在相同顶点集上构造有向图 D ，只需把 G 中的每条边换成与该边具有相同端点，但方向相反的两条弧，由此得到的有向图称为 G 的伴随有向图(associated digraph)。特别地，完全图的伴随有向图称为完全有向图(complete digraph)。

给无向图 G 中的每条边一个方向，由此得到的有向图称为 G 的一个定向 (orientation)。特别地，简单图的定向称为定向图 (oriented graph)，完全图的定向称为竞赛图 (tournament)。