总度数(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的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。可达性是一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。
匿名回答于2021-02-11 08:15:28
-连通图：任意两个顶点连通的无向图
-连通分量：无向连通图的极大连通子图
1. 如果有n个顶点，边数＜n-1，则此图非连通图
2. 全部顶点的度的和 = 边数的2倍
3. 有n个顶点，并且有 ＞n-1条边，则图一定有环
4. 边数取值范围从0到n(n-1)/2
5. 边数为n(n-1)/2时，叫完全图
6. 顶点数为n，则它的生成树含有n-1条边
-连通图的生成树是包含全部顶点的一个极小连通子图
7. 连通无向图最少边数 = (n-1)(n-2)/2+1 n为顶点数
8. 非连通无向图的边数 = n(n-1)/2+1
-任意顶点的入度 = 出度
9. 无向连通图边数至少为 = n-1
匿名回答于2021-10-06 22:09:37
