数学建模 图论方法专题专题板块系列 概率统计专题 1 优化专题 2 模糊方法及微分方程专题 3 图论方法专题 4图论方法专题 一 一 图论的基本概念 二 二 最短路与最小生成树 三 三 二部图的匹配 四 四 网络流A B C D 哥尼斯堡七桥示意图 问题1:七桥问题 能否从任一陆地出发通过每座桥恰好一次而 回到出发点？ 图论的基本概念七桥问题模拟图: A B D C 欧拉指出：如果每块陆地所连接的桥都是偶数座，则 从任一陆地出发，必能通过每座桥恰好一次而回到出 发地。 图论的基本概念问题2:哈密顿圈（环球旅行游戏） 十二面体的20个顶点代表世界上20个城市，能 否从某个城市出发在十二面体上依次经过每个 城市恰好一次最后回到出发点？ 图论的基本概念问题3:四色问题 对任何一张地图进行着色，两个共同边界的 国家染不同的颜色，则只需要四种颜色就够了。 德摩尔根致哈密顿的信（1852年10月23日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚 了了的事实。他说如果任意划分一 个图形并给各部分着上颜色，使任 何具有公共边界的部分颜色不同， 那么需要且仅需要四种颜色就够了 。下图是需要四
