图与补图的最大度和最小度的关系问题

图与补图的最大度和最小度的关系

搜了一下这类问题，居然没搜到！ 于是自己做了一些整理

先说明一下补图的定义！ 设G=<V,E>为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 G ‾ overline{G} G 或者用如下定义可能更清晰： 设G=<V,E>为n阶无向简单图，以V为顶点集，令 E ‾    =    { ( u , v ) ∣ u ∈ V ∧ v ∈ V ∧ u ≠ v ∧ ( u , v ) ∉ E } overline{E},,=,,left{ left( u,v ight) | uin Vland vin Vland u e vland left( u,v ight) otin E ight} E={ (u,v)∣u∈V∧v∈V∧u=v∧(u,v)∈/E} 则称 G ‾ = < V , E ‾ > overline{G}=<V,overline{E}> G=<V,E> 为G的补图。 注意，补图的顶点和原图的顶点是一样的，只有边改变了！！！顶点没变！ 对于一个完全图，很明显 Δ ( G ) varDelta left( G ight) Δ(G) (最大度) 和 δ ( G ) delta left( G ight) δ(G) （最小度） 都是n-1。 那么一个图的最大度和补图的最小度是什么关系呢？？ 我们画个四阶图理解一下： 对于这样一个图，它的补图如下：

很显然，原图的最大度是2，我们知道，如果此时v1与v4之间关联的话，最大度就变为3。 而正是因为v1是原图最大度对应的点且在v1这个点有那么一条线的空缺！ 所以在补图中，这个v1点一定是最小度对应的点，且最小度为1。 再看v4点， 原图最小度对应的是v4，v4的度为0， 那补图中v4就是最大度对应的点，v4的度为3。 由此我们得出规律！ Δ ( G ‾ ) = n − 1 − δ ( G ) δ ( G ‾ ) = n − 1 − Δ ( G ) varDelta left( overline{G} ight) =n-1-delta left( G ight) \ delta left( overline{G} ight) =n-1-varDelta left( G ight) Δ(G)=n−1−δ(G)δ(G)=n−1−Δ(G) 其中n表示图的顶点的个数。 这样的问题本质上 是要牢牢把握住完全图这个概念去解决，希望对学离散数学的同学有帮助！