证明如果简单图G是偶图，它有n个结点，m条边，则m≤n²/4
1个回答
展开全部
证明：设G的两个顶点集合中顶点个数分别为n1,n2，并有 n = n1 + n2 (1)；
同时，在简单二部图中，当其为完全二部图是，其边数最大，及max(m) = n1 × n2 (2)；
联立（1）（2）式，当n1=n2=1/2n时，max(m)取得最大值 （n*n）/4 ，所以
一般（n,m）简单二部图，其边数小于等于此最大值既 m≤（n*n）/4
同时，在简单二部图中，当其为完全二部图是，其边数最大，及max(m) = n1 × n2 (2)；
联立（1）（2）式，当n1=n2=1/2n时，max(m)取得最大值 （n*n）/4 ，所以
一般（n,m）简单二部图，其边数小于等于此最大值既 m≤（n*n）/4
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
|
广告 您可能关注的内容 |
