2016 CMO 第 6 题

Let $G$ be a complete directed graph with $100$ vertices such that for any two vertices $x,y$ one can find a directed path from $x$ to $y$ .

a) Show that for any such $G$ , one can find a $m$ such that for any two vertices $x,y$ one can find a directed path of length $m$ from $x$ to $y$ (Vertices can be repeated in the path)

b) For any graph $G$ with the properties above, define $m(G)$ to be smallest possible $m$ as defined in part a). Find the minimim value of $m(G)$ over all such possible $G$ 's.

令 $G$ 为具有 $100$ 个顶点的完全有向图，这样对于任意两个顶点 $x,y$ 都可以找到从 $x$ 到 $y$ 的有向路径。

a) 证明对于任何这样的 $G$ ，可以找到一个 $m$ ，这样对于任意两个顶点 $x,y$ 可以找到一条从 $x$ 到 $y$ 长度为 $m$ 的有向路径(路径中的顶点可以重复)

b) 对于具有上述属性的任何图 $G$，将 $m(G)$ 定义为 a) 部分中定义的最小可能 $m$。找出所有此类可能的 $G$ 的 $m(G)$ 的最小值。