举例:四色问题 问题( Francis Guthrie,1850):地图上的国 家是连通区域,对每个国家着色,以便于区分 具有共同边界的国家着不同颜色(角点除外) 至少需要几种颜色 些地图需要4种颜色 Heawood(1890)证明 至多五种颜色就够了 Appe和 Haken(1976) 100亿个判定 A 1200个机时 200399 Dept of computer Science and Engineering, Shanghai fiaotong University 11 举例:36军官问题 来自6个不同军团,共有6个不同的军阶的36名军 官,能否排成6x6方阵 每行的军官来自不同的军团「(1)(2,2)(3,3) 每行的军官的军阶不同 3×3的例子 (3,2)(1,3)(2,1) ■正交拉丁方 (2,3)(3,1)(1,2) Euer猜想n=2(mod4)时,不存在正交拉丁方(18世纪) Tarry证明n=6时,不存在正交拉丁方(1910) Bose、 Parker、 Shrikhande证明:n≡2(mod4),m>6时 必存在一对正交拉丁方(1960) ■应用:实验设计 200399 Dept of computer Science and Engineering, Shanghai fiaotong Univrsity6 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 11 举例：四色问题 „ 问题（Francis Gurthrie, 1850）：地图上的国 家是连通区域，对每个国家着色，以便于区分。 „ 具有共同边界的国家着不同颜色（角点除外) „ 至少需要几种颜色？ „ 一些地图需要4种颜色 „ Heawood（1890）证明 „ 至多五种颜色就够了 „ Appel和Haken（1976） „ 100亿个判定 „ 1200个机时 2003-9-9 Dept of Computer Science and Engineering， Shanghai Jiaotong University 12 举例： 36军官问题 „ 来自6个不同军团，共有6个不同的军阶的36名军 官，能否排成6x6方阵 „ 每行的军官来自不同的军团 „ 每行的军官的军阶不同 „ 3x3的例子 „ 正交拉丁方 „ Euler猜想n≡2(mod4)时，不存在正交拉丁方（18世纪） „ Tarry证明n=6时，不存在正交拉丁方（1910） „ Bose、Parker、Shrikhande证明：n≡2(mod4), n>6时 必存在一对正交拉丁方（1960） „ 应用：实验设计           (2,3) (3,1) (1,2) (3,2) (1,3) (2,1) (1,1) (2,2) (3,3)