图的度数平方和上界问题

mathe

在math.stackexchange看到一个题目:
G是一个简单图(两个不同的顶点之间最多一条边而且每个顶点没有到自己的边),
G有95个点和2021条边，各顶点的度分别是\(d_1,d_2,\cdots,d_{95}\)，试证明
\(d_1^2+d_2^2+\cdots+d_{95}^2\le 300000\)

mathe

我分析出来的条件有\[
\begin{cases}94\ge d_1\ge d_2\ge\cdots\ge d_{95}\ge 0\\
d_1+d_2+\cdots+d_{95}=4042\\
d_1^2+d_2^2+\cdots+d_{95}^2=2(d_2+2d_3+\cdots+93d_{94}+94d_{95})
\end{cases}\]利用这几个条件是否已经足够得出\(d_1^2+d_2^2+\cdots+d_{95}^2\le 300000\)?

mathe

假定G是度平方和最大的简单图，考虑它的邻接矩阵$A=(e_{ij})$，`A`是一个对称的01矩阵，对角线元素都是0.

【引理】如果G的顶点编号按度的降序排列，即$94\ge d_1\ge d_2\ge\cdots\ge d_{n=95}$，那么`A`不在对角线上的元素也是按降序排列的。即\[
\forall\ i_1≠j_1,i_1≤i_2,j_1≤j_2→\ e_{i_1j_1}≥e_{i_2j_2}
\]证明：上式表明`A`中的1偏于左上，0偏于右下。我们只需要证明对于同一行，除去对角线上的元素，1左0右就行了。
用反证法。假定 `\exists\ i,j,k,\ j<k,e_{ij}=0,e_{i,k}=1,d_j≥d_k`，那么交换`e_{ij}`和`e_{ik}`,仅使得`Δd_j=+1,Δd_k=-1`，故\[Δ\left(\sum_{i=1}^nd_i^2\right)=Δ(d_j^2+d_k^2)=(2d_jΔd_j+Δd_j^2)+(2d_kΔd_k+Δd_k^2)=2(d_j-d_k+1)>0\]这与最大平方和相矛盾。
比如下面就是一例符合这种偏聚性的矩阵。
0 1 1 1 1 1 0 0
1 0 1 1 0 0 0 0
1 1 0 1 0 0 0 0
1 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
【线性化公式】$d_1^2+d_2^2+...+d_n^2=2(d_2+2d_3+...+2(n-1)d_n$
证明：由`A\cdot\textbf1=(d_i)` 可知 \[\textbf1^t\cdot A^2\cdot \textbf1=d_1^2+d_2^2+\cdots+d_n^2\] 这里粗黑体`\textbf1`为全 1 向量。上式左边正好是矩阵$A^2$中所有元素之和。
再记$A=(e_i)$,则`A^2=(e_i\cdot e_j)`，当`i≤j`时,\[e_i\cdot e_j=\begin{cases}d_i=d_j,&\text{if}&i=j\\d_j,&\text{if}&i<j,e_{ij}=0\\d_j-1,&\text{if}&i<j,e_{ij}=1\end{cases}
\]所以$A^2$便是如下所示的矩阵（其中`d_i^-`表示`d_i\lor d_i-1)`\[
\begin{pmatrix}d_1&\cdots&d_i^-&\cdots&d_j^-&\cdots&d_n^-\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\
d_i^-&\cdots&d_i&\cdots&d_j^-&\cdots&d_n^-\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\
d_j^-&\cdots&d_j^-&\cdots&d_j&\cdots&d_n^-\\
\vdots&\ddots&\vdots&\ddots&\vdots&\ddots&\vdots\\
d_n^-&\cdots&d_n^-&\cdots&d_n^-&\cdots&d_n\\
\end{pmatrix}\]其中的`d_i^-`对应`A`中非对角线上 0 的地方为`d_i`, 对应`A`中 1 的地方为`d_i-1`, 所以`A^2`中所有`n×n`个元素的和\[
\begin{split}\textbf1^t·A^2·\textbf1&=\sum(2i-1)d_i-\sum d_i\\&=2\sum(i-1)d_i=2(d_2+2d_3+\cdots+(n-1)d_n)\end{split}
\]

mathe

n个点E条边的结果为f(n,E), 通过删除邻接矩阵的第一行第一列，那么我们可以有递推式
\(f(n,E)=\max_{\begin{cases}a(a+1)\ge2E\\a\le n-1\end{cases}}\{f(a,E-a)+4E-3a+a^2\}\)
而且\(f(n,0)=0,f(2,1)=1\)

1. #include <stdio.h>
   
2. #define MAXN 100
   
3. #define MAXE (MAXN*(MAXN-1)/2)
   
4. 
   
5. int ds[MAXN+1][MAXE+1];
   
6. 
   
7. int main()
   
8. {
   
9.     int n,e,a;
   
10.     ds[2][1]=2;
    
11.     for(n=3;n<=MAXN;n++){
    
12.         for(e=1;e<=n*(n-1)/2;e++){
    
13.             a=n-1;if(a>e)a=e;
    
14.             for(;a*(a+1)>=2*e;a--){
    
15.                 int v=ds[a][e-a]+4*e-3*a+a*a;
    
16.                 if(v>=ds[n][e])ds[n][e]=v;
    
17.             }
    
18.             printf("ds[%d,%d]=%d\n",n,e,ds[n][e]);
    
19.         }
    
20. 
    
21.     }
    
22.     return 0;
    
23. }

复制代码

得出f(95,2021)=258618

mathe

我原先以为对于大部分(n,E),达到最优值的解通常应该会有多种不同构的方案，结果没有想到计算$n\le500$以内，
所有的组合中均最多只有3个不同构的解。其中大部分只有唯一方案，部分两种方案，而三种方案只有
(7,9),  {9,18}, {24,133}, {38,349}这四种情况。
比如(7,9)度数分布可以是
6,4,2,2,2,1,1
5,5,2,2,2,2,0
4,4,4,3,3,0,0
度数平方和都是66

mathe

发现程序一个bug,不影响(95,2021)的结果。
但是可以有6种方案的例子,只有n=9,E=18达到。但是没有5种方案的。4种一下的方案的组合应该都有无穷个

mathe

有人给出了一篇文章 https://www.math.uni-bielefeld.de/ahlswede/homepage/public/31.pdf 给出了本题的解
文中给出这个最优解必然被quasi-complete 或quasi-star graph达到。
其中quasi-complete graph对应邻接矩阵前k行k列（忽略对角线）是一个全1正方形，此外只有第k+1行和k+1列还有非零元素。
ds[9,19]=210
        011111100
        101111100
        110111100
        111011100
        111101000
        111110000
        111100000
        000000000
        000000000
而quasi-star graph和quasi-complete graph互补，也就是它的最后k行k列构成全零，此外只有倒数第k+1行k+1列还有0（忽略对角线）。
当然有很多图可以同时是两者，比如:
ds[5,8]=54
        01111
        10111
        11010
        11100
        11000
但是也存在少数最优解不属于两者，但是必然有两者之一和它们一样优秀，比如:
ds[9,18]=192
        011111111 (quasi-star)
        101111111
        110111000
        111000000
        111000000
        111000000
        110000000
        110000000
        110000000

        011111111
        101111111
        110110000
        111010000
        111100000
        110000000
        110000000
        110000000
        110000000

        011111111
        101111000
        110111000
        111011000
        111101000
        111110000
        100000000
        100000000
        100000000

        011111110
        101111110
        110111110
        111000000
        111000000
        111000000
        111000000
        111000000
        000000000

        011111100
        101111100
        110111100
        111011100
        111100000
        111100000
        111100000
        000000000
        000000000

        011111100
        101111100 （quasi-complete)
        110111100
        111011000
        111101000
        111110000
        111000000
        000000000
        000000000

