资源描述：
《第七章 图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第七章图与网络分析 图与网络分析（GraphTheoryandNetworkAnalysis），是近几十年来运筹学领域中发展迅速、而且十分灵活的一个分支。由于它对实际问题的描述，具有直观性，故广泛应用与物理学、化学、信息论、控制论、计算机科学、社会科学、以及现代经济管理科学等许多科学领域。图与网络分析的内容十分丰富。本章只介绍图与网络的基本概念以及图论在路径问题、网络流问题等领域中应用。重点讲明方法的物理概念、基本概念及计算步骤。 §1图与网络的基本概念 定义1图是由表示具体事物的点（顶点）的集合V=｛v1,v2,…，vn｝和表示事物之间关系边
2、的集合E=｛e1,e2,…，em｝所组成，且E中元素ei是由V中的无序元素对[vi,vj]表示，即ei=[vi,vj]，记为G=（V，E），并称这类图为无向图。 例如，图7-1中，有８条边，６个顶点，即V=｛v1,v2,…,v6｝;E=｛e1,e2,…,e8｝其中e1=[v1,v2]=[v2,v1];e7=[v2,v5]=[v5,v2];e2=[v2,v3]=[v3,v2];e6=[v4,v5]=[v5,v4].定义２ （１）顶点数和边数：图G(Ｖ,Ｅ)中，Ｖ中元素的个数称为图Ｇ的顶点数，记作p(G)或简记为p；Ｅ中元素的个数称做图Ｇ的边数，记
3、为q(G)，或简记q。（２）端点和关联边：若ei=[vi,vj]∈Ｅ，则称点vi,vj是边ei的端点，边ei是点vi和vj的关联边。（３）相邻点和相邻边：同一条边的两个端点称为相邻点，简称邻点；有公共端点的两条边称为相邻边，简称邻边。（４）多重边与环：具有相同端点的边称为多重边或平行边；两个端点落在一个顶点的边称为环。（５）多重图和简单图：含有多重边的图称为多重图；无环也无多重边的图称为简单图。（６）次：以vi为端点的边的条数称为点vi的次，记作d(vi)。（７）悬挂点和悬挂边：次为１的点称为悬挂点：与悬挂点相联的边称为悬挂边。（８）孤立点：次
4、为零的点称为孤立点。（９）奇点与偶点：次为奇数的点称为奇点；次为偶数的点称为偶点。 例如，图7-1中,p(G)=8,q(G)=6;e3=[v4,v3]，v4与v3是e3的端点，e3是v4和v3的关联边；v2与v5是邻点，e3与e2是邻边；e7与e8是多重边，e4是一个环；图９.５是一个多重图；v1是悬挂点，e１是悬挂边；v６是孤立点；v２是奇点，v３是偶点。 定理１ 图Ｇ＝（Ｖ，Ｅ）中，所有点的次之和是边数的两倍。即。定理１是显然的，因为在计算各点的次时，每条边都计算两次，于是图Ｇ中全部顶点的次之和就是边数的２倍。 定理２ 任一图Ｇ＝（Ｖ，Ｅ）
5、种，奇点的个数为偶数。证 设Ｖ１，Ｖ２分别是Ｇ中奇点和偶点的集合，由定理１可知 （7.１）因为是偶数，而也是偶数，故也必是偶数，由于偶数个奇数才能导致偶数，所以有奇点的个数必须为偶数。 定义３ （１）链在一个图Ｇ＝（Ｖ，Ｅ）中，一个由点与边构成的交错序列（vi1,ei1,vi2,ei2,…，vik-1,eik-1,vik）如果满足eit=[eit,eit+1](t=1,2,…,k-1),则称此序列为一条联结vil,eik,的链，记为μ=（vi1,vi2,…，vik）,则称点vi２,vi3,…,vik-1为链的中间点。（２）闭链与开
6、链：若链μ中vi1＝vik即始点与终点重合，则称此链为闭链（圈）。否则称之为开链。（３）简单链与初等链：若链μ中，若含的边数均不相同，则称之为简单链；若链μ中，顶点vi1,vi2,…，vik都不相同，则称此链为初等链。除非特别交代，以后我们讨论的均指初等链。 例如，图7-1中，μ1=(v2,e2,v3,e3,v4,e6,v5)是一条链，由于链μ1里所含的边和点均不相同，故是一条初等链；而μ2=(v1,e1,v2,e2,v3,e3,v4,e5,v2,e1,v1)是一条闭链。 定义４（１）回路：一条闭的链称为回路。（２）通路：一条开的初等链称为通路
7、。（３）简单链回路和初等回路；若回路中的边都不相同，则称为简单回路；若回路中的边和顶点都互不相同，则称为初等回路或圈。 定义５ 一个图Ｇ的任意两顶点之间，如果至少有一条通路将它们连接起来，则这个图Ｇ就称为连通图，否则称为不连通图。例如，图7-1中，v1与v6没有一条通路把它们连接起来，故此图是不连通图。本章以后讨论的图，除特别声明外，都是指连通图。 定义６ （１）子图：设Ｇ1＝｛Ｖ1，Ｅ1｝Ｇ2＝｛Ｖ2，Ｅ2｝如果Ｖ1V2，又Ｅ1E2,则称Ｇ1为G2的子图。（２）真子集：若V1V2,E1E2即G1中不包含G2中所有的顶点和边，则称G1是G2的真
8、子图。（３）部分图：若V1=V2,E1E2,即Ｇ1中不包含G2中所有的边，则称G1是G2的一个部分图。（４）支撑子图：若G1是G2的部分图，且G1是连
