设有6个结点的无向图,该图至少应有( )条边才能是一个连通图。
时间: 2024-02-22 07:01:33 浏览: 508
一个无向图是连通图,当且仅当其中任意两个顶点都是连通的,也就是说,它们之间至少存在一条路径。设该图有n个顶点,则当每个顶点都和其他n-1个顶点相连时,该图是完全图,此时该图的边数为n(n-1)/2。而如果该图是连通图,则边数应该大于等于n-1,因为当边数小于n-1时,必然存在一个或多个孤立的点,无法构成连通图。因此,当n=6时,至少应该有6-1=5条边才能构成一个连通图。
阅读全文