超级军网最大团问题的多项式时间算法
来源：百度文库 编辑：超级军网 时间：2024/04/30 01:05:22
定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点，
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'中任意两个顶点的距离不大于2；
（3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的
最大团问题。
证明思路：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
只需注意细节，就可证明定理2。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确
定G的顶点色数。
证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图
G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度
小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。
由递归关系可知G的顶点色数可以在n的多项式时间内确定。
由定理1~定理3，对任意n阶简单无向图G=（V,E），n≥3，我们可以在n的多
项式时间内确定G的最大团，即最大团问题是P问题。又最大团问题是NPC问题，
从而NP=P。定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点，
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'中任意两个顶点的距离不大于2；
（3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的
最大团问题。
证明思路：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
只需注意细节，就可证明定理2。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确
定G的顶点色数。
证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图
G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度
小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。
由递归关系可知G的顶点色数可以在n的多项式时间内确定。
由定理1~定理3，对任意n阶简单无向图G=（V,E），n≥3，我们可以在n的多
项式时间内确定G的最大团，即最大团问题是P问题。又最大团问题是NPC问题，
从而NP=P。
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'中任意两个顶点的距离不大于2；
（3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的
最大团问题。
证明思路：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
只需注意细节，就可证明定理2。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确
定G的顶点色数。
证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图
G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度
小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。
由递归关系可知G的顶点色数可以在n的多项式时间内确定。
由定理1~定理3，对任意n阶简单无向图G=（V,E），n≥3，我们可以在n的多
项式时间内确定G的最大团，即最大团问题是P问题。又最大团问题是NPC问题，
从而NP=P。定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点，
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），存在简单无向图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'中任意两个顶点的距离不大于2；
（3）G'与G有相同的最大团。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则G的图着色问题（顶点色数问题）可以在n的多项式时间内转换为G的
最大团问题。
证明思路：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
只需注意细节，就可证明定理2。
定理3.设G=（V,E）是n阶简单无向图，n≥3，G中任意两个顶点的距离不大
于2，则存在n的多项式时间算法，可在该算法下，解决G的图着色问题，即确
定G的顶点色数。
证明思路与算法：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V2,V1∩V2=Ø，G去掉V1中所有顶点（及其关联边）得到图
G2=(V2，E2)。则可以证明G2的顶点色数比G的顶点色数小1；且G2去掉度
小于2的顶点（若这样的顶点存在）后，任意两个顶点的距离也是不大于2的。
由递归关系可知G的顶点色数可以在n的多项式时间内确定。
由定理1~定理3，对任意n阶简单无向图G=（V,E），n≥3，我们可以在n的多
项式时间内确定G的最大团，即最大团问题是P问题。又最大团问题是NPC问题，
从而NP=P。
我2004年毕业于某985高校数学系，研究图着色问题十余年了。
没人看得懂吗？！
NP=P，概括的说就是3句话：
1.任意简单无向图的最大团问题等于其对应的“任意两个顶点的距离不大于2的图”——可以称之为理想图的最大团问题；
2.任意理想图的图着色问题是多项式时间问题；
3.任意理想图，其图着色问题可在多项式时间内转换为它的最大团问题。
逻辑很清楚啊。
没人看得懂吗？！
NP=P，概括的说就是3句话：
1.任意简单无向图的最大团问题等于其对应的“任意两个顶点的距离不大于2的图”——可以称之为理想图的最大团问题；
2.任意理想图的图着色问题是多项式时间问题；
3.任意理想图，其图着色问题可在多项式时间内转换为它的最大团问题。
逻辑很清楚啊。
不明觉厉我放弃英语好多年了。谁能帮我翻译成英文啊！价格面议。
我的邮箱154088532@qq.com联系地址：江西省鹰潭市余江二中 胡老师
另外，我想投稿，往哪里投比较好？（不需要版面费的）
我的邮箱154088532@qq.com联系地址：江西省鹰潭市余江二中 胡老师
另外，我想投稿，往哪里投比较好？（不需要版面费的）
要翻译，首先得看懂
飞之鹰 发表于 2016-1-31 10:47
我放弃英语好多年了。谁能帮我翻译成英文啊！价格面议。
我的邮箱联系地址：江西省鹰潭市余江二中 胡老 ...
发科技大咖微博
我放弃英语好多年了。谁能帮我翻译成英文啊！价格面议。
我的邮箱联系地址：江西省鹰潭市余江二中 胡老 ...
发科技大咖微博
版主啊，我不知道他们的微博啊！我也没有微博。
不过上面的有错误，下面这个是我之前想的，是正确的（个人认为）。
论NP=P:最大团问题的多项式时间算法
余江二中 胡xx（湖南大学数学2004届）
定义：任意两个顶点的距离都小于3的简单无向图称为理想图。
定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点，
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），可找到理想图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'与G有相同的最大团。
注：G的理想图可能不止一个。例如：边数为4的道路，在同构意义下有两个
理想图。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G存在奇回路，则G的最大团问
题与G的图着色问题（顶点着色）之间存在n的多项式时间归约。
证明：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
具体细节以后再发。
定理3.设G=（V,E）是n阶理想图，n≥3，则可在n的多项式时间内找到
G'=(V'，E')，满足：
（1）G的阶数大于G'的阶数；
（2）G的顶点色数比G'的顶点色数大1。
证明：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V',V1∩V'=Ø，G去掉V1中所有顶点（及其关联边）得到图
G'=(V'，E')。则G'的顶点色数比G的顶点色数小1。
定理4：最大团问题存在多项式时间算法，从而NP=P。
证明：分为4个命题。
命题1.对任意n阶简单无向图G=（V,E），存在理想图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'与G有相同的最大团。
命题2.理想图G'的最大团问题可以归约为G'的图着色问题。
命题3.对理想图G'，可找到G''，满足：
（1）G'的阶数大于G''的阶数；
（2）G'的顶点色数比G''的顶点色数大1。
命题4.G''的图着色问题可以归约为G''的最大团问题。
以上4个命题都只需n的多项式时间。
由命题1~命题4，对任意简单无向图G=（V,E），可以找到G''，使得G的最大
团问题可以在n的多项式时间内归约为G''的最大团问题，且G的阶数比G''的阶
数要大。由递归关系可知，G的最大团问题可以在n的多项式时间内解决。由于最大
团问题是NP完全问题，从而NP=P。
不过上面的有错误，下面这个是我之前想的，是正确的（个人认为）。
论NP=P:最大团问题的多项式时间算法
余江二中 胡xx（湖南大学数学2004届）
定义：任意两个顶点的距离都小于3的简单无向图称为理想图。
定理1.设G=（V,E）是简单无向图，va、vb是G中距离大于2的两个顶点，
E'=E∪{（va，vb）}，则G'=(V，E')与G有相同的最大团。
证明：显然。
推论：对任意简单无向图G=（V,E），可找到理想图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'与G有相同的最大团。
注：G的理想图可能不止一个。例如：边数为4的道路，在同构意义下有两个
理想图。
定理2.设G=（V,E）是n阶简单无向图，n≥3，G存在奇回路，则G的最大团问
题与G的图着色问题（顶点着色）之间存在n的多项式时间归约。
证明：已知图着色问题≤p SAT（“≤p”表示多项式时间归约）
SAT≤p 3-SAT
3-SAT≤p 团问题
具体细节以后再发。
定理3.设G=（V,E）是n阶理想图，n≥3，则可在n的多项式时间内找到
G'=(V'，E')，满足：
（1）G的阶数大于G'的阶数；
（2）G的顶点色数比G'的顶点色数大1。
证明：易知G是k-部图（不一定、也无须是完全k-部图）。
算法：设v是G中度最大的顶点，显然v的邻点应该与v着色不同。在距离v为2的
顶点中，依次选取G中度最大且互不相邻的顶点，得到包含v的一个极大独立集V1，
设V=V1∪V',V1∩V'=Ø，G去掉V1中所有顶点（及其关联边）得到图
G'=(V'，E')。则G'的顶点色数比G的顶点色数小1。
定理4：最大团问题存在多项式时间算法，从而NP=P。
证明：分为4个命题。
命题1.对任意n阶简单无向图G=（V,E），存在理想图G'=(V，E')，满足：
（1）E⊆E'；
（2）G'与G有相同的最大团。
命题2.理想图G'的最大团问题可以归约为G'的图着色问题。
命题3.对理想图G'，可找到G''，满足：
（1）G'的阶数大于G''的阶数；
（2）G'的顶点色数比G''的顶点色数大1。
命题4.G''的图着色问题可以归约为G''的最大团问题。
以上4个命题都只需n的多项式时间。
由命题1~命题4，对任意简单无向图G=（V,E），可以找到G''，使得G的最大
团问题可以在n的多项式时间内归约为G''的最大团问题，且G的阶数比G''的阶
数要大。由递归关系可知，G的最大团问题可以在n的多项式时间内解决。由于最大
团问题是NP完全问题，从而NP=P。
这是最后的文稿，再也没有了，思路无误，细节待补充。
我没有时间！
我没有时间！
帮楼主顶，楼主你可以申请一个微博，关注中科院之声，联系他们试一下
楼主，你可以联系一下你的母校，或者你的导师呀
作为会员我不应该发表以下言论，作为版主我必须指出：你能够在多项式时间内解决最大团问题，那么必然可以在多项式时间解决最小顶覆盖问题、Hamilton 圈问题、最大独立集问题等图论内的等价NP，这已经是划时代的成就；通过这个问题你还妄图证明NP=P，那么已经取得等同于解决庞加莱猜想的伟大成就，成为第二个解决千禧7大数学问题的，第一位可以领取百万美金的最顶尖的科学家了。毫无疑问，我个人认为这个是民科帖子，如果有异议请向高一级版主申诉。
@华夏冉闵。数学专业毕业，十几年的研究，你一句“民科”就打发了，未免太武断了吧！
顶级数学玩的就是思路。我这文章，也就定理2没有详细的证明（个人能力有限，目前给不出完整的）――陶哲轩那一伙人应该可以在两年内证明。被你这一激，我还就杠上了――以《NP=P的一个充要条件》为标题，将此文自行翻译并向美国《数学年刊》等顶级杂志投稿。
手机码字不易。再说一句，你的回复有语意矛盾：分号前后的内容重复却是递进关系。