某天晚上,$21$ 个人之间互通电话 $n$ 次,已知其中 $m$ 个人 $a_1,a_2.\cdots,a_m$ 使得 $a_i$ 与 $a_{i+1}$ 互通了电话 $(i=1,2,\cdots,m,a_{m+1}=a_1)$,并且 $m$ 为奇数.如果在这 $21$ 个人中没有 $3$ 人互通了电话,求 $n$ 的最大值.
【难度】
【出处】
【标注】
【答案】
【解析】
用 $21$ 个点表示 $21$ 个人,若两人互通电话则对应两点连一条边,否则不连边,得到一个图 $G$,已知 $G$ 中含有一个奇圈,并且 $G$ 中不存在三角形,要求 $G$ 中边数 $n$ 的最大值.
设图中长度最短的一个奇圈 $C$ 的长为 $2k+1$,因为 $G$ 中没有三角形,故 $k\geqslant 2$,设 $C$ 为 $A_1A_2\cdots A_{2k+1}A_1$.则对任意 $i,j(1\leqslant i,j\leqslant 2k+1)$,$A_i$ 与 $A_j$ $j\not=i\pm1$ 没有连边 $(A_0=A_{2k+2}=A_1)$(否则存在长度更小的奇圈,与假设矛盾).除 $A_1,A_2,\cdots,A_{2k+1}$ 外,其余 $21-(2k+1)=2(10-k)$ 个点中无三角形,由托兰定理知这 $2(10-k)$ 个点之间最多连有 $\dfrac{1}{4}(20-2k)^2=(10-k)^2$ 条边.又这 $2(10-k)$ 中每一个点不能与 $C$ 中相邻两顶点连有边(否则存在三角形,与假设矛盾),故这 $2(10-k)$ 个点钟每个点至多与 $C$ 中 $k$ 个顶点相邻,所以图中的边数 $n$ 满足:$n\leqslant 2k+1+(10-k)^2+2(10-k)\dot k=102-(k-1)^2\leqslant 102-(2-1)^2=101$.
另一方面,设 $G$ 的 $21$ 个顶点为 $A_1,A_2,\cdots,A_{21}$,$X={A_1,A_2,\cdots,A_5}$,$Y={A_6,A_8,A_{10}\cdots,A_{20}}$,$Z={A_7,A_9,A_{11}\cdots,A_{21}}$.$X$ 中 $A_i$ 与 $A_{i+1}$ 连有边 $(i=1,2,3,4)$ 且 $A_5$ 与 $A_1$ 连有边,$Y$ 中每点与 $Z$ 中每点连有边,$Y$ 中每点与 $X$ 中两点 $A_1$ 和 $A_3$ 连有边,$Z$ 中每点与 $X$ 中两点 $A_2$ 和 $A_4$ 连有边,其余任意两点不连边,则 $G$ 中的边数为:$n=5+8\times8+2\times8=101$.
且 $G$ 中存在一个奇圈 $A_1A_2\cdots A_5A_1$,但不存在三角形.
综上所述,所求 $n$ 的最大值为 $101$.
答案 解析 备注
0.113146s