运筹学第10章习题

1第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,110.2已知9个人921,,,vvv中，1v和两个人握过手，32,vv各和四个人握过手，7654,,,vvvv各和五个人握过手，98,vv各和六个人握过手，证明这九个人中一定可以找出三个人互相握过手。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-12e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15图10-2又课程A必须安排在每一天上午考，课程F安排在最后一门，课程B只能安排在中午考，试列出一张满足各方面要求的考试日程表。表10-1考试课程研究生ABCDEF1ΔΔΔ2ΔΔ3ΔΔ4ΔΔΔ5ΔΔΔ6ΔΔ7ΔΔΔ8ΔΔ9ΔΔΔ10ΔΔΔ10.6用破圈法和避圈法找出图10-2的一个支撑树。10.7用破圈法和避圈法求图10—3中各图的最小树。310.8已知世界6大城市：（Pe）、（N）、（Pa）、（L）、（T）、（M）。试在由表10—1所示交通网络的数据中确定最小树。表10-2城市PeTPaMNLPe×1351776850T13×60706759Pa5160×57362M777057×2055N68673620×34L505925534×223221533522422536474536321(c)(d)图10-3(a)728232443613654174312223425(b)