入度

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

入度简介

入度引入

如果

入度定义

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

入度入度的常见情况

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

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

入度相关定理

定理1

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

定理2

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

定理3

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

入度有向图

有向图 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)。