《淺談組合數學》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 這 樣 得 到 的 網 絡 不 僅 比 原 來 節(jié) 省 材 料 ， 而 且 穩(wě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