图论基础定理概览：握手、可图化与惠特尼定理

《离散数学·图论》是一本深入探讨图论基础的重要教材，它涵盖了丰富的定理和概念，对于理解网络结构和算法设计具有核心价值。以下是一些关键的图论定理概要： 1. 握手定理：无论是无向图（定理14.1）还是有向图（定理14.2），其所有顶点度数之和都等于边数的两倍。这个定理直观地解释了在任何图中，顶点的奇数度会相互抵消，总和必定为偶数。握手定理还引申出一个推论：任何图的奇度顶点数量总是偶数。 2. 可图化与简单图化：定理14.3阐述了非负整数序列可表示为图的度数序列的条件，即序列的总和必须是偶数。同时，定理14.4说明无向简单图的度最大值$\Delta(G)\leq n-1$，这为判断图是否可简单化提供了依据。 3. 路径和回路长度：定理14.5和14.6分别指出，从任意两点间存在路径和回路时，总能找到长度不超过最大节点数减一的初级路径或初级回路。这对于分析图的连通性和循环结构非常有用。 4. 惠特尼定理：此定理（定理14.7）展示了图的极小连通分量数$\kappa(G)$（割点数）、最大独立集数$\lambda(G)$（边割集数）和最小度数$\delta(G)$之间的关系，即$\kappa(G)\leq\lambda(G)\leq\delta(G)$。它揭示了图的连通性质与局部结构之间的联系。 5. 强连通图判定：定理14.8给出了强连通图的定义，即在有向图中，每个顶点都可以通过有向边双向到达其他任何顶点。这个定理提供了一种判断图是否为强连通图的数学标准。 这些定理构成了图论中的基石，它们不仅用于理论研究，也在实际应用中，如网络设计、社交网络分析、算法优化等领域发挥着重要作用。理解和掌握这些定理，对于理解和构建复杂的网络模型至关重要。