无向图中所有顶点的度数之和等于边数的几倍

Question

数据结构:无向图中,所有顶点的度数之和是所有边数的几倍?
这题目有答案吗?我想是我理解错了.高手指点下

Answer 1

总度数（D）等于边数（e）的两倍。

D＝2e

图G的顶点数n和边数e的关系

1、若G是无向图，则0≤e≤n（n－1）／2。

恰有n（n－1）／2条边的无向图称无向完全图（Undireet－edCompleteGraph）。

2、若G是有向图，则0≤e≤n（n－1）。

恰有n（n－1）条边的有向图称为有向完全图（DirectedCompleteGraph）。

对于有向图最短路径问题，其计算过程与无向图最短路径问题相同，主要区别在于：无向图最短路径问题采用单标号法。单标记法是给每个点一个路径标记权；而有最短路径问题的则采用双标号法。双标号方法为每个点分配两个标号：路径和路径权。

扩展资料

对于有向图，情况就不同了，因为存在一条从U到V的路径，而没有暗示存在一条从V到U的路径。

假设D是一个有向图，u和V∈D，如果存在从顶点u到顶点V的路径，则称可以到达顶点V到顶点u的路径。

可达性的概念与从U到v的各种路径的数量和长度无关。此外，对于完备性，规定了任何到达自身的顶点都是可达的。

可达性是一个有向图的顶点的二元关系，根据定义，它是自反的和可传递的。一般来说，可达性既不对称也不反对称。

Answer 2

2倍
每条边都连接2个节点，即一条边对应2个度