图的度数平方和上界问题

mathe

如果至少有三个$d_h$非边界，比如$d_2,d_3,d_4$都是非边界值
我们不妨仅把$i_2,i_3,d_2,d_3,d_4$看成变量，其余看成常量，为了清晰，把常量写成大写，于是有
\(\begin{cases}
I_1\lt i_2 \lt i_3 \lt I_4 \\
D_1\gt d_2 \gt d_3 \gt d_4\gt D_5 \\
(i_2-I_1)d_2+(i_3-i_2)d_3 +(I_4-i_3)d_4 = A\\
(i_2-I_1)d_2^2+(i_3-i_2)d_3^2+(I_4-i_3)d_4^2 =  (i_2^2-I_1^2)d_2+(i_3^2-i_2^2)d_3+(I_4^2-i_3^2)d_4+B
\end{cases}\)
求\((i_2-I_1)d_2^2+(i_3-i_2)d_3^2+(I_4-i_3)d_4^2=  (i_2^2-I_1^2)d_2+(i_3^2-i_2^2)d_3+(I_4^2-i_3^2)d_4+B\)最大值
使用拉格朗日法，得到
\(\begin{cases}
2(i_2-I_1)d_2-u(i_2^2-I_1^2)-v(i_2-I_1)=0\\
2(i_3-i_2)d_3-u(i_3^2-i_2^2)-v(i_3-i_2)=0\\
2(I_4-i_3)d_4-u(I_4^2-i_3^2)-v(I_4-i_3)=0\\
d_2^2-d_3^2-u(2i_2d_2-2i_2d_3)-v(d_2-d_3)=0\\
d_3^2-d_4^2-u(2i_3d_3-2i_3d_4)-v(d_3-d_4)=0
\end{cases}\)
消去非零公因子得到
\(\begin{cases}
2d_2-u(i_2+I_1)-v=0\\
2d_3-u(i_3+i_2)-v=0\\
2d_4-u(I_4+i_3)-v=0\\
d_2+d_3-2ui_2-v=0\\
d_3+d_4-2ui_3-v=0
\end{cases}\)
可解得
\(I_4-i_3=i_3-i_2=i_2-I_1=\frac{I_4-I_1}3=\Delta I\gt 0, d_2-d_3=d_3-d_4=\Delta d\gt 0\),其中$\Delta I\gt 0$是常数，$\Delta d\gt 0$是待求变量。
并且记$I_2=I_1+\Delta I, I_3=I_1+2\Delta I$, 于是极值情况$i_2=I_2,i_3=I_3$
将结果代回原先两等式，得到$d_3=\frac{A}{3\DeltaI}$,再代入第二式得到
\((\frac{A}{3\Delta I}+\Delta d)^2+(\frac{A}{3\Delta I})^2+(\frac{A}{3\Delta I}-\Delta d)^2=(I_2+I_1)(\frac{A}{3\Delta I}+\Delta d)+(I_3+I_2)\frac{A}{3\Delta I}+(I_4+I_3)(\frac{A}{3\Delta I}-\Delta d)+\frac{B}{\Delta I}\)
可以化简为\(2\Delta d^2+4\Delta I \Delta d+H=0\), 由于$\Delta I\gt 0$,
所以如果有实数根，要么都负根，要么正根绝对值小于负根的绝对值.

目标函数这时取值\(\Delta I (d_2^2+d_3^2+d_4^2)=(\frac{A}{3\Delta I}+\Delta d)^2+(\frac{A}{3\Delta I})^2+(\frac{A}{3\Delta I}-\Delta d)^2=\frac{A^2}{3\Delta I^2}+2\Delta d^2\)
显然如果两根一正一负时，负根对应的目标值更加大。

现在我们回到题目中约束条件情况，并且再添加限制$i_2=I_2,i_3=I_3$，并或略不等式约束$D_1\gt d_2 \gt d_3 \gt d_4\gt D_5$得到
\(\begin{cases}
d_2+d_3 +d_4 = \frac{A}{\Delta I}\\
d_2^2+d_3^2+d_4^2 =  (I_2+I_1)d_2+(I_3+I_2)d_3+(I_4+I_3)d_4+\frac{B}{\Delta I}
\end{cases}\)
求\((I_2+I_1)d_2+(I_3+I_2)d_3+(I_4+I_3)d_4\)的最大值问题
这个问题的几何意义是限制$d_2,d_3,d_4$在一个三维球面和平面交线（圆）上，求点$(d_2,d_3,d_4)$在向量$(I_2+I_1,I_3+I_2,I_4+I_3)$有向投影的最大值。显然由于这个向量和圆所在平面不垂直（$(I_2+I_1,I_3+I_2,I_4+I_3)$和法线(1,1,1)不同向),所以这个问题正好有一个极大值和一个极小值。
而这个问题同样通过拉格朗日法求解，可以得出根上面完全一样的方程。
这说明了上面方程如果有一个正根一个负根，由于正根对应的目标函数更小，对应这里的极小值，所以对应会上面的问题，它不可能是极大值（但是也可能不是极小值）。而由于$\Delta d$的负根不符合题目不等式约束，得出在约束范围没有极大值点，所以只能在边界取最大值。也就是t必须继续减小。

