Question

离散数学题目 用图论解

N个城市间有K条相互连接的真达公路。证明：当K>(N-1)(N-2)/2时，人们便能通过这些公路在任何两个城市间旅行。

Answer 1

转化为图论问题既是：
在一个N顶点的无向图中，当边数K>(N-1)(N-2)/2时，证明其为连通图，证明如下：
假设存在一个N节点K条边无向图，为不连通的，即设它存在2个连通分支（连通分支越多，边数越少，故只需讨论两个连通分支的情况），并设一个连通分支的节点数为S，则另一个连通分支为N-S，则易知：在这个图中，边数最大条数为
(S-1)(S)/2+（N-S)(N-S-1)/2，（每一个连通分支为完全图），整理得，边数最大为：N×N-(2S+1)+S×S(S>=1),而K>(N-1)(N-2)/2=N×N-3N+2>=N×N-(2S+1)+S×S，故，在这两个连通分支之间必存在边，结论得证。