n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市)，证明：如果有
k＞l/2(n-1)(n-2)
则人们总能通过连接城市的公路在任何两个城市之间旅行。
正确答案：将城市作为结点将连接两个城市的公路作为边则该问题等价于证明一个具有n个结点k条边的简单无向图G是连通图。当n=2时结论显然成立以下证明n＞2时结论也成立。假设G不连通则可将G中的结点集V分为两个子集V1和V2它们．满足V1∪V2=VV1∩V2≠并且V1中的任何结点与V2中的任何结点均不连通。设由V1生成的G的子图G1中有n1个结点k1条边由V2生成的G的子图G2中有n2个结点k2条边则n1+n2=nk1+k2＝k。由于G是简单无向图因此G1和G2也是简单无向图从而有k1≤1/2 n1(n1-1)k2≤1/
词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。