上游充通大学 SHANGHAI JIAO TONG UNIVERSITY §1.3.3从网络到图 基本要求： 初步建立网络图论的概念 图、连通图和子图的概念 树、回路和割集的概念 树的选取，基本回路和基本割集的选取 11
11 §1.3.3 从网络到图 基本要求： 初步建立网络图论的概念 图、连通图和子图的概念 树、回路和割集的概念 树的选取，基本回路和基本割集的选取
上游充通大学 SHANGHAI JIAO TONG UNIVERSITY §1.3.3从网络到图 1、网络图论概论 图论是数学领域中一个十分重要的分支，这里所涉及 的只是图论在网络中的应用，称网络图论。网络图论 也称网络拓扑。 为在计算机上系统地列出一个复杂网络的方程以便分 析，就要用到网络图论和线性代数的一些概念。 随着计算机的发展，网络图论已成为计算机辅助分析 中很重要的基础知识，也是网络分析、综合等方面不 可缺少的工具。 12
12 §1.3 .3 从网络到图 1、网络图论概论 图论是数学领域中一个十分重要的分支，这里所涉及 的只是图论在网络中的应用，称网络图论。网络图论 也称网络拓扑。 为在计算机上系统地列出一个复杂网络的方程以便分 析，就要用到网络图论和线性代数的一些概念。 随着计算机的发展，网络图论已成为计算机辅助分析 中很重要的基础知识，也是网络分析、综合等方面不 可缺少的工具
上游充通大兽 SHANGHAI JIAO TONG UNIVERSITY §1.3.3从网络到图 2、图及其概念 图论是数学家欧拉创始的。1736年欧拉解决 了有名的难题，肯尼希堡城七桥问题。该镇 的普雷格尔河中有两个小岛，共有七座桥与 两岸彼此连通，问题：从陆地或岛上任一地 方开始，能否通过每座桥一次且仅仅一次就 能回到原地。 欧拉用顶点表示陆地区域，用联接相应顶点的线 段表示各座桥（如左图)，于是七桥问题就变为 一道数学问题：在左图中是否可能连续沿各线段， 从某一始点出发只经过各线段一次且仅仅一次又 回到出发点，即是否存在一条“单行曲线”。 13
13 2、图及其概念 图论是数学家欧拉创始的。1736年欧拉解决 了有名的难题，肯尼希堡城七桥问题。该镇 的普雷格尔河中有两个小岛，共有七座桥与 两岸彼此连通，问题：从陆地或岛上任一地 方开始，能否通过每座桥一次且仅仅一次就 能回到原地。 欧拉用顶点表示陆地区域，用联接相应顶点的线 段表示各座桥（如左图），于是七桥问题就变为 一道数学问题：在左图中是否可能连续沿各线段， 从某一始点出发只经过各线段一次且仅仅一次又 回到出发点，即是否存在一条“单行曲线” 。 §1.3 .3 从网络到图