Question

证明有向图G是单向连通图当且仅当G中存在经过所有顶点至少一次的通路。百度百科我看不懂。课本上写的略。

离散数学图论定理

Answer 1

证明：
充分性显然.
必要性：设P是G中经历的不同顶点的个数最多的一条途径.
如果有某个顶点x不在P上：任取P上的顶点v，v和x是单向连通的.
第一种情形：对P上的任何顶点v，都不存在从v到x的路，则对P上第一个顶点u，必有从x到u的路Q，那麼把Q和P连起来得到的途径Q*P比P经历的不同顶点的个数要多，矛盾.
第二种情形：存在P上某顶点v使得存在从v到x的路，那麼可以设u是P上最後一个有从u到x的路的顶点，并设从u到x的路为Q.若u是P上最後一个顶点，那麼P和Q联结起来得到的途径P*Q比P经历的不同顶点的个数要多，矛盾.若P在u後仍有顶点，设w为u的下一个顶点，则必存在从x到w的路q，那麼设P=(p,u,e,w,r)，则途径(p,u)*Q*q*(w,r)比P经历的不同顶点的个数要多，矛盾.
所以图G的所有顶点都在P上.