作者fragmentwing (片翼碎梦)
看板Math
标题[离散] 关於hamiltonian的问题
时间Fri Oct 23 09:13:03 2020
在读别人的笔记时看到的
关於HC：
是看到有一题写到不相邻两点x,y
deg(x)+deg(y)>=n则G必有HC
我上网查这应该其实是在讲Ore's theorem
但是那理论最後是说，符合条件的会形成Hamiltonian图形
并没有特别指HC或HP
99年台大资工的题目，不知道是不是条件有缺还是单纯他抄错
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.71.214.174 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1603415589.A.42C.html
※ 编辑: fragmentwing (111.71.214.174 台湾), 10/23/2020 09:36:45
1F：→ hwanger : 可以形成HC 下图节自"Introductory Combinatorics, 10/23 10:45
2F：→ hwanger : 5th ed., Richard A. Brualdi" 10/23 10:46
4F：→ hwanger : 证明的话书里有 10/23 10:48
5F：→ hwanger : 有HC 自然而然就有HP 10/23 10:48
6F：→ hwanger : 看到标题 当下是觉得要算量力或古典力学的题目 冏 10/23 10:49
7F：→ fragmentwing: 感谢ｈ大提供解法 10/23 12:41
8F：→ fragmentwing: 之後细看其实不算解法 不过後来有找到了 10/24 16:48
9F：→ hwanger : ??? 你原文中的问题不是满足Ore's property的图是有 10/24 21:12
10F：→ hwanger : HC还是HP吗 不太懂你後来找到的意思 10/24 21:15
11F：→ fragmentwing: 他这样写已经足够证明了吗 50个点 x＝4 45个点没有 10/24 23:38
12F：→ fragmentwing: 与该点相连且这些点degree46起跳 没有直接说明这个 10/24 23:38
13F：→ fragmentwing: 案例怎麽连成HC 10/24 23:38
14F：→ hwanger : 冏 那不是证明 只是我要连Ore's property也节下来 10/25 00:09
15F：→ hwanger : [10/23 10:48]"证明的话书里有">>>书里写了将近两页 10/25 00:10
16F：→ hwanger : 我没节下来 这本书不知为何 google第一笔就是他的电 10/25 00:11
17F：→ hwanger : 子书 想说就算找不到实体书好像也还好 就没节录证明 10/25 00:13
18F：→ fragmentwing: 原来是这样 我总算是看懂当初h大说证明书里有的意思 10/25 00:14