mathe

2#的条件中在二次约束不起作用时，只有线性约束，所有的最大值必然只能在边界取到，由此会导致一批变量合并，最后我们可以将约束方程改写为
\(\begin{cases}
0=i_0\le i_1\le i_2\le\cdots\le i_{t-1}\le i_t\le i_{t+1}=95\\
94=d_0\ge d_1\ge d_2\ge\cdots\ge d_{t-1}\ge d_t=0\\
(i_1-i_0)d_0+(i_2-i_1)d_1+\cdots+(i_t-i_{t-1})d_{t-1}=4042\\
(i_1-i_0)d_0^2+(i_2-i_1)d_1^2+\cdots+(i_t-i_{t-1})d_{t-1}^2\le \\
(i_1^2-i_0^2)d_0+(i_2^2-i_1^2)d_1+\cdots+(i_t^2-i_{t-1}^2)d_{t-1}
\end{cases}\)
我们可以稍微放大范围，将$d_h,i_h$是整数的约束去掉，允许它们有取实数
如果在某一步，二次不等式约束变成了等式约束，那么使用拉格朗日法(u,v为参数），可以得出方程组
\(\begin{cases}
2d_h-u\times(i_{h+1}+i_h)-v=0&(1\le h\le t-1)\\
d_{h-1}+d_h-2u\times i_h-v=0&(1\le h\le t)
\end{cases}\)
记\(e_h=d_h-\frac v2, j_h=u\times i_h\)方程组改为
\(\begin{cases}
2e_h=j_{h+1}+j_h&(1\le h\le t-1)\\
e_{h-1}+e_h=2j_h&(1\le h\le t)
\end{cases}\)
由此得出
\(\begin{matrix}
2j_h=j_{h+1}+j_{h-1}&(2\le h\le t-1)
\end{matrix}\)
所以我们得出\(\begin{cases}i_h=ah+b& (1\le h\le t)\\d_h=ch+d&(0\le h\le t)\end{cases}\), 根据初始条件得出\(d_h=\frac{94(t-h)}t\)带回原始条件可以得到一个关于变量(a,b)的二元二次方程组，可以有两个解，一个极大值，一个极小值。

hujunhua

按2#的线性化公式，度数较小的权重较大，要和最大，不就是均度数么？
但是按平均不等式的方向和驻点条件，均度数会使得平方和变小的呀，这不是互相矛盾么？

原来3#的引理限制了度数的平均化。
因为平均化就会削减最大的`d_1`,使`d_1<n-1`,  这就会在`A`的首行和首列尾部产生0，从而使`A` 的若干尾列和尾行为0，即使得\[
d_{k>d_1+1}=0
\]始欲平均化，不仅未使得较小的`d_{94},d_{95}`等变大，反而使之 趋向0极。
这表明，3#的引理应可使用表达式来表现。

mathe

2#的线性化公式表明，最大值必然在边界取到，由此会导致一批变量合并，可以将约束方程改写为
\(\begin{cases}
0=i_0\lt i_1\lt i_2\lt\cdots\lt i_{t-1}\lt i_t=95\\
94\ge d_1\gt d_2\gt\cdots\gt d_{t-1}\gt d_t\ge d_{t+1}=0\\
(i_1-i_0)d_1+(i_2-i_1)d_2+\cdots+(i_t-i_{t-1})d_t=4042\\
(i_1-i_0)d_1^2+(i_2-i_1)d_2^2+\cdots+(i_t-i_{t-1})d_t^2= \\
(i_1^2-i_1-i_0^2+i_0)d_1+(i_2^2-i_2-i_1^2+i_1)d_2+\cdots+(i_t^2-i_t-i_{t-1}^2+i_{t-1})d_t
\end{cases}\)
递推以后$d_h,i_h$在极值点的线性分布还是不变。
\(\begin{cases}
2d_h-u\times(i_{h-1}+i_h)+u-v=0&(2\le h\le t-1)\\
d_{h+1}+d_h-2u\times i_h+u-v=0&(1\le h\le t-1)
\end{cases}\)
在\(d_1,d_t\)没有取到边界值的情况下，第一式h的下界和上界分别可以扩展到1和t
记\(e_h=d_h+\frac {u-v}2, j_h=u\times i_h\)方程组改为
\(\begin{cases}
2e_h=j_{h-1}+j_h&(2\le h\le t-1)\\
e_{h+1}+e_h=2j_h&(1\le h\le t-1)
\end{cases}\)
由此得出
\(\begin{matrix}
2j_h=j_{h+1}+j_{h-1}&(2\le h\le t-2)
\end{matrix}\)
于是得出$j_h,e_h$线性分布，所以$i_h,d_h$线性分布
如果\(94 \gt d_1 \gt d_t \gt 0\), 那么$i_0~i_t, d_1~d_t$线性分布
如果\(94=d_1\gt d_t\gt 0\),那么$i_1~i_t, d_1~d_t$线性分布
如果\(94\gt d_1\gt d_t= 0\),那么$i_0~i_{t-1}, d_1~d_t$线性分布
如果\(94=d_1\gt d_t = 0\),那么$i_1~i_{t-1}, d_1~d_t$线性分布