《浅谈组合数学》PPT课件.ppt

上 图 为 三 阶 洛 书 神 农 幻 方4 9 23 5 78 1 62200BC 1 15 14 412 6 7 9 8 10 11 513 3 2 16 15世 纪 阶 幻 方 11， 11， 2， 11， 3， 3， 11， 4， 6， 4， 11， 5， 10， 10， 5， 11， 6， 15， 20， 15， 6， 1 1 2 3 1 2 3 (1,1) (2,2) (3,3)3 1 2 2 3 1 (3,2) (1,3) (2,1)2 3 1 3 1 2 (2,3) (3,1) (1,2) 1 22 1 1 2 32 3 13 1 2 1 2 4 32 3 1 43 4 2 14 1 3 2 :1 2 33 1 22 3 1 1 2 32 3 13 1 2 1 2 33 1 22 31 2 32 3 13 1 12 Euler 猜 想 组 合 数 学 中 有 一 个 著 名 定 理 ： 如 果 一 个 村 子 里 每 一 个 女孩 都 恰 好 认 识 k个 男 孩 ， 并 且 每 一 个 男 孩 也 恰 好 认 识 k个女 孩 ， 那 么 每 一 个 女 孩 都 可 以 嫁 给 她 认 识 的 一 个 男 孩 ，并 且 每 一 个 男 孩 都 可 以 娶 一 个 他 认 识 的 女 孩 。 （ k 正 则二 部 图 ， 一 定 存 在 一 个 完 美 匹 配 ） 914的 模 式 为 ： 312 37925 的 模 式 为 ： 24513 8 7 6 5 4 3 2 1 避 免 312排 列 n 如 何 用 最 短 的 线 路 将 三 部 电 话 连 起 来 ？n 此 问 题 可 抽 象 为 设 ABC为 等 边 三 角 形 ， ， 连 接 三 顶 点的 路 线 （ 称 为 网 络 ） 。 这 种 网 络 有 许 多 个 ， 其 中 最 短 路 线者 显 然 是 二 边 之 和 （ 如 AB AC） 。 A B C n 但 若 增 加 一 个 周 转 站 （ 新 点 P） ， 连 接 4点 的 新 网 络 的 最短 路 线 为 PA PB PC。 最 短 新 路 径 之 长 N比 原 来 只 连 三点 的 最 短 路 径 O要 短 。n 这 样 得 到 的 网 络 不 仅 比 原 来 节 省 材 料 ， 而 且 稳 定 性 也 更好 。 A B CP 四 九 二三 五 七八 一 六 1 2 1 .1n n n n m n mn n n n n 0 .j k l n k l j n k n lj j k l k l