haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

42届集训队测试题H

发布时间:2014-03-06 19:32:44  

2001年国家集训队测试题(W)

时间:3月23日上午1:30—5:30

一、k是给定整数,3?k?n. 设n个顶点的图G满足这样的条件:

对于图G的任两不相邻顶点x和y的度必有d?x??d?y??k.

请回答以下问题,并证明你的结论.

(1)设图G最长路的长度l满足不等式3?l?k,图G是否必有长为l?1的圈?(路和圈的长度都是指组成它们的线段数)

(2)对于3?k?n?1并且图G连通的情形,能否断定图G的最长路长度l?k?

(3)对于3?k?n?1的情形,图G是否必有长度为n?1的路(即Hamilton路)

二、约定记L3??3?,Lh??3,4,?,h??h?3?. 任意给定整数n?3,设n个顶点的图G

n2

具有Hamilton圈C,并且边数m?. 问对哪些l?Ln,图G必有长为l的圈? 4

三、MO太空城计划建造n个太空站点,任两太空站点间有一条单向通行的管道相联. 从站点P出发不经其他站点可单向直达的站点被称为P的可直达站点. 考察站点对?P,Q?可共同直达的站点数. 计划要求所有的站点对可共同直达的站点数目都相等.

(1)试计算按此要求建造的太空城的可单向循环通行的三角形数(如果三个太空站点.A,B,C之间的单向通道为A?B?C?A,则称△ABC为可单向循环通行三角形)

(2)是否对无穷多个整数n?3,都能建造有n个站点的符合上述计划要求的太空城?

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com