第十章图与网络 赵玮
第十章 图与网络 赵 玮
主要内容: ●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
def2:一个有向图G是一个有序的二元组,记为 G=(V,A),其中V=(V1V2…Vn)称为G的点集合, A={an称为G的弧(有向边)集合,a;是以V 指向V的一条弧。 ●V=n表示G中节点个数为n,此节点个数n也称 为图G的阶 ●|A=m表示有向图G中弧的个数为m ●任一顶点相关联(连接)的边的数目称为该顶 点的次数
7 def 2：一个有向图G是一个有序的二元组，记为 G=(V, A)，其中V=(V1V2…Vn )称为G的点集合， A={aij}称为G的弧（有向边）集合，aij是以Vi 指向Vj的一条弧。 ⚫ |V|=n表示G中节点个数为n，此节点个数n也称 为图G的阶 ⚫ |A|=m表示有向图G中弧的个数为m ⚫ 任一顶点相关联（连接）的边的数目称为该顶 点的次数
2连通图 def3:在有向图G中,一个点和边的交替序列 V ev称为G中从点V到V的一条 路,记为A,其中V为此路A的起点,V为路A 的终点;若路A的起点与终点重合,则称A为回 路;又若G中点V与V间存在一条路,则称点 V;与V是连通的;若G中任何二点都是连通的, 则称G为连通图,或图G为连通的。在无向图 中有对应的概念。 有向图 无向图 路链 回路 圈
8 2 连通图 def 3：在有向图G中,一个点和边的交替序列 {Vi eij Vj…Vk ekl Vl } 称为G中从点Vi到Vl的一条 路，记为A，其中Vi为此路A的起点，Vj为路A 的终点；若路A的起点与终点重合,则称A为回 路；又若G中点Vi与Vj间存在一条路，则称点 Vi与Vj是连通的；若G中任何二点都是连通的， 则称G为连通图，或图G为连通的。在无向图 中有对应的概念。 有向图 路 回路 无向图 链 圈
3子图 def4:设有两个图:G1=(V1,E),G2=(V2 E2)若有 VICVEICE,则称G1为G2的子图, 记作G∈G2;若有Ⅴ=V2而E∈E2,则称图 G1=(V1,E1)是图G2=(V2,E2)的生成子图(支撑 子图)
9 3 子图 def 4：设有两个图：G1= (V1 , E1 ) ，G2= (V2 , E2 )若有 ，则称G1为G2的子图， 记作 ；若有 V1=V2而 ,则称图 G1= (V1 , E1 ) 是图G2= (V2 , E2 )的生成子图（支撑 子图）。 V1 V2 E1 E2 G1 G2 E1 E2
●例:下示图G1是图G的子图,图G2.是图G的生 成子图。 (a)图G (b)图G1 (c)图G2
10 ⚫ 例：下示图G1是图G的子图，图G2是图G的生 成子图。 V1 V3 V2 V4 V1 V2 V4 V1 V3 V2 V4 （a）图G （b）图G1 （c）图G2
4赋权图(加权图)与网路 def5:设G是一个图(或有向图),若对G的每 条边(或弧)e;都赋予一实数oi,称其为该 边(弧)的权,则G连同其他弧上的权集合称 为一个赋权图,记作G=(V,E,W)或G=(V,A W),此中W={o,O1为对应边(弧)的权 若G=(V,E,W)(或(V,A,W)为赋权图,且 在G的V中指定一个发点(常记为)和一个 收点(记为v1),其余点称为中间点,则称这 样指定了发点与收点的赋权图G为网络
11 4 赋权图（加权图）与网路 def 5：设G是一个图（或有向图），若对G的每 一条边（或弧）eij都赋予一实数ωij，称其为该 边（弧）的权，则G连同其他弧上的权集合称 为一个赋权图，记作G= (V, E, W) 或G= (V, A, W)，此中W={ωij}，ωij为对应边（弧）eij的权。 若G= (V, E, W) （或(V, A, W)）为赋权图，且 在G的V中指定一个发点（常记为Vs）和一个 收点（记为Vt），其余点称为中间点，则称这 样指定了发点与收点的赋权图G为网络