第 9卷 第 2期 重 庆科 技 学 院学报 (自然科 学版 ) 2007年 6月
图 论 及 其 应 用
燕 子 宗 张 宝琪
(长 江大 学 ,荆 州 434000)
摘 要 :图论从诞生 至 今已近 300年,但很多问题 一 直没有很 好地解决 。随着 计算 机科学 的 发展 ,图论 又 重新 成 为了人
们 研 究 讨 论 的 热点 ,这里 给 出 图 论 在 现 实 生 活 中 的 一 些应 用 。
关 键 词 :欧拉 ;图论 ;二分 图 ;哈 密 顿 回路 ;着 色
中图 分 类 号 :0157 文献 标 识 码 :A 文章 编 号 :1673—1980(2007)02—0121—03
在 18世 纪 30年 代 ,一 个 非 常有 趣 的问题 引起
了 欧洲 数学 家 的浓 厚 兴趣 ,这个 问题 要 求遍 历 普 鲁
士 的哥尼斯 堡七 桥 中 的每一座 桥恰 好一 次 后 回到 出
发点 。欧拉 证 明 了这 是不 可 能完成 的 ,此后 ,欧 拉发
表了著名的论文《依据几何位置的解题方法》,这是
图论 领 域 的第 一篇 论 文 ,标 志着 图论 的诞 生 。 图论
的真正 发展 始 于 20世纪 五六 十年 代之 间 ,是 一 门既
古 老 又年轻 的学 科 。
图论极有 趣味性 。严 格来讲 它 是组合数 学 的一
个 重要 分支 。虽然 图论 只是 研 究 点 和线 的学 问 ,但
其应 用领 域 十 分广 阔 ,不 仅 局 限于 数 学 和 计算 机 学
科 。还涵 盖 了社会 学 、交通管 理 、电信领域 等等 。总
的来说 .图论这 门学 科具 有 以下特 点 :
① 图论蕴含了丰富的思想、漂亮的图形和巧妙
的证 明 ;
② 涉及的问题多且广泛 ,问题外表简单朴素 ,
本质上 却 十分复 杂深刻 ;
③ 解决问题的方法千变万化,非常灵活,常常
是 一种 问题 一种解 法 。
由 以上 三个 特 点可 以看 出 。图论 与 其 它 的数 学
分支不 同。它不像 群论 、拓扑等 学科那样 有一套完 整
的理论 体 系和解 决 问题的系统方法 。而且图论所研
究 的 内容非常 广泛 。例如图的连 通性 、遍历性 、图 的
计数 、图的着 色 、图的极值问题 、图的可平面 性等等 。
1 二 分 图
有 一类 非常 重要 的 图 ,如树 ,它 是 图 的特 例 ,这
类 图被称作 二 分 图 ,经 常应用 在 涉及 匹配 的 问题 中。
例 如 。某公 司现在正 经 历一 次罢 工 ,为 了使 公 司在 罢
工 中照 常运 作 。人 事 部确 定 了 4项 关 键 工 作 :销 售 、
维修 、安全 控制 和会 计 ,其 中销售 需要 2人 。表 1给
出 了每个 人 和他们 能胜 任 的工作 .判 断是 否所有 工
作都能有人来负责 ,设每人只能负责一项工作。
表 1 每 个 人 与 他 们 胜 任 的 工 作
会 计 、销 售
销 售 、安 全 控 制
销售 、安全控制 、维修
维 修
安全 、维修
这 看起 来 是社会 学 领域 的 问题 。我们 可 以尝试
多种 方法 。而其 中的一 种方法 就是 将其 化 为 图 ,建 立
一
个 图 的模 型 。最基 本 的 问题 是 如何描 述 它 ,什 么是
结 点 ,什 么是边 ?在 本 问题 中 ,没 有太 多 的选 择 ,只有
人 和工 作 。我 们 可 试 着用 集 合 中 的结 点 来 代 表
人 .用集合 y中 的结点来 代表工作 。用边 来 代表 图
中结点 之 间 的关 系 ,在这 里结 点之 间 的关 系是 “人 能
否 胜任 工作 ”。因此 ,若某 人能 胜任 工作 ,那 么就在 两
个 结点 之 间加上 一条 边 。由于销 售需要 2人 ,所 以用
2个 结 点 .s 和 .s 来 表 示 。如 此 得 到 二分 图 (I),
(II)给 出 了最 大 匹配 ,很 容 易 看 出 每一 项 工作 都 有
B C D E A B C D E
0 Sl s r 0 Sl S2 s
I Ⅱ
图 1 每 个 人 与 他 们 胜 任 的 工作 二 分 图
收稿 日期 :2007—01—04
作 者简 介 :燕子 宗 (1964一),男 ,湖 北 荆 州 人 ,博 士 ,长 江 大 学 信息 与数 学 学 院副 教 授 ,从 事最 优 化 理 论 的教 学 与 研 究 。
·
121·
维普资讯 http://www.cqvip.com
评论1