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

看板Grad-ProbAsk作者 (BearnoB)時間4年前 (2019/11/08 15:08), 4年前編輯推噓6(6推 0噓 23→)
留言29則, 4人參與, 4年前最新討論串1/1
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
→
11/08 16:15, 4年前 , 1F
死圖，無法解答QQ
11/08 16:15, 1F
→
11/08 16:27, 4年前 , 2F
他把/a/直接改成/gallery/了
11/08 16:27, 2F
不好意思@@剛剛沒意到 已經改好了 ※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:43:05 ※ 編輯: ThereisBear (101.12.24.71 臺灣), 11/08/2019 16:44:03
推
11/08 20:55, 4年前 , 3F
沒有只證1, 2啊 這是強數學歸納法
11/08 20:55, 3F
→
11/08 20:55, 4年前 , 4F
第三行假設<m都成立，去推導=m也成立
11/08 20:55, 4F
推
11/08 21:39, 4年前 , 5F
推樓上正解
11/08 21:39, 5F
→
11/09 02:05, 4年前 , 6F
想想原po應該是想問為什麼初始條件只要證1, 2？
11/09 02:05, 6F
→
11/09 02:05, 4年前 , 7F
這其實沒有一定的準則 強數學歸納法在歸納假設時一次假
11/09 02:05, 7F
→
11/09 02:05, 4年前 , 8F
設所有小於m的情況都成立，這個假設很強，讓推導 =m 的
11/09 02:05, 8F
→
11/09 02:05, 4年前 , 9F
情況時好推很多
11/09 02:05, 9F
→
11/09 02:05, 4年前 , 10F
卻可能有一個問題是雖然1成立了，1 -> 2卻不成立
11/09 02:05, 10F
→
11/09 02:05, 4年前 , 11F
因為我們是一次假設所有小於的情況都成立，沒有保證到這
11/09 02:05, 11F
→
11/09 02:05, 4年前 , 12F
種骨牌效應一定存在
11/09 02:05, 12F
→
11/09 02:05, 4年前 , 13F
實際上要證幾個初始條件，要看需要證幾個才能讓這種骨牌
11/09 02:05, 13F
→
11/09 02:05, 4年前 , 14F
效應連動
11/09 02:05, 14F
→
11/09 02:05, 4年前 , 15F
以這題來說，1只能說明自己連自己(loop)的情況，需要證
11/09 02:05, 15F
→
11/09 02:05, 4年前 , 16F
到2才會有跟別人連的情況，才能一路推導到m，大概是這
11/09 02:05, 16F
→
11/09 02:05, 4年前 , 17F
樣
11/09 02:05, 17F
推
11/09 09:54, 4年前 , 18F
11/09 09:54, 18F
→
11/09 09:54, 4年前 , 19F
我其實我也有點困惑，推到n=3時我覺得黃色框框由前面1
11/09 09:54, 19F
→
11/09 09:54, 4年前 , 20F
跟2推不出來，我觀念有錯嗎？
11/09 09:54, 20F
推
11/09 12:11, 4年前 , 21F
歸納時有說明 會先在G任取一個circuit C
11/09 12:11, 21F
→
11/09 12:11, 4年前 , 22F
這種情況是C已經是Euler Circuit了 不需要靠歸納假設證
11/09 12:11, 22F
→
11/09 12:11, 4年前 , 23F
另外你下面那個圖不算n=3的case 因為deg要求全是偶數
11/09 12:11, 23F
推
11/09 12:33, 4年前 , 24F
每個點的deg都是偶數吧？
11/09 12:33, 24F
→
11/09 12:33, 4年前 , 25F
更正，黃色框框的都是偶數吧？
11/09 12:33, 25F
→
11/09 12:41, 4年前 , 26F
下面那個
11/09 12:41, 26F
推
11/09 12:56, 4年前 , 27F
懂你意思了，除了一跟二的其他case之外都會被這個algo
11/09 12:56, 27F
→
11/09 12:56, 4年前 , 28F
.找到Euler circuit
11/09 12:56, 28F
→
11/09 12:56, 4年前 , 29F
謝謝
11/09 12:56, 29F
‣ 更多 ThereisBear 的文章
文章代碼(AID): #1TnHHLqJ (Grad-ProbAsk)