安徽大学：《运筹学》课程习题详解（PPT讲稿）第八章 图与网络分析

运筹学教程 第八章习题解答 8.1证明在9座工厂之间，不可能每座工厂只与其 他3座工厂有业务联系，也不可能只有4座工厂与偶数 个工厂有业务联系。 解：将有联系的工厂做一条连线。 如果仅有9座工厂只与其他3座工厂有业务联系， 说明顶点次数之和为27，矛盾。 如果只有4座工厂与偶数个工厂有业务联系，其他 5个工厂一定与奇数个工厂有业务联系，说明顶点次 数之和还是奇数，矛盾。 page 2 23 April 2025 School of Management

运筹学教程 School of Management page 2 23 April 2025 第八章习题解答 8.1 证明在9座工厂之间，不可能每座工厂只与其 他3座工厂有业务联系，也不可能只有4座工厂与偶数 个工厂有业务联系。 解：将有联系的工厂做一条连线。 如果仅有9座工厂只与其他3座工厂有业务联系， 说明顶点次数之和为27，矛盾。 如果只有4座工厂与偶数个工厂有业务联系，其他 5个工厂一定与奇数个工厂有业务联系，说明顶点次 数之和还是奇数，矛盾

运筹学教程 第八章习题解答 8.2有八种化学药品A、B、C、D、E、F、G、H 要放进贮藏室。从安全角度考虑，下列各组药品不能 贮存在同一室内：A一C,A一F,A一H,B一D,B F,B—H,C—D,C-G,D—E,D一G,EG, E一F,F一G,G—H,问至少需要几间贮藏室存放这 些药品。 解：能贮存在同一室内的两种药品之间作一条连 线。贮存在同一室内的药品应该构成一个完全图。 ABG,CFH,DE构成完全图。故，存放这些药品最少 需要3间储藏室。 page 3 23 April 2025 School of Management

运筹学教程 School of Management page 3 23 April 2025 8.2 有八种化学药品A、B、C、D、E、F、G、H 要放进贮藏室。从安全角度考虑，下列各组药品不能 贮存在同一室内：A—C，A—F，A—H，B—D，B— F，B—H，C—D，C—G，D—E，D—G，E—G， E—F，F—G，G—H，问至少需要几间贮藏室存放这 些药品。 解：能贮存在同一室内的两种药品之间作一条连 线。贮存在同一室内的药品应该构成一个完全图。 ABG，CFH，DE构成完全图。故，存放这些药品最少 需要3间储藏室。 第八章习题解答

运筹学教程 第八章习题解答 8.3 6个人围成圆圈就座，每个人恰好只与相邻 者不相识，是否可以重新就座， 使每个人都与邻座认 识？ 解：两个人认识作一条连线 2 3 6 3 4 5 5 6 2 page 4 23 April 2025 School of Management

运筹学教程 School of Management page 4 23 April 2025 8.3 6个人围成圆圈就座，每个人恰好只与相邻 者不相识，是否可以重新就座，使每 个人都与邻座认 识? 解：两个人认识作一条连线。 第八章习题解答

运筹学教程 第八章习题解答 8.4判定图8-50中的两个图能否一笔画出，若能， 则用图形表示其画法。 解：(a)图都是偶点，可以一笔画出。b)图只有两 个奇点，一个奇点为起点，另一个奇点为终点。 (a) (b) 图8-50 page 5 23 April 2025 School of Management

运筹学教程 School of Management page 5 23 April 2025 第八章习题解答 8.4 判定图8-50中的两个图能否一笔画出，若能， 则用图形表示其画法。 解： (a)图都是偶点，可以一笔画出。(b)图只有两 个奇点，一个奇点为起点，另一个奇点为终点

运筹学教程 第八章习题解答 8.5求解如图8-51所示的中国邮路问题，A点是邮 局。 6 4 3 3 2 3 3 1 1 1 2 5 1 2 5 图8-51 page 6 23 April 2025 School of Management

运筹学教程 School of Management page 6 23 April 2025 8.5 求解如图8-51所示的中国邮路问题，A点是邮 局。 第八章习题解答

运筹学教程 第八章习题解答 6 4 3 3 2 3 3 1 2 5 1 1 2 5 A page 7 23 April 2025 School of Management

运筹学教程 School of Management page 7 23 April 2025 第八章习题解答

运筹学教程 第八章习题解答 8.6分别用深探法、广探法、破圈法找出图8-52所 示图的一个生成树。 06 d 9 图8-52 page 8 23 April 2025 School of Management

运筹学教程 School of Management page 8 23 April 2025 8.6 分别用深探法、广探法、破圈法找出图8-52所 示图的一个生成树。 第八章习题解答

运筹学教程 第八章习题解答 0 深探法 page 9 23 April 2025 School of Management

运筹学教程 School of Management page 9 23 April 2025 第八章习题解答

运筹学教程 第八章习题解答 V 1 广探法 page 10 23 April 2025 School of Management

运筹学教程 School of Management page 10 23 April 2025 第八章习题解答

运筹学教程 第八章习题解答 型 1 8 破圈法 page 11 23 April 2025 School of Management

运筹学教程 School of Management page 11 23 April 2025 第八章习题解答