[理工] 離散 尤拉迴路證明

[ThereisBear (BearnoB)]

https://imgur.com/a/vK2kVxy
想請教版上大大，為什麼這個證明用數學歸納法，其中只需要證明 n = 1 和 n = 2 的

-----
Sent from JPTT on my Sony G3426.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.24.71 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1573196885.A.D13.html
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 15:13:55
→ realmanKG: 死圖，無法解答QQ
→ Ricestone: 他把/a/直接改成/gallery/了
不好意思@@剛剛沒意到 已經改好了
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:43:05
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:44:03
推 mi981027: 沒有只證1, 2啊 這是強數學歸納法
→ mi981027: 第三行假設<m都成立，去推導=m也成立
推 realmanKG: 推樓上正解
→ mi981027: 想想原po應該是想問為什麼初始條件只要證1, 2？
→ mi981027: 這其實沒有一定的準則 強數學歸納法在歸納假設時一次假
→ mi981027: 設所有小於m的情況都成立，這個假設很強，讓推導 =m 的
→ mi981027: 情況時好推很多
→ mi981027: 卻可能有一個問題是雖然1成立了，1 -> 2卻不成立
→ mi981027: 因為我們是一次假設所有小於的情況都成立，沒有保證到這
→ mi981027: 種骨牌效應一定存在
→ mi981027: 實際上要證幾個初始條件，要看需要證幾個才能讓這種骨牌
→ mi981027: 效應連動
→ mi981027: 以這題來說，1只能說明自己連自己(loop)的情況，需要證
→ mi981027: 到2才會有跟別人連的情況，才能一路推導到m，大概是這
→ mi981027: 樣
推 b10007034: https://i.imgur.com/9IPFlb9.png
→ b10007034: 我其實我也有點困惑，推到n=3時我覺得黃色框框由前面1
→ b10007034: 跟2推不出來，我觀念有錯嗎？
推 mi981027: 歸納時有說明 會先在G任取一個circuit C
→ mi981027: 這種情況是C已經是Euler Circuit了 不需要靠歸納假設證
→ mi981027: 另外你下面那個圖不算n=3的case 因為deg要求全是偶數
推 b10007034: 每個點的deg都是偶數吧？
→ b10007034: 更正，黃色框框的都是偶數吧？
→ mi981027: 下面那個
推 b10007034: 懂你意思了，除了一跟二的其他case之外都會被這個algo
→ b10007034: .找到Euler circuit
→ b10007034: 謝謝