例1、在一個有n個頂點的G=V,E中,u,vV若存在一條從u到v的

1、例1、在一個有n個頂點的G=<V,E>中，u,vV。若存在一條從u到v的一條通路，則必有一條從u到v的長度不超過n-1的通路。問題解析：象這類存在性命題在圖論中比較多見，往往就可采用構(gòu)造性證明方法，問題的關(guān)鍵就是找出命題結(jié)論所要求的通路。證明的思路是從某一個事物出發(fā)，就象計算機(jī)程序中的循環(huán)語句一樣用同樣的過程根據(jù)要求對之進(jìn)行加工，在有限步內(nèi)得到所求。證明：設(shè)veve2ev是從u=v到v=v的長為的通路。若n-1，則結(jié)論顯然成立。否則因為+1>n，故v,v,v中必有一個頂點是重復(fù)出現(xiàn)的。不妨設(shè)v=v(0i<j)，則新通路vevevevevev是一條從u 到v的通路，且此通

2、路長度比原通路長度至少少1。若新通路的長度n-1，則結(jié)論得證。否則對新通路重復(fù)上述過程，必可以得到一條從u到v的長為n-1的通路。例2 、一個有向圖是單向連通圖它有一條經(jīng)過所有結(jié)點的路。問題解析：這也是圖論中的存在性命題，可采用構(gòu)造性證明方法。先找出一條經(jīng)過若干個頂點的通路。然后想辦法將這條路進(jìn)行變化，使得它經(jīng)過的頂點越來越多，直到得到一條經(jīng)過所有頂點的路。證明：設(shè)G=<V,E>是單向連通圖。任取u,vV，則u可達(dá)v或v可達(dá)u。不妨設(shè)u可達(dá)v，即從u到v有路徑P。若P經(jīng)過G中所有頂點至少一次，則P就是滿足結(jié)論要求的路徑。否則若P沒有經(jīng)過頂點w，則如果v經(jīng)過路徑T可達(dá)w, 連接P和T

3、我們可得一條經(jīng)過P經(jīng)過的所有頂點及w的更長的路徑P；否則若w經(jīng)過路徑S可達(dá)u，連接S和P我們也可得一條經(jīng)過w及P經(jīng)過的所有頂點的更長的路徑P；再否則我們一定可以找到P經(jīng)過的兩個相鄰頂點t和s，t到s有邊，t經(jīng)過路徑T 可達(dá)w，w經(jīng)過路徑T可達(dá)s（否則就與u可達(dá)w，w可達(dá)v矛盾），我們構(gòu)造這樣一條路徑P：從u出發(fā)經(jīng)過P到達(dá)t,t經(jīng)過路徑T到達(dá)w，再從w出發(fā)經(jīng)過路徑T到達(dá)s，然后從s出發(fā)經(jīng)過P到達(dá)v。這是一條經(jīng)過w及P所經(jīng)過的所有頂點的更長的路徑。 P Pu v u v T S w w P u t s v T T w 對P重復(fù)上述過程，直到得到一條經(jīng)過所有頂點的路徑為止。例3 、任一有限半群一定在

4、等冪元。問題解析：這是代數(shù)結(jié)構(gòu)中的存在性命題，也可采用構(gòu)造性證明方法。由于半群的性質(zhì)有限，只有結(jié)合律可用。因此證明時要充分利用元素個數(shù)的有限性和半群的運算滿足結(jié)合律，具體構(gòu)造出一個等冪元。證明： 設(shè)<S,*>是一個有限半群。任取aS，由于*滿足結(jié)合律，我們有 a,a,a,a,S 因為S是有限集合，故a,a,a,a,不可能兩兩不同。從而一定存在正整數(shù)k,m,1k<m使得 a=a令p=m-k，則由于*滿足結(jié)合律，a=a= a* a。對任意正整數(shù)qk，有a= a * a =（a* a）*a= a* a （#） 若p=q，則元素a就是一個等冪元。否則因為p1，故存在正整數(shù)n滿足npk。故利用