设无向图的顶点个数为n,则该图最多有多少条边
3个回答
展开全部
设无向图的顶点个数为n,则该图最多有n(n-1)/2条边。
1个顶点没边,2个顶点1条,3个顶点3条,4个顶点6条,5个顶点10条那么所以就有当n>=3多的时候,任意2个顶点就会有一条边,所以是c2/n。
无向图的最多边是无向完全图:包含n(n-1)/2条边。因为一条边关联两个结点,有向完全图的才有n(n-1)条弧。而无向图变联通至少边数:n-1。有向图变连通图至少需要边数:n。
扩展资料:
下面(b)图中的G2和(c)图中的G3均是无向图,它们的顶点集和边集分别为:
V(G2)={v1,v2,v3,v4}
E(G2)={(vl,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}
V(G3)={v1,v2,v3,v4,v5,v6,v7}
E(G3)={(v1,v2),(vl,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7)}
若G是无向图,则0≤e≤n(n-1)/2
恰有n(n-1)/2条边的无向图称无向完全图(Undirected Complete Graph)
注意:完全图具有最多的边数。任意一对顶点间均有边相连。
参考资料来源:百度百科-无向图
北京丹青华瑞科贸
2024-11-22 广告
2024-11-22 广告
瑞士丹青科技集团成立于1986年,是集研发、生产、销售、技术服务于一体的计量检测设备和几何量测量解决方案供应商...
点击进入详情页
本回答由 北京丹青华瑞科贸提供
展开全部
设无向图的顶点个数为n,则该图最多有n(n-1)/2条边
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
1个顶点没边,2个顶点1条,3个顶点3条,4个顶点6条,5个顶点10条那么所以就有当n>=3多的时候,任意2个顶点就会有一条边,所以是c2/n
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
广告 您可能关注的内容 |