5.1 图论（图的表示、路径、树、网络流、染色问题）

文档摘要

5.1 图论（图的表示、路径、树、网络流、染色问题） 5.1 图论：离散结构中的网络之舞图论，作为离散数学的核心支柱之一，早已超越了其最初作为“七桥问题”智力游戏的朴素起源，演化为现代科学与工程中不可或缺的建模语言。它以点与线的抽象组合，映射着社交网络的人际联结、计算机系统的数据流动、生物体内的代谢通路、交通网络的路径规划——凡是有“关系”的地方，图论便悄然登场。在本章中，我们将深入剖析图的表示机制、路径的探索策略、树的结构性质、网络流的优化算法，以及染色问题背后的组合约束，力求在严谨的数学框架下，揭示这些概念如何交织成一张既优美又实用的理论之网。一、图的表示：从抽象到可计算一个图 $ G = (V, E) $，由顶点集 $ V $ 和边集 $ E $ 构成。