[工学]图论模型.pdfVIP

图 论 模 型 1 图论的基本概念 问题1(哥尼斯堡七桥问题): 能否从任一陆地出发通过每座桥恰好一次而回到出 发点？ C C A B B A D D 问题2 (哈密顿环球旅行问题): 十二面体的20个顶点代表世界上20个城市，能否从 某个城市出发在十二面体上依次经过每个城市恰好一 次最后回到出发点？ 哈密顿圈（环球旅行游戏） 图论中的“ 图”并不是通常意义下的几何图形或物体 的形状图, 而是以一种抽象的形式来表达一些确定的事 物之间的联系的一个数学系统. 定义 一个有序二元组 V, E 称为一个图, 记为G = V, E , 其中 (1) V ≠ 称为G的顶点集, 其元素称为顶点或结点; (2) E 称为G的边集, 其元素称为边, 它联结V 中的两个 点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = {v , v , … , v }是有限集, 则称G为有限图或n 1 2 n 阶图. 如果E 的每一条边都是无向边, 则称G为无向图; 如 果E 的每一条边都是有向边, 则称G为有向图; 否则, 称 G为混合图. 记作 V = {v , v , … , v }, E = {e , e , … , e } 1 2 n 1 2 m 称点v , v 为边v v 的端点. 在有向图中, 称点v , v 分别为 i j i j i j 边v v 的起点和终点. 该图称为(n, m) 图 i j 对于一个图G = V, E , 人们常用图形来表示它, 称其为图解. 凡是有向边, 在图解上都用箭头标明其方向. 例如, 设V = {v , v , v , v }, E = { v v , v v , v v , v v , v v , 1 2 3 4 1 2 1 3 1 4 2 3 2 4 v v }, 则G = ( V, E ) 的图解如下图所示. 3 4 有边联结的两个点称为相邻顶点, 有一个公共端点的边称为 相邻边. 边和它的端点称为互相关联. 定义 若将图 G 的每一条边e 都对应一个实数W(e), 则称W(e) 为该边的权, 并称图G为赋权图(网络), 记为G = V, E , W . 例 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河 到河东. 由于船小,一次只能带一物过河，并且狼与羊, 羊与菜不能在无人时共处.给出渡河方法. 解：用四维0-1 向量表示(人,狼,羊,菜)在河西岸的状态 (在河西岸则分量取1,否则取0),共有24 =16 种状态.在河 东岸的状态类似记作. 由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从 而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的. 以可允许的10个状态向量作为顶点,将可能互相转移 的状态用线段连接起来构成一个图. 根据此图便可找到渡河方法. (1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,1,0,1) (0,1,0,0) (0