恩 老師是說去掉點。 當時老師在教：定理6-3的證明： |E|>=|V|-1、利用強數學歸納法證明： By induction on V |V|=1、成立 假設|V|<k時成立 當|V|=k時、去掉一點v(deg(v)=m)使得G-v形成j個分量圖、此j個分量圖均連通、根據數學歸納假設， |E|=|E1|+...|Ej|+m =|V1|+...|Vj|-1-j+m =|V|-1+(m-j)得證
回到原來的問題, 如果你問說有沒有可能存在一個圖, 其中的每一點都是cut point, 那答案是否定的, 換句話說, 任何一個連通圖 G 中必定都會存在一個點 v 使得當你去掉 v 時 G 仍可保持連通, 所以理論上我們的確可以取這種 v 出來證, 問題是你得先證明這個 v 的存在性, 這樣整個證明才會完整
5 則留言:
你確定老師是這樣說的嗎? 這應該是不成立的, 如果改成去掉任何一"邊"就會對
恩 老師是說去掉點。
當時老師在教：定理6-3的證明：
|E|>=|V|-1、利用強數學歸納法證明：
By induction on V
|V|=1、成立
假設|V|<k時成立
當|V|=k時、去掉一點v(deg(v)=m)使得G-v形成j個分量圖、此j個分量圖均連通、根據數學歸納假設，
|E|=|E1|+...|Ej|+m
=|V1|+...|Vj|-1-j+m
=|V|-1+(m-j)得證
此時老師說：
有的同學想說就去掉邊邊角角那個點使得G-v(記為G'=(V,E'))仍為連通、
根據數學歸納假設、G-v滿足
|E'|=|V'|-1
所以
|E|=|V|-1+m(deg(v)=m)得證
此時老師說：
若你要這樣證必須先證明必存在這種邊邊角角的點使得去掉後圖必定仍為連通才行、事實上我可以找到例子使得這種點必不存在。
以上是當時的情況、我一直在苦惱這種例子到底為何..
老師的意思不是說存在有一種圖會使得當你去掉它的每一個點都會導致不連通, 而是指這裡不能寫說要去掉甚麼邊邊角角的點, 因為首先你得定義甚麼是邊邊角角的點, 且必須去證明他們的存在性, 畢竟也許不是對每個圖我們都可以找到像這樣邊邊角角的點
回到原來的問題, 如果你問說有沒有可能存在一個圖, 其中的每一點都是cut point, 那答案是否定的, 換句話說, 任何一個連通圖 G 中必定都會存在一個點 v 使得當你去掉 v 時 G 仍可保持連通, 所以理論上我們的確可以取這種 v 出來證, 問題是你得先證明這個 v 的存在性, 這樣整個證明才會完整
老師這裡最主要想強調的是, 圖論這部分的證明若我們還夠不熟悉, 自己在證時寫法上很容易會出現一些有欠考慮的地方, 所以儘量試著去習慣書上的這些圖論證明, 這樣以後自己在證時會比較容易找到方法來嚴謹敘述
P.S. 筆記歸納法推導那段有些小錯誤, 應改成
|E| = |E1| + ... + |Ej| + m
≧ |V1| + ... + |Vj| - j + m
= (|V|-1) + (m-j)
怪了..老師說他有例子阿..
算了、就這樣吧、反正是不成立就對了..
感謝助教囉..'
張貼留言