数学建模-图论前言从七桥问题说起---关于图模型为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现。问题分析与模型假设：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。将该图中所有顶点用不同颜色表示，最少需要几种颜色。9问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？问题3(四色问题):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？数学建模-图论数学建模-图论数学建模-图论数学建模-图论数学建模-图论数学建模-图论数学建模-图论若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).顶点u与v称为连通的，如果存在u到v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。一、图的基本概念(应用)一、图的基本概念(应用)一、图的基本概念(应用)一、图的基本概念(应用)一、图的基本概念(应用)一、图的基本概念(应用)293031邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达矩阵等等……1有向图的邻接矩阵A=(aij)n×n（n为结点数）2有向图的权矩阵A=(aij)n×n（n为结点数）3有向图的关联矩阵A=(aij)n×m（n为结点数m为边数）例3：分别写出右边两图的关联矩阵二、图的矩阵表示二、图的矩阵表示若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F).重要性质：设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。43444546472025年3月6日星期四2025年3月6日星期四2025年3月6日星期四2025年3月6日星期四2025年3月6日星期四2025年3月6日星期四54555657585960支配集：DV(G),若图G中任意顶vD，则v必与D内一顶相邻，则D为G的一个支配集。若D是G的覆盖集，若D的任意子集不是支配集。则D是G的极小支配集。含顶最少的支配集为最小支配集。最小支配集中所含顶数为图G的支配数。归为求最小支配v5v6例3.公司生产a,b,c,d,e,f,g7种化学品,其中(a,b)(a,d)(b,c)(b,e)(b,g)(c,d)(c,e)(c,f)(d,e)(d,g)(e,f)(f,g)不能放在一起,公司必须把仓库分成若干个区,以便把不相容的制品分开,问至少分几个区,怎样存放才能保证安全.问题归结为求最小覆盖