图论模型一、图的相关概念二、常见图类三、较简单的图的模型的建立四、有一定难度的图论模型解答：不能。一个画圈的方格只能和一个没有画圈的方格被一个小棋盘覆盖，而画圈的有32个，不画圈的只有30个。可用二分图的理论解释：即此二分图有无完美匹配的问题。1、以方块为点，两点相邻当且仅当两个方块有公共边，得到一个二分图。2、匹配：一个边的集合，其中任意两条边没有公共边。3、完美匹配：包含了所有的点的匹配即完美匹配。4、若一个二分图有完美匹配，其点集的两个二分划必须有相同点数。2、如下图，边上的数为两点间距离，求从a到f的最短距离。b19c1521a202319f1618c14e此问题看起来简单，实际上有些看似和它毫不相关的问题也可以转化为这类问题。3、某企业使用一台设备，每年年初要决策是购买新的还是继续用旧的。购买新的需购置费，使用旧的需维修费。现已知有关费用如下：给设备在各年初的价格为：第一年第二年第三年第四年第五年1111121213根据使用时间不同每年所需的维修费为：使用年数０－１１－２２－３３－４４－５维修费用5681118请求出五年内总费用最少的设备更新使用计划。分析：以年为点，包括第0年，共6个点。任意两点之间都有一条边，边（i,j)上的权值为第i年的购置费加上从第i年到第j年每年的维修费之和。比如：从0到3，权值为11＋5＋6＋8＝30，从2到4，权值为12＋5＋6＝23.所求即从点0到点5的最短路。4、现有一批化学药品A至F要存放。因为有些药品之间容易发生反应，所以要分开存放。已知不能在一起存放的有如下一些：a和c，b和d，a和d，b和f，c和e，c和f。问题是最少需要几间库房，能够将它们安全存放（假设无论怎样安排都能将一种药品安排在一间库房内）？分析：以化学药品为点，两个点相邻当且仅当两个药品间容易发生反应。则可以放在同一间库房的药品之间没有边相邻。我们称一个点集为独立集，如果此点集内任何两点间没有边相连。此问题就是可以将所有的点划分成最少几个不交的独立集的问题。点着色问题：一个独立集着一种色。如何求点色数以及着色的方法已有成熟的方法。5、多叉路口交通信号灯管理问题：如下图所示，有一个五叉路口，其中C和E为单行道。在路口有13条可行通路，其中有的可以同时通行，有的不能同时通行。那么，在路口应如何设置交通灯进行车辆的管理呢？CDBEA问题：如何设置红绿灯，可使车辆通过时间最短。分别以13个通路为点，两个点相邻当且仅当这两个通路不能同时通行。所求即此图的最小点着色的色数问题。6、如何编制课程表：教室数量有限，且假设所有教室都能容纳每一个教学班级。希望能在最少的时间内让所有的课都上完。以每一教师为一个点，每一个要同时上课的教学班级为一个点，两点相邻当且仅当该教师要给这个教学班级授课。如此可得一个二分图。可以同时上课的班级就是此图的一个边集，其中任何两个边没有公共点（即一个匹配）。此边集的边数不能超过学校能提供的教室数。此问题就是最少可以将所有的边划分几个不交的匹配，使每个匹配的边数不超过教室数。大家都知道“一笔划”这个游戏。此问题即从一个点开始，不重不漏地经过所有的边在回到起点的路径问题。这是一个“边的可行遍性”问题。此问题的结论：可一笔划当且仅当每个点的度（与此点关联的遍的条数）都是偶数。1001构造一个八个点的有向图，八个点分别为{000,001,010,011,100,101,110,111}。我们给001到010画一条从001指向010的边，因为在001后面补上0之后，其后三位是010。同理，我们也要画上一条从001指向011的有向边，这是在后面补1的情况。其它点之间也按这个规律画上有向边，可得下图。其欧拉回路就是01安排方案。0008、货郎担问题(TSP)最优Hamilton路问题（点的可行遍性问题）9、“马行天下”问题在如下的8×8的棋盘上，一个国际象棋的马怎样才能从任意一个格开始，不重不漏的经过所有的格，在回到起点？分析：以每个方格为点，两个点相邻当且仅当马从这个点可以一步跳动另一个点。所求路径就是此图的一个Hamilton路。令人惊奇的是，将马跳动某个方格时的步数写在这个方格上，竟然得到了一个每行每列都是260的幻方。10、商人们怎样安全过河模型构成模型求解11、控制问题：要给一个人不太多的地方安路灯，为了降低成本，考虑只要让每个小巷的某一个灯照到就可以了。那么最少需要多少个灯？此问题即找到此图的一个点集，使得该图的任意一条边至少有一个端点在这个点集中。这类问题的算法还不是很成熟。五、常见网络优化问题六、图的矩阵表示