数学建模暑期培训图论问题的起源七桥问题的分析欧拉的结论图的作用图的广泛应用基本的网络优化问题例如，在1978年，财政部的税务分析部门在对卡特尔税制改革做评估的过程中，就有一个100000个约束以上，25000000个变量的问题，若用普通的线性规划求解，预计要花7个月的时间。他们利用网络分析的方法，将其分解成6个子问题，利用特殊的网络计算机程序，花了大约7个小时问题就得到了解决。目的图论的基本概念定义定义前往顶点的次数例在一次聚会中，认识奇数个人的人数一定是偶数。子图关联矩阵邻接矩阵前往最短路问题及其算法基本概念前往若P不含y，则eM。图的应用是非常广泛的，在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如河道网、灌溉网、管道网、公路网、铁路网、线网、计算机通讯网、输电线网等等。若u=x，显然有yT。地属于M1和M2且每个圈是偶圈。有序三元组G=(V，E，)称为一个图，假设：对于顶点v6，同样与v1，v2，v3，v4中至少3个顶点相邻，即在v2和v4中至少有一个顶点与v6相邻。Deg(x)≤2，所以≤2，故H的每个连通分支或者是一条路2)与图中每一顶点相连的边必须是偶数。T=T{y}，转(4)。一:(1)边在M1和M2中交错出现的偶圈。分图，映射l:V(G)R，满足对G的每条边e={x，y}，均有l(x)+l(y)(x，y)，其中(x，y)表示边{x，y}的权，则称l为G的可行顶标。最短路问题及其算法由定理3可知，G有饱和V1的匹配M，再据V1=V2和推据匹配的定义，H的任意两条邻接边一定分选址问题--重心问题而根据这些问题的特点，采用网络分析的方法去求解可能会非常有效。定理3(Hall定理，1935)设G是有二部划分(V1，V2)的二分图，算法步骤：TOMATLAB(road1)1每对顶点之间的最短路算法的基本思想算法原理——求距离矩阵的方法算法原理——求路径矩阵的方法i算法步骤TOMATLAB(road2(floyd))一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题前往选址问题--中心问题S(v1)=10，S(v2)=7，S(v3)=6，S(v4)=10，S(v5)=7，S(v6)=7，S(v7)=8.5选址问题--重心问题匹配阐明:(1)完美匹配是最大匹配，反之未然;(2)匹配的定义与边的方向无关，故匹配是针对无向图而言。(3)图G的边不交匹配的最小数目即为G的边色数。定义3(可增广路):设M是图G的匹配，P是G的一条路，且在P中，M的边和E(G)-M的边交替出现，则称P是G的一条交错路。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。例1求下图G的一条交错路和一条可增广路。定理1设M1和M2是图G的两个不同匹配，由M1M2导出的G建模案例：最优截断切割问题故存在AV1，使得N(A)<A，矛盾。推论3设G是二部划分(V1，V2)的简单二分图，且若M不能饱和V1，则在V1中选择一个非M饱和点x，若G中存在以x为起点的M可增广路P，则M’=MP就是比M更大的匹配，利用M’代替M，并重复这个过程。T=T{y}，转(4)。若G中不存在以x为起点的M可增广路，则令H是根在x的M交错子图的顶点集，并令S=HV1，T=HV2，由定理1，T=NG(S)，且G中不存在以x为起点的M可增广路，此时称x为检验过的非M饱和点。选址问题--中心问题(2)(a)(b)设y是H中异于x的非M饱和点，则G中存在以x和y为端点的M交错路P。他们利用网络分析的方法，将其分解成6个子问题，利用特殊的网络计算机程序，花了大约7个小时问题就得到了解决。(2)若M饱和V1则结束。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。若yS，则显然有T=S-2。(5)若y为M饱和点转(6)，否则作求一条从x到y的M可增广路P，置M=MP，转(2)若二分图G有完美匹配，由定理3有定理2M是图G的最大匹配，当且仅当G中不存在M可增广路。证明:()假设存在M可增广路P，则M’=MP是G的一个新的匹配，且|M’|＝|M|＋1>|M|，矛盾。()若M不是G的最大匹配，则存在匹配M’，使得|M’|>|M|，作H=M’M，由定理1，H的任意边导出子图Q是下列两种情况之一:(1)交错偶圈:Q中每个结点度数为2。(2)交错路。Q中除端点外，其余结点度数均为2。由于|M’|>|M|，故|E(H)M’|>|E(H)M|，因而H中必有一条起始于M’且终止于M’的连通分支P，故P是M可增广路，矛盾，所以命题正确。定义:NG(S):设S是图G的任意顶点子集，G中与S的顶点邻接的所有顶点的集合，称为S的邻集