离散数学握手定理求无向树边数

握手定理是离散数学中图论的一个经典结果，它用于估算简单无向图中边的数量。握手定理又称为“握手问题”，基于一个直观的观察：在一个无向图中，每条边连接两个顶点，所以每当有一对顶点通过一条边相互接触时，就相当于一次“握手”。每个顶点至多参与一对这样的握手，除了孤立的顶点（没有边相连的顶点），因为它不会形成额外的握手。

设\( n \)是无向树中的顶点数，由于每个非孤立顶点恰好与其他顶点有一条边相连，所以总的边数\( e \)等于所有顶点度数之和的一半减去顶点总数。公式表述为：

\[ e = \frac{1}{2} \sum_{\text{每个顶点}} \text{顶点度数} - n \]

其中，“顶点度数”表示该顶点拥有的边的数量。对于一棵有\( n \)个顶点的树来说，因为树是连通的且没有环，所以它的边数正好是\( n - 1 \)，这是因为从任意一个顶点出发，能到达其余所有顶点，共经过\( n - 1 \)条边。

举个例子，如果有6个顶点的无向树，计算边数就是将每个顶点的度数加起来除以2，然后减去6。如果其中有4个顶点度数是2，1个顶点度数是3，剩下1个顶点是叶子节点（度数为0），则总边数为 \( (2*4 + 3*1) / 2 - 6 = 1 \)。