Anu*_*rma 3 algorithm graph-theory graph-algorithm
如果满足以下条件,让我们调用n个顶点的无向图p-interesting:
图的子图是一组图顶点和一组图边.此时,边集必须满足条件:集合中每条边的两端必须属于所选的顶点集.
任务是找到由n个顶点组成的p-interesting图.
要查看问题陈述,请单击此处
我甚至不理解这里解释的教程.
如果有人能指出我背景所需的理论或与这个问题相关的一些模糊定理.我很高兴.
这是一篇有点混乱的社论.让我们首先关注创建0个有趣的图表.图论的关键事实是以下公式.
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,编辑旨在证明由3到n和(1,2)的所有v组成的边(1,v)和(2,v)的图是"(-3) - 有趣的" ",这在技术上不起作用,因为每个1顶点子图应该最多有2(1) - 3 = -1个边(oops).因为感兴趣的实际p是非负的并且没有自循环,所以当我们添加如下的附加边时,这个问题将自行解决.对于n'> = 2的n'-顶点子图,我们考虑四种情况,其中两种是对称的.第一种情况是子图既不包含1也不包括2.该子图没有边,n'> = 2表示0 <2n' - 3.第二种情况是子图包含1而不是2.该子图可以具有从1到每个其他顶点的边,最多n' - 1 <= 2n' - 3个边.第三种情况是子图包括2而不是1; 它与第二种情况对称.第四种情况是子图包括1和2,在这种情况下,它在1和2之间最多有1个边,从1到其他顶点有n' - 2个边,从2到其他顶点有n' - 2个边,总共最多2n'-3个边缘.
对于p-interesting图,观察结果是,通过将p个新边添加到0-有趣图中,根据需要,新图中的边数为2n + p.每个n'-顶点子图中的边数是旧边数加上新边数.与以前一样,旧边数最多为2n'.新边的数量最多为p.