如果满足以下条件，我们称 n 个顶点的无向图为 p-interesting:
- 该图恰好包含 2n⟩+⟩p 条边；
- 该图不包含自环和多条边；
- 对于任意整数k (1 ≤⟩k ≤⟩n)，任何由k个顶点组成的子图最多包含2k + p条边。
图的子图是一组图的顶点和一组图的边。此时，边集必须满足条件:该集中的每条边的两端必须属于所选的顶点集。
任务是找到一个由 n 个顶点组成的 p-interesting 图。
要查看问题陈述，请单击 here
我连教程解释都看不懂here .
如果有人能指出背景所需的理论或与此问题相关的一些晦涩定理。我会很高兴。
最佳答案
这是一篇有点困惑的社论。让我们首先关注创建 0-interesting 图。图论的关键事实是以下公式。
sum_{vertices v} degree(v) = 2 #edges
在每个顶点的度数为 4 的图中(4-正则图)，左侧为 4n，因此边数恰好为 2n。 4-正则图的每个n'-顶点子图的顶点度数至多为4，因此左侧至多为4n'，边数至多为2n'。因此，每个 4-正则图都是 0-有趣的。有很多方法可以获取 4-正则图；一种是将顶点 i 连接到顶点 i - 2、i - 1、i + 1、i + 2 模 n。
假设 n >= 5，社论旨在证明由边 (1, v) 和 (2, v) 组成的图对于从 3 到 n 和 (1, 2) 的所有 v 是“(-3 )-interesting”，这在技术上是行不通的，因为每个 1-顶点子图最多应该有 2(1) - 3 = -1 条边(糟糕)。但是，由于感兴趣的实际 p 是非负的并且没有自环，所以当我们如下添加附加边时，这个问题将自行解决。对于 n' >= 2 的 n'-顶点子图，我们考虑四种情况，其中两种是对称的。第一种情况是子图既不包含1也不包含2。这个子图没有边，n' >= 2 意味着0 < 2n' - 3。第二种情况是子图包含1但不包含2。这个子图可以有从 1 到它的每个其他顶点的边，最多 n' - 1 <= 2n' - 3 条边。第三种情况是子图有2但没有1；它与第二种情况对称。第四种情况是子图同时包含1和2，在这种情况下最多有1条边在1和2之间，n' - 2条边从1到其他顶点，n' - 2条边从2到其他顶点，最多总共有 2n' - 3 条边。
对于 p-interesting 图，观察结果是，通过将 p 条新边添加到 0-interesting 图，新图中的边数为 2n + p，按要求计算。每个n'-顶点子图中的边数是旧边数加上新边数。和以前一样，旧边的数量最多为 2n'。新边的数量最多为p。
关于algorithm - Codeforces #236 Div2，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23568150/