图论设G(p,q)是简单图,求证:q≤1/2p(p-1)在什么情况下q=1/2p(p-1)?

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/07 23:07:03

图论设G(p,q)是简单图,求证:q≤1/2p(p-1)在什么情况下q=1/2p(p-1)?
图论
设G(p,q)是简单图,求证:q≤1/2p(p-1)
在什么情况下q=1/2p(p-1)?

图论设G(p,q)是简单图,求证:q≤1/2p(p-1)在什么情况下q=1/2p(p-1)?
组合数啊.p个点最多组成p(p-1)/2条边
当是完全图的时候,有那么多边

设G(p,q)是简单图,则任意两点之间最多有一条边,故p个结点最多应有2p(p-1) 条边(p个结点的完全图的边数),于是q≤1/2p(p-1) ,如果是完全图,则q=1/2p(p-1)

p个点,任意两点之间如果都存在连接(完全图),那么边数q=p(p-1)/2
如果不是完全图,那么=变成<=