图论与几何模型-西安电子科技大学电子工程学院.PDF

数学建模实验(数学建模基础之续) 第七讲第七讲第七讲第七讲: : 图论与几何模型图论与几何模型图论与几何模型图论与几何模型 水鹏朗水鹏朗 雷达信号处理国防科技重点实验室 7.17.1 哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题 EulerEuler问题问题 Euler时代代的哥尼斯堡城城区((18世纪)) EulerEuler问题问题 现在的俄罗斯加里宁格勒市 能否找到一条路径:从一 个地方出发穿过每座桥仅个地方出发穿过每座桥仅 一次再回到出发地。 几何抽象几何抽象 几何抽象的目的在于提纯与问题相关的因素几何抽象的目的在于提纯与问题相关的因素((河流河流、桥桥、区区 域），剔除与问题无关的因素(城区的地面景观等) ，以便简 化问题描述。 雷达信号处理国防科技重点实验室 7.17.1 哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题 CC CC AA DD AA AA DDDD BB BB Graph(Graph(图图,无向图无向图)), 图论图论(Graph(Graph Theory)Theory) 雷达信号处理国防科技重点实验室 7.17.1 哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题 图的描述图的描述 一个图 G 由两个集合构成，顶点 图的描述图的描述 ((vertex)) 集集 合合 V(G)(G) 和和 边边 ((Edge)) 集集 合合 E(G). f e V(G)={a, b, c, d, e, f, g, h, i } E(G)={acE(G)={ac, adad, afaf, bdbd, bgbg, chch, didi, a d ef, ei, fg, gh, hi } g g ii a b c d e f g h i a 0 0 1 1 0