要保证连通具有10个顶点的无向图,至少需要()条边。
A.9
B.90
C.37
D.45
正确答案是 C
要保证连通具有10个顶点的无向图,重点是需要保证连通,则需要前面9个顶点两两相连,就能保证第10个顶点加入一条边就能保证连通。即:从9个节点中人任意选取两个节点连接,则需要C(9,2)条边,再加上最后一条边,则总边数为: C(9,2)+1=(9*8)/(1*2)+1=37
我没有实习,也没有赶上校招,毕业之后只能社招,投的简历全部石沉大海,特别受打击。开始反思,找问题。简历做的不够好,产品质量达不到。现在停下来,在开始系统的,查漏补缺的学习。
感觉文章思路挺清晰的~
强~~希望更多人更加努力
为什么不是9啊。
如果是可以确保有,是9,保证有的是37
最好情况是9条边,要保证连同需要考虑最坏情况,即其他9个顶点两两相连,共9*8/2=36条边,这时只需再有一条边即可保证连通。
此题意思是说要多少条边,能保证无论以怎么胡来的连法,都保证一定联通。例如九条边,确实有可以联通的连法,但是如果充满了恶意,只在前5个点连接,则后面5个点是不联通的。必须要更多的边才能保证胡乱连接也一定互联,这个边数就要取到(9个点的全通+1),这样无论怎样试图让其中一个点不连通,只在剩余九个点中连边,最后都剩余一条边,必须把最后一个点连上,于是保证联通了。
9条边可保证10个顶点的无向图连通,如果有37条边,则可确保所有定点连通
总结起来就是:其中9个点构成完全图,另一个点随便连一条边都是通的。即:9*8/2+1=37
不是说10个点连通至少需要多少个点,而是为了保证连通,不管出现什么情况都可以连通,至少需要几个点
多线程中sleep()和wait()方法的区别
使用js实现数组的冒泡排序
如何理解PV、UV、IP
介绍一下标准的CSS的盒子模型?
我没有实习,也没有赶上校招,毕业之后只能社招,投的简历全部石沉大海,特别受打击。开始反思,找问题。简历做的不够好,产品质量达不到。现在停下来,在开始系统的,查漏补缺的学习。
感觉文章思路挺清晰的~
强~~希望更多人更加努力
为什么不是9啊。
如果是可以确保有,是9,保证有的是37
最好情况是9条边,要保证连同需要考虑最坏情况,即其他9个顶点两两相连,共9*8/2=36条边,这时只需再有一条边即可保证连通。
此题意思是说要多少条边,能保证无论以怎么胡来的连法,都保证一定联通。例如九条边,确实有可以联通的连法,但是如果充满了恶意,只在前5个点连接,则后面5个点是不联通的。必须要更多的边才能保证胡乱连接也一定互联,这个边数就要取到(9个点的全通+1),这样无论怎样试图让其中一个点不连通,只在剩余九个点中连边,最后都剩余一条边,必须把最后一个点连上,于是保证联通了。
9条边可保证10个顶点的无向图连通,如果有37条边,则可确保所有定点连通
总结起来就是:其中9个点构成完全图,另一个点随便连一条边都是通的。即:9*8/2+1=37
不是说10个点连通至少需要多少个点,而是为了保证连通,不管出现什么情况都可以连通,至少需要几个点