第十章图与网络 赵玮
第十章 图与网络 赵 玮
主要内容: ●10.1基本概念 ●10.2最短路回题 (一) Bellman 二) Dijkstra (四) ●10.3最小生成树 (一)基本概念与理论 (二) Kruskal算法(加边法、破圈法) (三)丢边法(破圈法)
3 主要内容： ⚫ 10.1 基本概念 ⚫ 10.2 最短路问题 （一）Bellman最优化原理 （二）Dijustra算法（双括号法） （三）通信线路布施问题 （四）设备更新问题 ⚫ 10.3 最小生成树 （一）基本概念与理论 （二）Kruskal算法（加边法、破圈法） （三）丢边法（破圈法）
主要内容: ●104最大流问题 (一)基本概念 )双号 10.5最小费用 (一)基本概 (二)求解算法
4 主要内容： ⚫ 10.4 最大流问题 （一）基本概念 （二）双标号算法 ⚫ 10.5 最小费用最大流 （一）基本概念 （二）求解算法
s101基本概念 1图 del:一个无向图(简称为图)G是一个有序 的二元组,记为G=(V,E)。其中V={V1…VnB 称为G的点集合,E=(e称为G的边集合,e为 连接V与V的边
5 § 10.1 基本概念 1 图 def1：一个无向图（简称为图）G是一个有序 的二元组，记为G=(V, E)。其中 V={V1…Vn } 称为G的点集合，E=(eij)称为G的边集合，evj为 连接VV与Vj的边
●若N和E均为有限集合,则称为G 为有限图,否则称无限图。 ●若G中既没有有限回路(圈), 也没有两条边连接同一对点,则图a 称G为简单图。如右图之(a), 右图之(b)不是简单图。 ●若G为简单图,且G中每个点对之 间均有一条边相连,则称G为完 全图。如图(a)是简单图,但不 是完全图。 图b
6 ⚫ 若N和E均为有限集合，则称为G 为有限图，否则称无限图。 ⚫ 若G中既没有有限回路（圈）， 也没有两条边连接同一对点，则 称G为简单图。如右图之（a）， 右图之（b）不是简单图。 ⚫ 若G为简单图，且G中每个点对之 间均有一条边相连，则称G为完 全图。如图（a）是简单图，但不 是完全图。 图 a 图 b