资源描述：
《第七章图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第七章图与网络分析*图,J网络分析(GraphTheoryandNetworkAnalysis),是近儿十年来运筹学领域中发展迅速、而且十分灵活的一个分支。由于它对实际问题的描述，具冇直观性，故广泛应用与物理学、化学、信息论、控制论、计算机科学、社会科学、以及现代经济管理科学等许多科学领域。图与网络分析的内容十分丰富。木章只介绍图与网络的基本概念以及图论在路径问题、网络流问题等领域屮应用。重点讲明方法的物理概念、基本概念及计算步骤。§1图与网络的基本概念定义1图是由表示具体事物的点(顶点)的集合V={V],V2,…，V]J和表示事物之间关系边的集合E=(
2、ei,e2,-,ej所组成，且E中元索ei是由V屮的无序元素对[Vj]表示，即ei=[vi,vj],记为G=(V,E),并称这类图为无向图。例如，图7・1中，有8条边，6个顶点，即V={vhv2,---,v6};E={ci。,…,显其中ei=[vi,v2]=[v2,vi];e?=[v2,v5]=[v5,v2];e2=[v2,v3]=[v3,v2];e6=[v4,v5]=[v5,v4].图7-1定义2(1)顶点数和边数：图G(V,E)中，V中元素的个数称为图G的顶点数，记作p(G)或简记为p；E中元素的个数称做图G的边数，记为q(G),或简记q。(2)端点
3、和关联边：若牛山划丘E,贝lj称点Vj,比是边q的端点，边q是点Vj和vj的关联边。(3)相邻点和相邻边：同一条边的两个端点称为相邻点，简称邻点；有公共端点的两条边称为相邻边，简称邻边。(4)多重边与环：具有相同端点的边称为多重边或平行边；两个端点落在一个顶点的边称为环。(5)多重图和简单图：含有多重边的图称为多重图；无环也无多重边的图称为简单图。(6)次：以w为端点的边的条数称为点旳的次，记作d(Vi)o(7)悬挂点和悬挂边：次为1的点称为悬挂点：与悬挂点和联的边称为悬挂边」(8)孤立点：次为零的点称为孤立点。(9)奇点与偶点：次为奇数的点称为奇点：次
4、为偶数的点称为。例如，图7-1中,p(G)=8,q(G)=6;e3=[v4,v3],v4与V3是e3的端点,e3是v4和V3的关联边;V2与V5是邻点,s与勺是邻边；引与e8是多重边,e4是一个环；图9.5是一个多重图;vj是悬挂点，C1是悬挂边；VG是孤立点；V2是奇点，V3是偶点。令定理1图G=(V,E)中，所有点的次Z和是边数的两倍。即■“O定理1是显然的，因为在计算各点的次时，每条边都计算两次，于是图G中全部顶点的次Z和就是边数的2倍。令定理2任一图G=(V,E)种，奇点的个数为偶数。证设V】，V2分别是G中奇点和偶点的集合，由定理1可知迟＜#厲
5、”2?⑷=2?⑷=匀(7.1)另/时迟*山)因为是偶数，而吋也是偶数，故g也必是偶数，由于偶数个奇数才能导致偶数，所以冇奇点的个数必须为偶数。篠定义3(1)链在一个图G=(V,E)中，一个由点与边构成的交错序列(Vi】,S,Vi2,Ci2,…,Vik-i,eikj,Vik)如果满足ei(=[eibeil+i](t=l,2,--,k-l),则称此序列为一条联结vibeik,的链，记为U=(Vii,Vi2,…，Vik),则称点Vi2,Vi3,…，Vjk_i为链的中间点。(2)闭链与开链：若链卩中*尸Vik即始点与终点重合，则称此链为闭链(圈)。否则称Z为开链
6、。(3)简单链与初等链：若链口中，若含的边数均不相同，则称Z为简单链；若链》中,顶点Vi,2,・・・，和都不相同，则称此链为初等链。除非特别交代，以后我们讨论的均指初等链。例如，图7・1中,u)=(v2,e2,v3,e3,v4,e6,v5)是一条链，由于链》丨里所含的边和点均不相同,故是一条初等链；而u2=(vi,ebv2,e2,v3,e3,v4,e5,v2,e1,v1)是一条闭链。定义4(1)回路：一•条闭的链称为回路。(2)通路：一条开的初等链称为通路。(3)简单链回路和初等回路；若回路中的边都不相同，则称为简单回路；若回路中的边和顶点都互不相同，则
7、称为初等回路或圈。樂定义5—个图G的任意两顶点Z间，如果至少冇一条通路将它们连接起来，则这个图G就称为连通图，否则称为不连通图。例如，图7-1中，V
8、与V6没有一条通路把它们连接起来，故此图是不连通图。本章以示讨论的图，除特别声明外，都是指连通图。義定义6-(1)子图：设G
9、={V],EJG2={V2,E2}如果V]V2，又E】E2,则称6为G2的子图。u(2)真子集：若V)V2,E]E2即G
10、中不包含G2中所有的顶点和边，则称G)是G2的真子图。(2)部分图：若Vi=V2,EiE2,即G]中不包含G2中所有的边,则称Gi是G2的一个部分图。(4)支撑子
11、图：若G是G?的部分图，且G是连通图，则称G是G2的支撑子图。(3)生成子图：若
