2016年全国高中数学联赛加试T3解答

2016年全国高中数学联赛加试T3解答

加试T3是图论题。
  题意为10个点的图没有长为3,4的圈,求最大边数。


一个不算困难的图论题。
  首先Peterson图满足条件,边数为15。
  下证边数最大为15。
  没有三角形对应托兰定理,没有四边形对应点对的计数,单独使用都不够紧,所以要综合使用。
  
  容易知道若15边以上,则最大度至少为4,设点a的度最大为 n ≥ 4 n\ge 4 n4,则余下图分为 A A A(a邻域),与 A ˉ \bar A Aˉ
   总 边 数 = n + ∣ A 与 A ˉ 间 连 边 ∣ + ∣ A ˉ 内 连 边 ∣ ≤ n + ( 9 − n ) + ( 9 − n ) 2 4 16 总边数= n+|{A与\bar A间连边}|+|\bar A内连边|\le n+(9-n)+{(9-n)^2\over 4}16 =n+AAˉ+Aˉn+(9n)+4(9n)216
  其中, ∣ A 与 A ˉ 间 连 边 ∣ |{A与\bar A间连边}| AAˉ由没有四边形知, A ˉ \bar A Aˉ每点至多一边到 A A A(考虑点对),而 ∣ A ˉ 内 连 边 ∣ |\bar A内连边| Aˉ由托兰定理保证。
  证毕。

最新回复(0)
/jishuWeTH6Vv6FJorOuMQE8p39Du7kR_2F51sj8ZIZ_2FAA_3D_3D4794692
8 简首页