2010-7-22离散数学模型分析覆盖问题 清晰版.pdf

离散数学模型分析 离散数学模型分析 —— 覆盖问题 —— 覆盖问题 报告人 杨有龙教授 时 间 2010年7月22 日 Email ylyang@ youlongy@126.com 1 2008年国家一等奖 西安电子科技大学理学院数学系 杨有龙 2 2009年国家二等奖 西安电子科技大学理学院数学系 杨有龙 3 2009年国家二等奖 西安电子科技大学理学院数学系 杨有龙 4 2008年陕西省一等奖 西安电子科技大学理学院数学系 杨有龙 5 2008年陕西省一等奖 西安电子科技大学理学院数学系 杨有龙 6 2009年陕西省一等奖 西安电子科技大学理学院数学系 杨有龙 7 2009年陕西省一等奖 西安电子科技大学理学院数学系 杨有龙 8 2009年国际数模ICM 一等奖 西安电子科技大学理学院数学系 杨有龙 9 2009年国际数模ICM 二等奖 西安电子科技大学理学院数学系 杨有龙 10 近年赛事成绩 赛事 国际大学生数学 全国研究生 全国大学生数学建模竞赛 建模竞赛 数学建模竞赛 国际 国际 国家 国家 陕西省 陕西省 国家 国家 国家 奖项 一等奖 二等奖 一等奖 二等奖 一等奖 二等奖 一等奖 二等奖 三等奖 2008年 3 5 3 1 3 12 2 8 0 2 2 2009年 4 3 1 1 5 2 17 2 7 1 2 3 2010年 3 1 3 西安电子科技大学理学院数学系 杨有龙 11 内容提要 背景问题 覆盖问题 覆盖问题的求解 西安电子科技大学理学院数学系 杨有龙 12 内容提要 背景问题 覆盖问题 覆盖问题的求解 西安电子科技大学理学院数学系 杨有龙 13 问题1 某城市的城建部门计划在每条街 的拐角处或另一个尽头装一个消防水 龙头，需要水龙头的个数是多少？请 建立模型并给出解决的方案。 西安电子科技大学理学院数学系 杨有龙 14 问题2 根据菜单和对应的营养表， 怎么点菜使得营养全、费用少？ 西安电子科技大学理学院数学系 杨有龙 15 问题2 A 西班牙煎蛋 10 B 炒鸡丁 15 菜 单 C 色拉 16 D 牛排 26 E 土豆 12 欢迎用餐 F 洋葱炒肝 24 西安电子科技大学理学院数学系 杨有龙 16 营养成分列表 蛋白质 碳水化合物 维生素 矿物质 A 1 0 1 1 B 1 1 0 0 C 0 0 1 1 D 1 0 0 0 E 0 1 1 0 F 1 0 0 1 西安电子科技大学理学院数学系 杨有龙 17 内容提要 背景问题 覆盖问题 覆盖问题的求解 西安电子科技大学理学院数学系 杨有龙 2 /30 18 背景知识—— 图的表示 G V , E E 一个图 是由“顶点”集合 和“边”集合 所 V 构成，边被看成图的不同顶点的无序对 v, w ∈E . e2 v1 v5 e6 e1 v3 e7 e3 e5 v2 v4 e4 西安电子科技大学理学院数学系 杨有龙 19 五个顶点V v , v , v , v , v 1 2 3 4 5 七条边E e ,e ,e ,e ,e ,e ,e 1 2 3 4 5 6 7 西安电子科技大学理学院数学系 杨有龙 20 图的表示矩阵 用一个上三角形矩阵表示图的顶 点之间是否有边相连，若有边则 矩阵元素为1，否则为0，此矩阵 称为图的表示矩阵。 V V V V V 1 2 3 4 5 V ?0 1 0 0 1 ? 1 ? ? V * 0 1 1 0 2 ? ? V3 ?* * 0 1 1? V ? ? 4 ?* * * 0 1? V5 ??* * * * 0?? 西安电子科技大学理学院数学系 杨有龙 21 图的关联矩阵 v e v ∈e ?v Re 若顶点 与边 j 相关联 i j i j ， i 则记r 1，否则记r 0，矩阵R r 称为 ij ij ij 图的关联矩阵。 e e e e e e e 1 2 3 4 5 6 7 ?1 1 0 0 0 0 0? V 1 ? ? 1 0 1 1 0 0 0 V2 ? ? V ?0 0 1 0 1 1 0 ? 3 ? ? V 0 0