图论模型数学系孙艳蕊主要内容 图模型 最短路问题 最小生成树问题 旅行售货员问题 最大流问题 图论的基本概念 匹配问题一、图模型 例1.哥尼斯堡七桥问题(18世纪，1736年)(1)问题能否从一块陆地出发,走遍每座桥一次且仅一次然后回到出发地?ABCD普瑞格尔河(2)问题分析与模型假设 问题的本质是能否从一地无重复地一次走遍七桥, 与所走过的桥的大小、形状、长短、曲直等均无关，因此不妨将其视为一条弧线； 四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的无关，因而可视四块陆地为四个点A、B、C、D。 对四个陆地A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为边。A B C D问题变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。-Euler-回路(圈)问题。ABCD 例2药品存储问题 有8种化学药品A、B、C、D、P、R、S和T要放进贮藏室保管,出于安全原因,下列各组药品不能贮在同一室内:AR，AC，AT，RP，PS，ST，TB，BD，DC，RS，RB，PD，SC，
