无向图的入度和出度是什么

无向图是一类图形结构，其中每个节点都和其他节点相连，但没有方向性。因此，对于无向图，没有入度和出度的概念。然而，在实际应用中，为了方便分析无向图，人们通常将无向图看作是一类有向图的特例，通过引入“虚拟的”或“等效的”方向性来定义它们的入度和出度。

什么是入度和出度？

在有向图中，每个节点可以有多个入度和出度，这些指标用于描述节点的连接情况。具体来说，一个节点的入度表示有多少个边(即连接)指向它，而出度表示有多少个边从它指出。例如，当一条从节点A指向节点B的有向边存在时，节点B的入度为1，而节点A的出度也为1。

无向图的等效有向图

为了将无向图转换为有向图，需要为每条无向边引入两条有向边(即正方向和反方向)，它们分别表示沿两个方向的连接。这些有向边的方向被指定为从一个节点到另一个节点(即它们的头和尾)。例如，在下图(1)中，无向边AB被替换为有向边(AB和BA)。

(1) 无向图与等效有向图

通过这种方式，可以在无向图中“模拟”出入度和出度的概念。对于每个节点，在等效有向图中，它的入度可以定义为以该节点为终点的所有有向边的数量，而它的出度可以定义为以该节点为起点的所有有向边的数量。例如，对于下图(1)的节点A，它的入度为0，出度为2。

无向图的度

与入度和出度类似，无向图的度是一个与节点连接性相关的指标。对于无向图，一个节点的度表示连接(即与它相邻的边)的数量。例如，在下图(2)中，节点B和节点C的度分别为3和4。

(2) 无向图的度

需要注意的是，无向图中的度与入度和出度的概念不同，它是节点连接数的总和，而入度和出度分别描述了指向该节点和从该节点指出的边的数量。

无向图中节点度的性质

无向图中节点度的数量是一个重要的性质，它可以提供有关图形结构的信息。下面是一些关于无向图节点度性质的例子：

1. 所有节点度的总和是偶数。这是因为每个连接都会贡献2个度。这个性质被称为握手引理。它可以方便地用于检查无向图是否存在欧拉路径(即覆盖图中的所有边恰好一次)，因为只有当所有节点度都是偶数时，该条件才会成立。

2. 高度连接的节点在度数上具有较高的值。这意味着具有较高度的节点在整个图中的地位更重要，因为它们与更多的节点相连。

3. 在衰减网络中，度较高的节点更易受攻击。在许多网络应用中，一些节点具有比其他节点更高的度。例如，在社交网络中，一些人比其他人具有更多的朋友。在这种情况下，连接质量的保护成为一个重要的问题，因为衰减网络中的度较高的节点更容易成为攻击的目标。