图论 图论是运筹学中研究图的结构、性质及其应用的数学分支。图由顶点（或节点）和边（连接顶点的线）组成，用于建模对象之间的关系。例如，交通网络中的城市可视为顶点，道路视为边。图论的核心目标是分析图的连通性、路径、优化流等问题。 步骤1：图的基本定义与类型 图 ：形式化定义为 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。边可以是无向（如城市间的双向道路）或有向（如单行道）。 常见图类型 ： 无向图 ：边无方向，表示对称关系（如合作网络）。 有向图 ：边有方向，表示非对称关系（如网页链接）。 加权图 ：边附带数值（如距离、成本），用于优化问题。 连通图 ：任意两顶点间存在路径；否则为非连通图（如孤立的岛屿）。 步骤2：图的表示与基本性质 表示方法 ： 邻接矩阵 ：用矩阵 \( A \) 表示边，\( A_ {ij} = 1 \) 表示顶点 \( i \) 和 \( j \) 之间有边（加权图则存储权重）。 邻接表 ：为每个顶点存储其相邻顶点列表，节省空间（适用于稀疏图）。 基本性质 ： 度 ：顶点的度指与其相连的边数（有向图分为入度和出度）。 路径 ：顶点序列，其中连续顶点由边连接。 最短路径 是图论中的经典问题（如Dijkstra算法）。 步骤3：连通性与树 连通分量 ：无向图中的极大连通子图。非连通图可能包含多个连通分量。 树 ：无环的连通图，具有 \( n \) 个顶点和 \( n-1 \) 条边。树是图的最小连通结构，常用于网络设计（如通信网络布线）。 生成树 ：包含图中所有顶点的树。 最小生成树 （MST）是边权重和最小的生成树，可用Prim或Kruskal算法求解。 步骤4：路径与网络流问题 最短路径问题 ：寻找顶点间权重和最小的路径。算法包括： Dijkstra算法 ：适用于非负权重，按距离递增顺序搜索。 Bellman-Ford算法 ：处理负权重，检测负权环。 网络流 ：研究有向图中从源点到汇点的最大流量（如水管网络）。 最大流-最小割定理 指出最大流等于最小割的容量，可用Ford-Fulkerson算法求解。 步骤5：图论在运筹学中的应用 物流与路由 ：用图模型化运输网络，求解最短路径或车辆路径问题（VRP）。 调度问题 ：用顶点表示任务，边表示依赖关系，通过拓扑排序优化顺序。 社交网络分析 ：顶点表示用户，边表示关系，通过中心性度量（如度中心性）识别关键节点。 图论通过抽象建模现实问题，为运筹学提供结构化的分析工具，其算法（如路径优化、网络流）是决策优化的基础。进一步学习可扩展至图着色、匹配问题等高级主题。