第10章 图与网络分析习题详解(习题)

10.1 证明如下序列不可能是某个简单图的次的序列：

（1）7,6,5,4,3,2 （2）6,6,5,4,3,2,1 （3）6,5,5,4,3,2,1

10.2 已知9个人v1,v2,?,v9中，v1和两个人握过手， v2,v3各和四个人握过手，

v4,v5,v6,v7各和五个人握过手，v8,v9各和六个人握过手，证明这九个人中一定可以找出三个人互相握过手。

10.3 有八种化学药品A、B、C、D、P、R、S、T要放进储藏室保管。出于安全原因，下列各组药品不能储存在同一室内：A-R、A-C、A-T、R-P、P-S、S-T、T-B、T-D、B-D、D-C、R-S、R-B、P-D、S-C、S-D问储存这八种药品至少需要多少间储藏室。

10.4 已知有十六个城市及他们之间的道路联系（见图10-1）。某旅行者从城市A出发，沿途依次经过J、N、H、K、G、B、M、I、E、P、F、C、L、D、O、C、G、N、H、K、O、D、L、P、E、I、F、B、J、A，最后到达城市M。由于疏忽，该旅行者忘了在图上标明各城市的位置，请应用图的基本概念及理论，在图10—1中标明各城市A~P的位置。

10.5 十名研究生参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表10—1给出了每个研究生应参加考试的课程（打Δ号的）。规定考试应在三天内结束，每天上下午各安排一门。研究生们提出希望每人每天最多考一门，

图10-1

1

又课程A必须安排在每一天上午考，课程F安排在最后一门，课程B只能安排在中午考，试列出一张满足各方面要求的考试日程表。

表10-1

考试课程 研究生 1 2 3 4 5 6 7 8 9 10

10.6 用破圈法和避圈法找出图10-2的一个支撑树。

图10-2

e1 e3 v1 e2 v3 e7 v5

v2 e4

e6 e8

e5

e10 e12

v8 e13 e15

v4 e9

v6 v9

e14

v10

e11 A Δ Δ Δ Δ Δ Δ B Δ Δ Δ Δ C Δ Δ Δ Δ Δ D Δ Δ Δ E Δ Δ Δ F Δ Δ Δ Δ Δ v7

10.7 用破圈法和避圈法求图10—3中各图的最小树。

2

2

4 7 8

1

3 2

2

5 7 4 3 6 (a) 5 2 5

4

3 3

6 2 4

4 1

1

2

2

2 3

(b)

2 4

5

2 3 4 2

2

7

3 6 4

5

6 3 2

1

2 3 2 2 1 3

3 5 (c)

图10-3

(d)

10.8 已知世界6大城市：（Pe）、（N）、（Pa）、（L）、（T）、（M）。试在由表10—1所示交通网络的数据中确定最小树。

表10-2

城市 Pe T Pa M N L

Pe × 13 51 77 68 50 T 13 × 60 70 67 59 Pa 51 60 × 57 36 2 M 77 70 57 × 20 55 N 68 67 36 20 × 34 L 50 59 2 55 34 × 3