第15章 省赛第一场

  此时的徐辰，確实遇到了麻烦。

  【这个问题，有点棘手。】

  他把陈老师给的竞赛资料在脑子里过了一遍，很確定，没有讲过这类问题的解题技巧。

  陈老师的资料也是托关係从別的学校要来的，都是些常规的竞赛知识点。对於安城三中大部分学生来说，已经完全够用了，再深的东西，教了也学不会。

  所以，徐辰现在只有一个大概的方向，但缺少趁手的数学工具。

  他停下笔，开始思考。

  【要证明存在一种“好”的著色方案，可以反过来想，证明“所有方案都不好”的概率小於1。】

  【一个“不好”的方案，就是指至少有一条边的两个端点顏色相同。】

  他想到了概率论里最基础的工具——联合界。

  【假设a_i是第i条边顏色相同的事件，那么p(a_i)= 1/k。如果图里有m条边，所有坏事件的概率加起来就是 m/k。】

  笔尖在草稿纸上划了几行，徐辰又停下了。

  【不行。m的最大值能到 nd/2，这样算出来的概率和很可能会大於1。联合界这个方法太粗糙了，行不通。】

  他轻轻划掉了刚写的几行字。

  徐辰闭上眼睛，屏蔽了周围的杂音，脑子里只剩下那张由点和线构成的抽象的图。

  【这些“坏事件”a_i之间，不是完全独立的。一条边出问题，会影响到和它共用一个顶点的其他边……但是，这种影响是局部的。】