1、运筹帷幄之中决胜千里之外图与网络分析Graphs and Network Analysis第 1页Leonhard Euler(公元 1707-1783年 )欧拉 1707年出生在瑞士的巴塞尔城， 13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰 .伯努利的精心指导。他从 19岁开始发表论文，直到 76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了 886本书籍和论文，其中分析、代
2、数、数论占 40%，几何占 18%，物理和力学占28%，天文学占 11%，弹道学、航海学、建筑学等占 3%。 1733年，年仅 26岁的欧拉担任了彼得堡科学院数学教授。 1741年到柏林担任科学院物理数学所所长，直到 1766年，重回彼得堡，没有多久，完全失明欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。 2哥尼斯堡七桥问题能否从某个地方出发，穿过所有的桥各一次后再回到出发点。ACDB图论模型3第 6章 网 络 分 析| 6.1 图与子图| 6.2 图的连通性| 6.3 树与支撑树| 6.4 最小树问题| 6.5 最短有向 路 问题| 6.6 最大 流 问题| 6.7
3、 最小费用 流 问题| 6.8 最大 对集 问题46.1 图 与 子 图| 图与网络无向图的基本概念有向图和网络| 关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论|子图 5无向图的基本概念图 6.1.16关联 ：一条边的端点称为与这条边的关联邻接 ：与同一条边关联的端点称为是邻接的，同时如果两条边 有一个公共端点，则称这两条边是邻接的有限图 ：任何图 G=(N,E),若 N和 E都是有限集合 ,则称 G为 空图 ：没有任何边的图平凡图 ：只有一个点的图简单图 ：一个图 ,既没有环 ,也没有重边 ,则称为 例如 :(a)是 一简单图 ,但 (b)就不是简单图 .续 17完全图 ：每一对点之间均有一条边相连的图二分图 G=(N,E)： 存在的一个二分划 (S,T)， 使得 G的每条边有一个端点在 S中，另一个端点在 T中完全二分图 G=(S,T,E)： S中的每个点与 T中的每个点都相连的简单二分图简单图 G的补图 :与 G有相同顶点集合的简单图，且补图中的两个点相邻当且仅当它们在 G中不相邻图 6.1.3 (b)(a)续 28续 397BADC2358网 络| 设 G是一个图（有向图），若对 G的每条边（弧）都赋予一个实数，并称为这条边（弧）的权，则 G连同它边（弧）上的权称为一个（有向）网络或赋权（有向）图，记为 G=(N,E,W).图 6.4.1续 4第 10页
