基本电路理论 上海交通大本科学课程 2003年7月
基本电路理论 上海交通大学本科学位课程 2003年7月
§13从网络到图 1、网络图论概论 图论是数学领域中一个十分重要的分支,这里 所涉及的只是图论在网络中的应用,称网络 图论。网络图论也称网络拓扑。 为在计算机上系统地列出一个复杂网络的方 程以便分析,就要用到网络图论和线性代数 的一些概念。 随着计算机的发展,网络图论已成为计算机 辅助分析中很重要的基础知识,也是网络分 析、综合等方面不可缺少的工具
§1.3 从网络到图 1、网络图论概论 图论是数学领域中一个十分重要的分支，这里 所涉及的只是图论在网络中的应用，称网络 图论。网络图论也称网络拓扑。 为在计算机上系统地列出一个复杂网络的方 程以便分析，就要用到网络图论和线性代数 的一些概念。 随着计算机的发展，网络图论已成为计算机 辅助分析中很重要的基础知识，也是网络分 析、综合等方面不可缺少的工具
2、图及其概念 图论是数学家欧拉创始的。1736年欧拉解 决了有名的难题,肯尼希堡城七桥问题 该镇的普雷格尔河中有两个小岛,共有七 座桥与两岸彼此连通,问题:从陆地或岛 上任一地方开始,能否通过每座桥一次且 仅仅一次就能回到原地。 欧拉用顶点表示陆地区域,用联接相应顶点 的线段表示各座桥(如左图),于是七桥问 题就变为一道数学问题:在左图中是否可能 D连续沿各线段,从某一始点出发只经过各线 段一次且仅仅一次又回到出发点,即是否存 在一条“单行曲线
2、图及其概念 图论是数学家欧拉创始的。1736年欧拉解 决了有名的难题，肯尼希堡城七桥问题。 该镇的普雷格尔河中有两个小岛，共有七 座桥与两岸彼此连通，问题：从陆地或岛 上任一地方开始，能否通过每座桥一次且 仅仅一次就能回到原地。 A B C D 欧拉用顶点表示陆地区域，用联接相应顶点 的线段表示各座桥（如左图），于是七桥问 题就变为一道数学问题：在左图中是否可能 连续沿各线段，从某一始点出发只经过各线 段一次且仅仅一次又回到出发点，即是否存 在一条“单行曲线”。 • A BC D
欧拉得出了一般结论,即存在 单行曲线的必要、充分条件是A 奇次顶点(联接于顶点的线段 数为奇数)的数目为0。显然 右图不满足此条件,因此,七B 桥问题的答案是否定的。 在七桥问题中,欧拉用点表示陆地,用线段 表示桥。图论中,把一些事物及其之间的联 系用点和连接于点与点之间的线段来表示 因此,图就是一些点与线段的集合
欧拉得出了一般结论，即存在 单行曲线的必要、充分条件是 奇次顶点（联接于顶点的线段 数为奇数）的数目为0。显然 右图不满足此条件，因此，七 桥问题的答案是否定的。 在七桥问题中，欧拉用点表示陆地，用线段 表示桥。图论中，把一些事物及其之间的联 系用点和连接于点与点之间的线段来表示， 因此，图就是一些点与线段的集合。 • A BC D
在网络图中,将支 4 路用线段表示,支 路间的连接用点表 网络图论中的一条标准支路 Vsk =rk ik -isk =g (vk-vs) r(ik -isk)+v V)+
网络图论中的一条标准支路： ① 1 ② ③ ④ 2 3 4 5 6 ① 1 ② ③ ④ 2 3 4 5 6 Sk i ki Sk v k v kr + − + − Sk i ki Sk v k v k g + − + − ( ) ( ) k Sk k k Sk k k k Sk Sk v v r i i v r i i v − = − = − + ( ) ( ) k Sk k k Sk k k k Sk Sk i i g v v i g v v i − = − = − + 在网络图中，将支 路用线段表示，支 路间的连接用点表 示