选择题 28.  具有n个顶点的有向图,所有顶点的出度之和为m,则所有顶点的入度之和为______。
【正确答案】 A
【答案解析】 度指的是与该顶点相关联的边数。在有向图中,度又分为入度(In-degree)和出度(Out-degree)。以某顶点为弧头,终止于该顶点的弧的数目称为该顶点的入度。以某项点为弧尾,起始于该顶点的弧的数目称为该顶点的出度。在某顶点的入度和出度的和称为该顶点的度。
   在有向图的邻接表中,从一个顶点出发的弧链接在同一链表中,邻接表中结点的个数恰为图中弧的数目,所以,顶点入度之和为弧数和的一倍。如果为无向图,同一条边有两个结点,分别出现在和它相关的两个顶点的链表中,因此,无向图的邻接表中结点个数为边数的2倍。本题中顶点的出度之和为m,所以,所有顶点的入度之和也为m(一条弧对应一个入度与一个出度),通过以上分析可知,选项A正确。