稳定性定理_数学术语 - 威林百科weilinceramic.com

稳定性定理

数学术语

稳定性定理是图论中的定理。

1.G”可由X(G删除O(ex(n,}c))条边得到.

2. a (G;)=O(ex(n，产))十O(n)， }V

3.对任意常数。>0,G，中满足a(v)>cn的顶点数仅为O(1)，满足b(v)>cn的顶点数仅为

O(ex(n,fc)/n)+O(1).

4.设LE },川=r，若A为S中满足b不含L.

以上叙述中最优划分是指失去边最少的划分.Q (v)和b(v)分别表示顶点v处失去和增加的边数.X表示联图的运算符号.第二稳定性定理以极图偏离XG的程度描述了极图的稳定性.

参考资料

最新修订时间：2024-05-21 16:27

条目作者

概述

参考资料