请输入您要查询的百科知识:

 

词条 入度
释义

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

入度的常见情况

入度为0

顾名思义,入度为0指有向图中的点不作为任何边的终点,也就是说,这一点所连接的边都把这一点作为起点。

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

度的相关定理

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

定理2 任意一个无向图一定有偶数个(或0个)奇点(度为奇数的顶点)。

定理3 无论无向图还是有向图,顶点数n,边数e和度之间又如下关系:

E=(d[v1]+d[v2]+…+d[vn])/2;

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/1 10:20:02