资源描述：
《图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第六章网络优化我们在工农业生产、交通运输和邮电通信等部门中经常看到许多的网络，如公路网、铁路网、河道网、灌溉网、管道网、线路网等等。还有许多问题，表而上看去，和网络无联系,实则可用网络表示Z,如牛产计划、资本预算、设备更新、项目排程等问题便是如此。对网络的研究当然是希望解决管理中的一些优化问题。基本的网络最优化问题有四个,即最短路问题，最小支撑树问题，最大流问题，最小费用流问题。网络优化问题屮有许多问题的数学模型实际上都是线性规划问题。但若川线性规划的方法去求解，就非常麻烦，而根据这些问题的特点，采用网络分析的方法去解决倒是非常简便冇
2、效的。§6.1图与网络的基本概念从前面所举的各个网络实例，可以看到具中一些共性的东西，即每个网络都至少包含两种类型元素：点和线。例如铁路网中的火乍站和铁路；电话网中的电话局与线路等火车站<®火车站铁路我们把山点和连接点的线所组成的图形叫做图，并称这些点为图的顶点或图的点，这些线叫做图的边。定义1图是由表示具体事物的点(顶点)的集合7二山川2,…，匕｝和表示事物Z间关系边的集合E=｛弓,勺…,en｝所组成，且E中元素©是由/中的无序元素对也,V]表示,即弓二也,V」。记G=(7,E),并称这类图为无向图。例6个顶点和8条边的图：7二｛片
3、,卩2，・・・,比｝，E二｛弓《2…，纟8)其中ei=[vbV2]=[V2,V{],^7=[v5,V2]=[v2,V5],幺2=["3,V2]=[v2,v3],^6=[V4,V5]=[V5,V4]o定义2(l)顶点数和边：图G=(y,E)中，7中元素的个数称为G的顶点数，记作p(G)；E中元索的个数称为图的边数，记作g(G)。(2)端点和关连边：若=[vz,v/]g£,则称比，vj是边©的端点，边勺是点岭和vj的关连边。（3）相邻点和相邻边：同一条边的两个端点称为相邻点，简称为邻点；冇公共端点的两条边称为相邻边。（4）多重边与环：具有
4、相同端点的边称为多重边，如勺与內；两个端点落在一个顶点的边称为坏，如幺4。（5）多重图和简单图：含有多重边的图称作多重图，如图1中的图；无环也无多重边的图称为简单图。简单图的例了见课木P184（6）完全图与二分图：见课木P185（7）次：以刃为端点的边的条数称作点刃的次，记作d（vi）。（8）悬挂点与悬挂边：次为1的点为悬挂点，如申；与悬挂点相连的边称为悬挂边，如©。（9）孤立点：次为0的点，如％。（10）奇点与偶点：次为奇数的点称为奇点，如厂为奇点，因为4v2）=5；次为偶数的点称为偶点，如V3为偶点。定理1图G=（K,E）中，所有
5、点的次Z和是边数的2倍，即工dej=2q（G）v^V证明因为在计算各点的次时，每一条边都计算了2次，于是图G屮的全部顶点的次之和是边数的2倍。定理2任一图G=（r,£）中，奇点的个数为偶数。证明设人，血分别是G中奇点和偶点的集合。由定理1有工〃（％）+工〃（匕）=工力⑴）二2g（G）因为工〃⑴）和2g（G）是偶数,故工d（%）必是偶数。由于偶数个奇数才能导致偶数，从V申耳码而奇点的个数必须为偶数定义3（1）链：在一个图G=（7,E）中，一个由点和边组成的交错序列“二佗，勺必，…，以，印，％｝称为G中由Vj,V；的链，或称为路，记为（2
6、）圈：若在链“=｛%,%｝中，冇沪刃，即始点和终点重合，则称链“为圈，也称为闭链（闭路）或环；否则就称为开链。（3）简单链和初等链：若链“中的边均互不相同，则称链“为简单链；若链“屮的点互不相同，则称链〃为初等链。今后除非特别交代，否则我们仅讨论初等链。例如,在图1中，=｛v2,e2,v3,e3,v4,e6,v5｝是一条链，且还是初等链;而链“2=｛气,弓川2，勺，叫,勺，比(5,叫，弓，V】｝是圈。定义4(1)回路：一条闭的链。(2)通路：一条开的初等链。(3)简单回路：冋路屮的边都互不和同。(4)初级回路：顶点都不相同的回路。定义
7、5若一个图G的任意两个顶点Z间至少冇一条通路将它们连接起來，则称G为连通图，否则称为不连通图。例如，图1中的图就是不连通的，因刃与心之间没有一条通路将它们连接起来。而是连通图定义6(1)子图：设G=(K,E)是图，若«匸y,E、uE,且厲,目)是图，则称图G]=(汗,坊)是G的子图。(2)支撑子图：若G严馅，厶)是G=(K,£)的了图，月”=7(即点相同)，则称G为G的支撑子图。例如，在下图中，图Go是一个图，G]和G2都是Go的子图，且G2还是Go的支撑子图。”2幺2V4GiV4定义7设图G=（r,E）中，对于任意一条边ewE,若相
8、应地都有一个权值w（w）,则称G为赋权图，w（£）称为边幺的权。例如下图2就是一赋权图^l=[vbv2]^旳由此可见，赋权图不仅指出各点Z间的邻接关系，而R也表示各点Z间的数量关系，所以赋权图在图的理论及其应用方面有着重
