图与网络模型及方法

图与网络模型及方法图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图绪论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷n2n+2CH的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈绪论近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。绪论图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题这个图是连通的，且每个点都与偶数线相关联绪论图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。图------由若干个点和连接这些点的连线所组成的图形vi——图中的点，称为顶点（代表具体事物，研究对象。ei——图中的连线，称为边（对象之间的联系）m(G)=|E|——G的边数，简记为mn(G)=|V|——G的顶点数，简记为n一.图的概念记V={vi}——点的集合，E={ei}——边的集合G={V，E}G——一个图1v2v3v4v5v1e2e3e4e5e6em=6,n=5},{jikvve图的基本概念有向图无向图——边e=(vi,vj)有方向vi为始点，vj为终点——边e=(vi,vj)无方向，此时(vi,vj)=(vj,vi)e4=(v3，v4）=(v4，v3）e4=(v3，v4)≠(v4，v3）e5=(v3，v4）=(v4，v3）此时(vi,vj)≠(vj,vi)1v2v3v4v1e2e3e4e5e6e1v2v3v4v1e2e3e4e5e6ee5=(v4，v3)≠(v3，v4)图有向图无向图二.常用名词：1v2v3v4v1e2e3e4e5e6e1、端点和关联边：的关联边和点是的端点，边是边、则称点若jikkjijikvveevvEvve,},{2、相邻点和相邻边：边边称为相邻边，简称邻端点落在同一个顶点的相邻点，简称邻点，一条边的两个端点称为3、多重边与环：点的边称为环。两个端点落在同一个顶多重边或平行边；具有相同端点的边称为4、多重图和简单图：无环也无多重边的图称为简单图。含有多重边的图称为多重图；5、次：)(iiivdvv的次，点为端点的边的条数称为以点6、悬挂点和悬挂边：次为1的点称为悬挂点，与悬挂点相联的边称为悬挂边。7、孤立点：8、奇点与偶点：的点称为孤立点次为0点，次为偶数的点称为偶次为奇数的点称为奇点1v2v3v4v2e3e4e5e1e5v6v6e,3)(1vd为悬挂点，、62vv为悬挂边，、52ee为孤立点，5v4)(3vd,1)(2vd,3)(4vd,0)(5vd,1)(6vd为奇点，、、、6421vvvv为偶点、35vv)(ivd12，G的边数m=6mvdi2)(即性质1：在图G=(V,E)中，所有点的次之和是边数m的两倍。证明：由于每条边均与两个顶点关联，因此在计算顶点的次时每条边都计算了两遍，所以顶点次数的总和等于边数的二倍。三.次（度）的性质性质2：在任何图G=(V,E)中，奇点的个数为偶数证明：设V1，V2分别是图G中奇点和偶点的集合，则V1∪V2=V,V1∩V2=Φ,有性质1，，因为V2是偶点的集合，d(vi)(i∈V2)均为偶数，所以mvdvdvdViiViiVii2)()()(21为偶数所以2)(Viivd为偶数1)(Viivd是奇点的集合而1,V均为奇数))((,1Vivdi只有偶数个奇数相加才能得到偶数，所以V1中的点，即奇点的个数为偶数。四.链、路、连通图1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1.链：对于无向图G=(V，E)，若图G中有一个点与边的交替序列μ={vi0,ei1,vi1,ei2,,vik-1,eik,vik}，且eit=(vit-1,vit)(t=1,2,…,k),则称该交替序列μ为连结vi0和vik的一条链。简单链：μ中只有重复的点而无重复边者为简单链。初等链：μ中没有重复的点和重复边者为初等链。圈：无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中只有重复点而无重复边者为简单圈，既（除起点、终点重复外）无重复点也无重复边者为初等圈},,,,{48176vevev不是链},,,,{17556vevev初等链},,,,,,,,,,{18433229445vevevevevev简单链1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e为一个圈},,,,,,,,,,,,{5443322948175vevevevevevev为一个圈},,,,,,,,{544816655vevevevev（简单圈）（初等圈）2路：在有向图D=(V，A)中，若有从vi0到vik不考虑方向的链，且各边方向一致，则称之为从vi0到vik的一条路。对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈．此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1v2v3v4v2e3e4e1e5v6e3连通图：一个图中任意两点间至少有一条链(或路)相连的图。连通图非连通图五．网络在实际问题中，往往只用图来描述所研究对象之间的关系还不够，与图联系在—起的，通常还有与点或边有关的某些数量指标，通常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种带有某种数量指标的图称为网络(赋权图)。如公路交通图：vi表示城市,ei表示公路w(ei)表示公路ei的长度如w(e2)=50表示城市v2与城市v3之间的距离是50千米1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e六.完全图、偶图1．完全图：一个简单图，若任意两个顶点之间均有一条边相连，则称这样的图为完全图。对于完全图，由于每个顶点与所有其余顶点都有一条边相连，所以在有n个顶点的完全图中，各个顶点的次均为（n-1）。2.偶图：若图G的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中的任意两个顶点均不相邻，称这样的图为偶图，也称为二部图。若偶图的顶点集合V1，V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。v2v3v4v5v2v3v4v5••••••••••v1v1完全图(完全)偶图定理一个图为偶图的充分必要条件该图无奇圈七.子图、部分图对于图G1={V1,E1}和图G2={V2,E2},若有，称G1是G2的一个子图。若有，称G1是G2的一个部分图（生成子图）。2121EEVV和2121EEVV和*部分图也是子图，但子图不一定是部分图。生成子图七.子图、部分图*部分图也是子图，但子图不一定是部分图。生成子图2121EEVV和2121EEVV和对于图G1={V1,E1}和图G2={V2,E2},若有，称G1是G2的一个子图。若有，称G1是G2的一个部分图（生成子图）。八.前向弧与后向弧设μ是一条从vs到vt的链，则链μ上与链的方向一致的弧称为前向弧，记这些弧为μ+；链μ上与链的方向相反的弧称为后向弧，记这些弧为μ-。•••••••vsv1v2v3v4v5vt前向弧与后向弧子图设G1=[V1,E1],G2=[V2,E2]子图定义：如果V2V1,E2E1称G2是G1的子图；真子图：如果V2V1,E2E1称G2是G1的真子图；部分图：如果V2=V1,E2E1称G2是G1的部分图；导出子图：如果V2V1,E2={[vi,vj]∣vi,vjV2}，称G2是G1中由V2导出的导出子图。九、图的矩阵表示用矩阵表示图对研究图的性质及应用常常是比较方便的．定义：网络(赋权图)G＝(V，E)，其边(vi,vj)有权ωij,构造矩阵A=(aij)n×n,其中：　　　其它　　0E)v,v(ajiijij称矩阵A为网络G的权矩阵。例、写出下图的权矩阵v1v2v3v4•••••v57654249380650760844580320430974290A定义：对于图G＝(V，E)，|V|=n,构造一个矩阵A=(aij)n×n,其中：　　　其它　　0E)v,v(1ajiij称矩阵A为图G的邻接矩阵。例、写出下图的邻接矩阵v1v3v5••••••v2v4v6当G为无向图时，邻接矩阵为对称矩阵010000101010100010010010000100000110　　A654321vvvvvv654321vvvvvv最短轨道问题给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)—直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u0,v0间的具最小权的轨。这条轨叫做u0,v0间的最短路，它的权叫做u0,v0间的距离，亦记作d(u0,v0)最短轨道问题求法---Dijkstra算法基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。最短轨道问题求法---Dijkstra算法定义：连通且不含圈的无向图称为树。记作T(V，E)二、树树可以有很多等价的定义,以下定理中的各命题都体现树的特征.定理设G={V,E}是一无向图，|V|=n，|E|=m。则以下命题是等价的.(1)G是树;(2)G的每对顶点之间有唯一的一条路;(3)G连通且m=n-1;(4)G无圈且m=n-1;(5)G无圈,在G的任一对顶点上加一新边后产生圈;(6)G连通，但删去任何一边后不再连通。定理：无向图G有生成树当且仅当G连通。证明:必要性显然,只证充分性。若G无圈，则G本身就是G的生成树。若G有圈C，则在G中删去C的一条边，所得的图是连通的，继续这个过程，直到所得的图T无圈为止，则T就是G的一棵生成树。定义：若图G的生成子图是一棵树，则称该树为G的生成树(支撑树)。或简称为图G的树(b)为(a)图的生成树最小生成树的求法：避圈法与破圈法定义：树的各条边称为树枝。一般图G的生成树有多个，称其中树枝总长度最小的生成树为最小树。避圈法：在图G中，每步选出一条边e，使它与已选边不构成圈，且e是未选边中长度最小的边，直到选够n-1边为止。•••••••••v1v2v3v8v7v6v5v4v04112131444523552•••••••••v1v2v3v8v7v6v5v4v011211232•••••••••v1v2v3v8v7v6v5v4v04112131444523552•••••••••v1v2v3v8v7v6v5v4v011211232破圈法：从网络图N中任取一回路，去掉该回路中权数最大的一条边，得一子网