Re: [理工] 幾題離散

[kiki86151 (白飯)]

用推文講太累 直接另開文
你的證明 我是認為應該不行...殘酷一點可能0分
因為不夠嚴謹 何況想用數歸連前題都沒假設好 就想蒙混過去= =
什麼叫以類推 不就直接隨便代個數字直接說它成立 根本說不通
就算想用數歸應該要先假設n成立
就要"試著證明n+1也成立" 整個就成立才對吧...
而不是隨便代數字就直接說它成立
不過說真的 圖論的證明我也覺得很難 變化很大
定義大家都會 但證明要想很久才能想到很完美的證明 只能說多思考
通常證法 看過可能用鴿籠or找反例比較多

以第六題來說 問如果G有超過11個點 G和Gbar必其中一個不是平面圖

先假設G和Gbar都是平面圖 G=(V,E) Gbar=(~V,~E) 且G有n點>=11
由於是平面圖都必滿足尤拉e<=3v-6和~e<=3~v-6
又v=~v 且e+~e必是最多邊 也就是C(n,2)=n(n-1)/2
又尤拉公式得到的兩式相加得e+~e<=3(v+~v)-12 根據上面得n(n-1)/2<=6n-12
最後整理得n^2-13n+24<=0 解開會得到n不可能大於11所以矛盾
所以n超過11點 G和Gbar必其中一個不是平面圖

至於第五題 也差不多找矛盾吧 太晚了先睡 看有沒有高手補充

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.231.33.174
推 LOVEEE5566:第六題因為還不確定想法對不對所以就沒有繼續寫下去QQ
推 LOVEEE5566:以此類推意思是跟上面v=11一樣的寫法XD
推 LOVEEE5566: http://miupix.cc/pm-S2D53C
你貼的圖 那是數論 本來用數歸法是OK的
但我認為那詳解貌似少講n=k成立試證n=k+1
是會拿到分數 但可能會被扣一點分
個人盡量把n=k+1推導出來

推 LOVEEE5566:我當初是看到這個才想說能不能像這樣寫QQ
→ LOVEEE5566:X雖然題目不一樣XD

第五題我後來想一下
題目是問點s到t 有任何2條path必存在有共同點吧
所以 設2條path沒有共同點 比較好證吧..何必有n個以上共同點= =

下面想到的
如果點s到t有any path就代表G是連通的
因此先假設G中s到t有兩條path為PA和PB 沒有共同點
令PA有nA點eA邊  PB有nB點eB邊
由於G是連通 所以必須要滿足E>=N-1 因此必滿足eA=nA-1和eB=nB-1
兩式相加得eA+eB=nA+nB-2 且eA=eB=floor(n/2)+1代入得
2*floor(n/2)+2=nA+nB-2
又兩條path沒有共同點 這代表這兩條path會形成一個cycle
因此這條cycle的邊為eA+eB=2*floor(n/2)+2等於nA+nB與上面式子矛盾

故存在any path有任兩條path必有共同點

好像錯了
因為cycle上的每點必不重複 所以少減2(?)怪怪的= =
看有沒有人補充
※ 編輯: kiki86151       來自: 36.231.33.174        (11/18 15:59)
推 LOVEEE5566:阿~~我剛剛才在想 是不是因為有一個共同點以上而矛盾
推 LOVEEE5566:最後怪怪的~因為在算cycle邊時不會有重複邊
→ LOVEEE5566:所以直接用2*(FLOOR(n/2)+1) 就跟上面一樣了
推 LOVEEE5566:我懂你的意思了XD 頭尾點會重複所以應該要減2