第6章 图与网络分析

第6章 图与网络分析 §6.1 图的基本概念

§6.2 树图和图的最小部分树 §6.3 最短路问题

§6.4 网络的最大流 §6.5 最小费用流

第1页

引 言图论是运筹学的一个经典和重要的分支，它起源于欧拉 (Euler)对七桥问题的抽象和论证。 1936年，匈牙利数学家柯尼希(Kö nig)出版了图论的 第一部专著《有限图与无限图理论》,竖立了图论发展的第 一座里程碑。 此后，图论进入发展与突破的快车道，所研究的问题涉 及经济管理、工业工程、交通运输、计算机科学与信息技术、 通讯与网络技术等诸多领域。近几十年来，由于计算机技术 和科学的飞速发展，大大地促进了图论研究和应用，图论的 理论和方法已经渗透到物理、化学、通讯科学、建筑学、生 物遗传学、心理学、经济学、社会学等学科中。

图论研究点与边的连接关系、一笔画问题、通路、最短 路、最大流量。而诸如“四色问题”,“旅行商问题”等世 界著名的难题都属于图论的研究范畴。第2页

§6.1 图的基本概念运筹学中研究的图是生活中各类图的抽象概括, 它表明一些研究对象和这些对象之间的相互关系。 用点表示研究对象，用边表示这些对象之间的联 系，则G图可定义为点和边的集合，记为

G {V , E }式中V是点的集合，E是边的集合。

第3页

基本概念网络图N:若给图中的点和边赋以具体的含义和权。 顶点(节点):记为v 边:记为e e1=[v1,v1] e2=[v1,v2] 或 e2=[v2,v1] 端点,关联边,相邻：若边e=[vi,vj],称vi和vj是边e的端点; 边e为点vi或vj的关联边；

若点vi、vj与同一条边关联，称点vi和vj 相邻；e1 e2 v2 v1 e5

若边ei和ej具有共同的端点，称边ei和ej相邻；e3 v3 e4

环,多重边,简单图： 若边e的两个端点相重，称该边为环;v4

e6

若两顶点之间至少有两条边，称为具有多重边;

无环、无多重边的图称作简单图。

第4页

次,奇点,偶点，孤立点 与点v相关联的边的数目称为点v的次(度或线度),记作d(v)

次为奇(偶)数的点称作奇(偶)点； 次为0的点称作孤立点； 链,圈,路，回路，连通图 点和边的交错序列μ={v0, e1, v1,…,ek ,vk}, 若其中各边e1, e2,…,ek互不相同, 且任意vt-1和vt (2≤t≤k)均相邻, 称μ为链.若链中所有的顶点也互不相同,这样的链称为路.e1 e2 v2 v1 e5 e6 v5

e3

v3 e4v4

起点和终点重合的链称为圈. 起点和终点重合的路称为回路. 若图中的每一对顶点之间至少存在一条链, 称这 样的图为连通图, 否则称该图是不连通的.

第5页

完全图，偶图

任意两点之间均有边相连的简单图, 称为完全图.

Kn2 | E | Cn

K2

K3

K4

若图的顶点能分成两个互不相交的非空集合V1和 V2,使在同一集合中任意两个顶点均不

相邻称, 这样的 图为偶图(二分图). 若偶图的顶点集合V1和V2之间的每对不同顶点都 有边相连，称 这样的图为完全偶图. Km,n

K3, 2

m n

第6页

子图，部分图

设G=(V,E)是一个图, 并设V V 和E E , 如果对E 中任意的一条边eij [vi , v j ], 都有 vi V , v j V , 则称G [V , E ] 是G的一个子图. 若V V , E E , 则称 G 是G的一个部分图.

注意： 部分图是子图，但子图不一定是部分图.e1 e2 v2 v1 e5 e3 v3 e4

e2v4 v2

v1

v3

e5

e2 v2

v1 e6

v3 e4 v4 e2 v2 v1 e5

e6

子图

部分图

非子图第7页

树图(简称树): 无圈的连通图，记作T(V, E) G的部分树(或支撑树): 若G1是G的部分图又是树图. 树枝: 树图的各条边. 假定图的各边均有权重. 最小部分树(或最小支撑树，minimum spanning tree): 图中树枝总长最小的部分树.

第8页

§6.2.1树图的性质

悬挂点

悬挂边

性质1 任何树图中必存在次为1的点. 证明：用反证法. 假设树图中不存在次为1的点.又连通图中不存在孤立点，故树图中所有顶点的次≥2. 不妨设d(v1)=2, 既v1有两条关联边， 设关联边的其他两个端点为v2 , v3,而d(v2 )≥2, d(v3) ≥2, 又可知与v2 , v3关联的边的其他端点v4 , v5,同样d(v4 )≥2, d(v5) ≥2,可继续一直往下推。 而图的顶点的总数是有限的，故最后 必然回到前面的某一顶点，于是在图中出 现了圈，这与树的定义产生了矛盾.v2 v4

v5v1 v3

第9页

性质2 具有n个顶点的树图的边树恰好为n-1条. 证明：用归纳法.当n=2和n=3时, 上述性质显然成立. 假设当n=k-1时, 上述性质也成立. 当n=k时, 因树中至少有一个悬挂点，将此悬挂点及 关联的悬挂边从树图中拿掉. 根据前述，剩下的图仍为树图，故此时图中有k-1个 点，据假定应有k-2条边. 再把拿掉的悬挂点及悬挂边放回去，说明树图中含 有k个点时，边数为k-1条.

第10页

性质3 任何具有n个顶点、n-1条边的连通图是树图. 证明： 用反证法. 假设有n个顶点、n-1条边的连通图不是树图.此时这个图中含有圈， 则从圈中拿掉任意一条边, 图仍连通. 若仍有圈， 则继续从圈中拿掉任意一条边, 这样继续下去. 一直到图中没有任何圈为止. 由于剩下的图仍连通且无圈，故仍为树. 但此时图中有n个顶点, 而边数却少于n-1条, 与性质2矛盾.

说明：(1) 树是无圈连通图中边数最多的, 在树图中只要任意再加上一条边，必会出现圈.(2) 树图的任意两点之间有一条且仅有一条唯一通路.

第11页

§6.2.2 图的最小部分树定 …… 此处隐藏：2772字，全部文档内容请下载后查看。喜欢就下载吧 ……