图与网络模型及方法图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图绪论绪论绪论哥尼斯堡七桥问题绪论图------由若干个点和连接这些点的连线所组成的图形有向图二.常用名词：5、次：性质1：在图G=(V,E)中，所有点的次之和是边数m的两倍。四.链、路、连通图（简单圈）3连通图：一个图中任意两点间至少有一条链(或路)相连的图。如公路交通图：2.偶图：若图G的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中的任意两个顶点均不相邻，称这样的图为偶图，也称为二部图。若偶图的顶点集合V1，V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。七.子图、部分图对于图G1={V1,E1}和图G2={V2,E2},若有，称G1是G2的一个子图。若有，称G1是G2的一个部分图（生成子图）。七.子图、部分图八.前向弧与后向弧设μ是一条从vs到vt的链，则链μ上与链的方向一致的弧称为前向弧，记这些弧为μ+；链μ上与链的方向相反的弧称为后向弧，记这些弧为μ-。子图设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)，|V|=n,构造一个矩阵A=(aij)n×n,其中：最短轨道问题最短轨道问题求法---Dijkstra算法最短轨道问题求法---Dijkstra算法定义：连通且不含圈的无向图称为树。记作T(V，E)定理：无向图G有生成树当且仅当G连通。证明:必要性显然,只证充分性。若G无圈，则G本身就是G的生成树。若G有圈C，则在G中删去C的一条边，所得的图是连通的，继续这个过程，直到所得的图T无圈为止，则T就是G的一棵生成树。最小生成树的求法：避圈法与破圈法•筑路选线问题prim算法构造最小生成树Kruskal算法构造最小生成树可行遍问题Euler回路的Fleury算法可行遍问题的应用若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：多邮递员问题旅行商（TSP）问题改良圈算法。旅行商问题的数学表达式对集1957年，贝尔热(Berge)得到最大对集的充要条件：定理2M是图G中的最大对集当且仅当G中无M可增广轨。1935年，霍尔(Hall)得到下面的许配定理：定理3G为二分图，X与Y是顶点集的划分，G中存在把X中顶点皆许配的对集的充要条件是，，∀S⊂X，则|N(S)|≥|S|，其中N(S)是S中顶点的邻集。推论1：若G是k次（k>0)正则2分图，则G有完美对集。所谓k次正则图，即每顶点皆k度的图。由此推论得出下面的婚配定理：定理4每个姑娘都结识k(k≥1)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。人员分派问题人员分派问题匈牙利算法最优分派问题定义若映射l:V(G)→R，满足∀x∈X,y∈Y，l(x)+l(y)≥w(x,y)，则称l是二分图G的可行顶点标号。令El={xy|xy∈E(G),l(x)+l(y)=w(xy)}，称以lE为边集的G的生成子图为相等子图，记作Gl。可行顶点标号是存在的。例如Kuhn-Munkres算法最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以便用这个模型．如设备更新、管道铺设、线路安排、厂区布局等。最短路问题的一般提法：设G={V，E}为连通图，图中各边(vi,vj)有权lij(lij=∞表示vi,vj间无边)。vs,vt为图中任意两点，求一条路μ，使它是从vs到vt的所有路中总权最小的路。即(2)使用条件——网络中所有的弧(边)权均非负，即：可用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号，给vi点一个P标号时，表示从vs到点vi的最短路权,vi点的标号不再改变。给vi点一个T标号时．表示从vs到点vi的估计最短路权的上界，是一种临时标号．凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n一1步就可以得到从始点到终点的最短路。计算步骤：例、用Dijksta