PDF《科别：数学科》

1 i ,

1 i s N S C → : S s s n

2 ∈ '

, 为同

2 类,如果 与的+1,-1 个数相同、包含同数目的封闭区域与分割数并且满足 . s ) '

s '

s ( ) ( C s C = 2. 一个图称为连通如果图形的任两个顶点,都存在一路径连结.若图形存在 w 个连 通区域但彼此不连通,则我们称其为 w 个分割. 3. 一个图为平面图,如果图上除了顶点外没有其他交点. 4. 一个图所包含的封闭区域数为平面被图形分割的总区域数.如果一个图不包含任 何封闭区,那麽一定是树或路径. 5. 平面图的尤拉公式为

2 = + ? r e v ,其中 v 为顶点数、e 为边数、r 为封闭区域数. 6. 多面体压缩到平面上为将多面体的底面挖一个洞拉开,直到能够投影到平面上, 使得顶点数、边数、面数不变的一种变换.

二、 研究过程

(一)、每间房间对外通道数相同的猫抓老鼠问题 我们先讨论最原始的猫抓老鼠问题: 假设有二十间房间,每间房间各养了一只猫,每间房间有三个通道与其 他房间相通,如果现在要抓 k 只猫换成 k 只老鼠,请问如何才能关闭最少的 通道,而将老鼠放进去?

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20 图2我们一个情况一个情况来讨论. 1.一只老鼠: 由於每个房间都有

3 个通道,因此所有解都同类,任取哪一房间皆可. ∴最佳

3 个通道

3 2.二只老鼠: (A)完全连接二房间:由於任选完全连接二房间都与选择 01-06 同类,故断

4 条.

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20 (B)不完全连接二房间 : 由於任选不完全连接二房间都与选择 01-04 同类 , 故6条.

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20 ∴最佳

4 个通道 3.三只老鼠: (A)完全连接的三房间:由於任选完全连接三房间都与选择 01-02-05 同类,故断

5 条.

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20 (B)不完全连接三房间:由於超过

2 个分割,因此断掉的边必定大於等於 6. ∴最佳

5 个通道

4 4.四只老鼠: (A)完全连接的四房间:由於任选完全连接四房间都与选择 01-02-05-04 同类,故断

6 条12345678910

11 12

13 14

15 16

17 18

19 20 (B)不完全连接四房间:由於超过

2 个分割,断掉的边必定大於等於 6. ∴最佳

6 个通道 5.五只老鼠: (A)完全连接的五房间: (1)包含

1 封闭区域:由於任选包含

1 封闭区域五房间都与选择 01-02-03-04-05 同类,故断

5 条12345678910

11 12

13 14

15 16

17 18

19 20 (2)不包含封闭区域:由於任选不包含封闭区域五房间都与选择 01-02-03-04-10 同类,故断

7 条12345678910

11 12

13 14

15 16

17 18

19 20

5 (B)不完全连接五房间:若有

2 个分割,则至少有一个分割的顶点个数大於一, 所以断掉的边必定大於等於 3+4=7.若超过

2 个分割,则断掉的边必定大於 等於 9. ∴最佳

5 个通道 6.六只老鼠: (A)完全连接的六房间: (1)包含

1 封闭区域:由於任选包含

1 封闭区域六房间都与选择 01-02-03-04-05-06 同类,故断

6 条12345678910

11 12

13 14

15 16

17 18

19 20 (2)不包含封闭区域:由於任选不包含封闭区域六房间都与选择 06-07-08-09-10-11 同类,故断

8 条12345678910

11 12

13 14

15 16

17 18

19 20 (B)不完全连接的六房间:若有

2 个分割,则至少有一个分割的顶点个数大於一, 所以断掉的边必定大於等於 3+4=7.若超过