mathe

所以我们现在只需要考虑最多两个$d_h$非边界值的情况。正好两个非边界值情况分四种
1. $n-1 \gt d_1 \gt d_2 \gt 0, 0=I_0\lt i_1 \lt I_2=n$
2. $n-1=D_1 \gt d_2 \gt  d_3 \gt 0, 0=I_0\lt i_1 \lt i_2 \lt I_3=n$
3. $n-1 \gt d_1 \gt d_2 \gt D_3=0, 0=I_0\lt i_1 \lt i_2 \lt I_3=n$
4. $n-1=D_1 \gt d_2 \gt d_3 \gt D_4=0, 0=I_0\lt i_1 \lt i_2 \lt i_3 \lt I_4=n$
根据12#的分析，
第一种情况取极值要求$i_1=\frac n 2$,
  计算得出对应方程\(\Delta d^2 +n \Delta d -\frac{8e(n(n-1)-2e)}{n^2}=0\)的正根，这时目标函数取值$\frac {16e^2+n^2\Delta d^2}{4n}$
      对应题目中参数可以得出这个极值点取值为250343.166<300000

这种情况由于只有三个参数$i_1,d_1,d_2$,我们也可以根据第一个线性约束消去$i_1$，然后根据第二式做出$d_1,d_2$的关系图，如上图中红色曲线，横坐标为$d_1$,纵坐标为$d_2$, 图中直线$d_1\gt d_2, d_1 \lt 94, d_2 \gt 0$给出了$d_1,d_2$的约束，而另外$0\lt i_1\lt 95$对应两条绿色虚直线。
也就是红色曲线落在带点标记的矩形内部部分才是合法的定义域。然后图中分别出目标函数取值为200000,250343.166,300000对应的图，可以看到250343.166正好和红色曲线相切，这时取到的实际是局部最小值而不是最大值。使用拉格朗日乘数法的一个缺点是很难判断这个点是局部最大还是局部最小值。

第二种要求\(\begin{cases}D_1-d_2=d_2-d_3=\Delta d\\I_3-i_2=i_2-i_1=\Delta i\end{cases}\)
  可以得到\(\begin{cases}\Delta i\Delta d=\frac{n(n-1)-2e}3\\\Delta i^2-\frac35\Delta i-\frac{n(n-1)-2e}3=0\end{cases}\)
     对应题目中参数可以得到极值点取值为\(
\frac53 (n(n-1)-2e)\Delta d-n(n-1)^2+4e(n-1)=\)246881.293<300000
第三种要求\(\begin{cases}d_1-d_2=d_2-D_3=\Delta d\\i_2-i_1=i_1-I_0=\Delta i\end{cases}\)
  可以得到\(\begin{cases}\Delta i\Delta d=\frac{2e}3\\\Delta i-\Delta d=\frac35\end{cases}\)
     对应结果\(\frac{10e\Delta d}3=\)245263.611<300000
第四种要求\(\begin{cases}D_1-d_2=d_2-d_3=d_3-D_4=\Delta D=\frac{D_1-D_4}3\\i_2-i_1=i_3-i_2=\Delta i\end{cases}\)
   可以得到\(\begin{cases}i_2=\frac{2e}{n-1}\\3(n-1)^2 \Delta i^2 +2 (n-1)^3 \Delta i -9e(n^2-n-2e)=0\end{cases}\)
   目标函数在极值点变为\(2e(n-1)-\frac49(n-1)^2\Delta i=\)246361.698<300000

计算量还是太大了,后面还有一个$d_h$不在边界和所有$d_h$都不在边界的情况.

比如$ n-1 \gt d_1 \gt 0$时，所有点的度数等于$d_1$，无法同时满足俩约束
比如$n-1=D_1\gt d_2 \gt 0, 0=I_0\lt i_1\lt I_2=n$, 两个变量，两个约束方程，直接得出
  $d_2= \frac{2e-(n-1)i_1}{n-i_1}$
   $i_1^2-(2n-1)i_1+2e=0$， 对应最值259781.511
比如$n-1 \gt d_1 \gt D_2=0, 0=I_0\lt i_1 \lt I_2=n$, 两个变量，两个约束方程，直接得出
   $d_1i_1=2e, d_1=i_1-1$, 对应最值254964.070
比如$n-1 =D_1 \gt d_2 \gt D_3=0, 0=I_0 \lt i_1 \lt i_2 \lt I_3=n$, 三个变量，两个约束方程
   得出最值取值条件为\(d_2=\frac{D_1+D_3}2=\frac{n-1}2, \Delta i =i_2-i_1 , i_2+i_1 = \frac{4e}{n-1}, \Delta i^2+2(n-1)\Delta i - \frac{16e(n(n-1)-2e)}{(n-1)^2}=0\), 目标函数取值\(4(n-1)^2 (\frac{2e}{n-1}-\frac {\Delta i}2)+(n-1)^2 \Delta i\)。
    本题中计算得到$i_1\lt 0$不符合条件，舍去。

而所有$d_h$都不在边界，就是说所有点度数都是n-1和0，只有一个自由变量$i_1$,无法同时满足两个约束条件。

所以得出在约束条件下目标函数取值不超过259781.511<300000