查看“︁惠特尼不等式”︁的源代码

{{Multiple issues|
{{Refimprove|time=2021-12-10T03:00:00+00:00}}
{{Orphan|time=2021-12-10T04:25:06+00:00}}
}}
在[[图论]]中，'''惠特尼不等式''' (英：'''Whitney's connectivity inequalities''' or '''Whitney's inequalities''')<ref>{{cite journal|title=Congruent Graphs and the Connectivity of Graphs.|author=Whitney, Hassler|url=https://www.jstor.org/stable/2371086|journal=American Journal of Mathematics|doi=10.2307/2371086|year=1932|volume=54|pages=150–68|access-date=2021-12-10|archive-date=2022-05-21|archive-url=https://web.archive.org/web/20220521162419/https://www.jstor.org/stable/2371086}}</ref>，又称为'''惠特尼连通性不等式'''，是关于图的[[连通图|连通度]]的重要不等式，几乎出现于任何一本图论教科书中。该不等式明确地指出了图的点连通度与边连通度以及与图最小度之间的大小关系。但目前关于该定理的提出者是否是[[哈斯勒·惠特尼]]还没有统一定论。<ref>{{cite conference|author=程钊|title=关于惠特尼不等式的历史注记|conference=第三届数学史与数学教育国际研讨会|location=中国北京|url=http://cpfd.cnki.com.cn/Article/CPFDTOTAL-SXDF200905001017.htm|year=2009|access-date=2021-12-10|archive-date=2021-12-10|archive-url=https://web.archive.org/web/20211210061626/http://cpfd.cnki.com.cn/Article/CPFDTOTAL-SXDF200905001017.htm}}</ref>

== 叙述 ==
对于任何一个非平凡图<math>G</math>，均满足

<math display="block">\kappa(G)\leq \lambda(G)\leq \delta(G)</math>其中<math>\kappa(G)</math>表示图<math>G</math>的[[门格尔定理|点连通度]]，<math>\lambda(G)</math>表示图<math>G</math>的[[门格尔定理|边连通度]]，<math>\delta(G)</math>表示图<math>G</math>的[[度 (图论)|最小度]]。

== 证明 ==
[[File:Whitney's_connectivity_inequalities_right_proof.png|替代=惠特尼不等式的右半边证明|缩略图|惠特尼不等式的右半边证明]]

=== 右半边 ===
由于图<math>G</math>的最小度为<math>\delta(G)</math>，于是考虑<math>G</math>中度为<math>\delta(G)</math>的点<math>v</math>，<math>deg(v)=\delta(G)</math>。从<math>G</math>中删除与<math>v</math>相接的所有边，则<math>v</math>成为孤立点，即与<math>v</math>相接的所有边构成了一个不连通边集<math>F</math>，且该不连通边集的大小<math>|F|=deg(v)=\delta(G)</math>。根据边连通性的定义，<math>\lambda(G)\leq |F| = \delta(G)</math>。

=== 左半边 ===
考虑图<math>G</math>的最小不连通边集<math>F</math>，只需证明存在图<math>G</math>的一个割集<math>S</math>，它们的大小满足<math>|S|\leq |F|</math>即可。
对于<math>F</math>，<math>F</math>将图<math>G</math>分割成至少两个[[連通分量 (圖論)|连通分量]]<math>C_1, C_2</math>，这里取<math>C_1</math>为连通分量，<math>C_2</math>为剩余部分（不一定为连通分量）。令<math>T=F\cap C_1</math>，显然<math>T</math>中不包含任何边，否则从<math>F</math>中除去该边，则得到比<math>F</math>更小的不连通边集，与<math>F</math>是最小的不连通边集矛盾。

* 如果<math>C_1-T \neq \varnothing</math>，即<math>C_1</math>除去<math>T</math>中的点外还有其他点<math>v</math>，则<math>T</math>可以作为分离<math>v</math>与<math>C_2</math>的割集。考虑<math>T</math>的大小，断言<math>|T|\leq |F|</math>。这是因为根据上述分析，<math>T</math>中不包含任何边，而<math>T\subseteq F</math>，所以<math>T</math>中任意一点均与<math>F</math>中至少一条边相接。于是<math>\kappa(G)\leq |T|\leq |F| = \lambda(G)</math>。

* 如果<math>C_1-T=\varnothing</math>，即<math>C_1</math>除去<math>T</math>中的点外没有其他点，此时<math>T</math>并不能直接作为割集。任取一点<math>u\in T</math>，考虑<math>u</math>的邻居组成的集合<math>N(u)</math>。显然<math>N(u)</math>分割了<math>u</math>与其他部分，所以<math>N(u)</math>可以作为图<math>G</math>的割集，断言<math>|N(u)|\leq |F|</math>。这是因为，若<math>u</math>的邻居为<math>F\cap C_2</math>中的点，则它们之间的边即为<math>F</math>中的边，所以对于这样的邻居，<math>N(u)</math>中一个点对应了<math>F</math>中一条边；若<math>u</math>的邻居也是<math>F\cap C_1</math>中的点，则一定存在与该邻居相接的在<math>F</math>中的边，所以对于这样的邻居，<math>N(u)</math>中一个点对应了<math>F</math>中至少一条边。于是<math>\kappa(G)\leq |N(u)|\leq |F|=\lambda(G)</math>。<gallery class="center" widths="400" heights="200" caption="惠特尼不等式的左半边证明">
File:Whitney's connectivity inequalities left proof1.png|alt=最小不连通边集的分割情况|最小不连通边集的分割情况
File:Whitney's connectivity inequalities left proof2.png|alt=连通分量中没有其他点的情况|连通分量中没有其他点的情况
</gallery>

== 关于3正则图的推论 ==
当图<math>G</math>是[[正則圖|3正则图]]时，<math>\kappa(G)= \lambda(G)</math>。<ref>{{Cite book|title=Introduction to Graph Theory|url=https://archive.org/details/introductiontogr00west_576|last=West|first=Douglas Brent|publisher=Prentice Hall|year=2001|isbn=81-7808-830-4|pages=[https://archive.org/details/introductiontogr00west_576/page/n173 153]-154}}</ref>

=== 推论证明 ===
[[File:Whitney's_connectivity_inequalities_3-regular_corollary_proof.png|替代=3正则图的割集与不连通边集|缩略图|3正则图的割集与不连通边集]]
根据惠特尼不等式，已有<math>\kappa(G)\leq \lambda(G)</math>，只需证明<math>\kappa(G)\geq \lambda(G)</math>。

考虑图<math>G</math>的最小割集<math>G</math>，由于图<math>G</math>是3正则图，则<math>S</math>与余下被分隔的部分之间的连接只有最多三种类型。

# 对于第一种类型，<math>S</math>中的点与连通分量<math>C</math>相连1条边，与剩余部分相连2条边，则取与连通分量<math>C</math>相连的1条边加入集合<math>F</math>；
# 对于第二种类型，<math>S</math>中的点与连通分量<math>C</math>相连2条边，与剩余部分相连1条边，则取与剩余部分相连的1条边加入集合<math>F</math>；
# 对于第三种类型，<math>S</math>中的点与连通分量<math>C</math>相连1条边，与剩余部分相连1条边，与<math>S</math>中的另一点相连一条边，则取与连通分量<math>C</math>相连的1条边加入集合<math>F</math>。

显然，<math>|F|=|S|</math>，且<math>F</math>是图<math>G</math>的不连通边集。于是<math>\lambda(G)\leq |F|=|S|=\kappa(G)</math>。

== 影响及意义 ==
一方面，该不等式提供了三个图的基本量之间的大小关系，为其他不等式以及定理提供了放缩方向；另一方面，该不等式也反映了「高连通性需要图较为稠密」的组合直观。

== 参考文献 ==
<references />

{{图论}}
[[Category:图论]]
[[Category:组合数学]]
[[Category:理论计算机科学]]
[[Category:数学定理]]