作者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/cn.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