某居民区内有 $1990$ 个居民，每天他们之中每个人都把昨天听到的消息告诉给他所有的熟人，而且任何消息都能逐渐地被全区居民所知道．证明：可以指定 $180$ 个居民，使得同时向他们指导某一消息，那么至多经过 $10$ 天，这一消息变为全区居民所知道．
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
用点表示这些居民，两个顶点相邻就表示相应的居民是熟人，这样就得到了一个有 $1990$ 个顶点的图 $G$．由题意知，图 $G$ 是连通的，不妨设这个图是树 $T_{1990}$（否则用这个图的生成树来代替它），在图 $T_{1990}$ 中，取一条最长的链，设为 $v_1^{(1)}v_2^{(1)}v_3^{(1)}\cdots v_{n-1}^{(1)}$
取 $v_11^{(1)}$ 作为一个居民代表，并将 $(v_11^{(1)},v_12^{(1)})$ 去掉．这时 $T_{1990}$ 被分成两棵树，前一棵树中，每个顶点 $v$ 到 $v_{11}^{(1)}$ 的距离不大于 $10$（否则在树 $T_{1990}$ 中，$v$ 到 $v_n^{(1)}$ 是一条比 $v_1^{(1)}$ 到 $v_n^{(1)}$ 更长的链）．于是代表 $v_11^{(1)}$ 所知道的消息，前一棵树的顶点所表示的人在 $10$ 天之内都能知道．
取 $v_11^{(1)}$ 作为一个居民代表，并将 $(v_11^{(1)},v_12^{(1)})$ 去掉．这时 $T_{1990}$ 被分成两棵树，前一棵树中，每个顶点 $v$ 到 $v_{11}^{(1)}$ 的距离不大于 $10$（否则在树 $T_{1990}$ 中，$v$ 到 $v_n^{(1)}$ 是一条比 $v_1^{(1)}$ 到 $v_n^{(1)}$ 更长的链）．于是代表 $v_11^{(1)}$ 所知道的消息，前一棵树的顶点所表示的人在 $10$ 天之内都能知道．
答案
解析
备注
