作者ThereisBear (BearnoB)
看板Grad-ProbAsk
標題[理工] 離散 尤拉迴路證明
時間Fri Nov 8 15:08:03 2019
https://imgur.com/a/vK2kVxy
想請教版上大大，為什麼這個證明用數學歸納法，其中只需要證明 n = 1 和 n = 2 的
-----
Sent from JPTT on my Sony G3426.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.24.71 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1573196885.A.D13.html
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 15:13:55
1F：→ realmanKG: 死圖，無法解答QQ11/08 16:15
2F：→ Ricestone: 他把/a/直接改成/gallery/了11/08 16:27
不好意思@@剛剛沒意到 已經改好了
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:43:05
※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:44:03
3F：推 mi981027: 沒有只證1, 2啊 這是強數學歸納法 11/08 20:55
4F：→ mi981027: 第三行假設<m都成立，去推導=m也成立 11/08 20:55
5F：推 realmanKG: 推樓上正解 11/08 21:39
6F：→ mi981027: 想想原po應該是想問為什麼初始條件只要證1, 2？ 11/09 02:05
7F：→ mi981027: 這其實沒有一定的準則 強數學歸納法在歸納假設時一次假 11/09 02:05
8F：→ mi981027: 設所有小於m的情況都成立，這個假設很強，讓推導 =m 的 11/09 02:05
9F：→ mi981027: 情況時好推很多 11/09 02:05
10F：→ mi981027: 卻可能有一個問題是雖然1成立了，1 -> 2卻不成立 11/09 02:05
11F：→ mi981027: 因為我們是一次假設所有小於的情況都成立，沒有保證到這 11/09 02:05
12F：→ mi981027: 種骨牌效應一定存在 11/09 02:05
13F：→ mi981027: 實際上要證幾個初始條件，要看需要證幾個才能讓這種骨牌 11/09 02:05
14F：→ mi981027: 效應連動 11/09 02:05
15F：→ mi981027: 以這題來說，1只能說明自己連自己(loop)的情況，需要證 11/09 02:05
16F：→ mi981027: 到2才會有跟別人連的情況，才能一路推導到m，大概是這 11/09 02:05
17F：→ mi981027: 樣 11/09 02:05
19F：→ b10007034: 我其實我也有點困惑，推到n=3時我覺得黃色框框由前面1 11/09 09:54
20F：→ b10007034: 跟2推不出來，我觀念有錯嗎？ 11/09 09:54
21F：推 mi981027: 歸納時有說明 會先在G任取一個circuit C 11/09 12:11
22F：→ mi981027: 這種情況是C已經是Euler Circuit了 不需要靠歸納假設證 11/09 12:11
23F：→ mi981027: 另外你下面那個圖不算n=3的case 因為deg要求全是偶數 11/09 12:11
24F：推 b10007034: 每個點的deg都是偶數吧？ 11/09 12:33
25F：→ b10007034: 更正，黃色框框的都是偶數吧？ 11/09 12:33
26F：→ mi981027: 下面那個 11/09 12:41
27F：推 b10007034: 懂你意思了，除了一跟二的其他case之外都會被這個algo 11/09 12:56
28F：→ b10007034: .找到Euler circuit 11/09 12:56
29F：→ b10007034: 謝謝 11/09 12:56