推 HEroKuma: 3無迴圈連通圖, 也就是tree12/27 10:19
推 w181496: 1.應該是一定要先選那三條邊 剩下n取2 -3條可取可不取 這12/27 10:41
→ w181496: 樣就包含三角形了 12/27 10:41
推 moooner: 1.你都講說可取可不取，那我要取一個三角形不就等於一定12/27 10:44
→ moooner: 要取三個便，所以扣掉3。我是這樣理解，有錯請告知12/27 10:44
推 HEroKuma: 2 ,每個人deg至少k 所以大家至少k個鄰居 12/27 10:48
→ HEroKuma: 從點v0開始 每取一個其他人deg就-112/27 10:49
每取一個，其他人的deg就-1
那不就代表每個點都彼此相連嗎
意思是指至少我能保證一條v1至vk再到v1的cycle嗎
還是覺得很抽象，如果有十個點，deg最少為5好了，不也能找到長度為3的cycle嗎？(v1v
2v3v1)
請問這個證明的在證最大的cycle嗎？
→ HEroKuma: 取完k個結束 迴圈長=點數+112/27 10:49
→ HEroKuma: 這是概念 嚴謹證明要再翻一下12/27 10:50
推 HEroKuma: 1是一定要有某三角形abc所以-312/27 10:52
※ 編輯: newpuma (42.73.172.102), 12/27/2016 12:30:10
推 Transfat: (3)的話取一個Tree 就是graph 且|E|=|V|-112/27 12:45
瞭解
→ Transfat: (1)和(2) 有沒有完整一點的描述啊，有點看不懂想要問什 12/27 12:45
定理跟筆記這樣寫，我也想找完整一點描述，比較好理解QQ
推 HEroKuma: 10個點每人5個鄰居 確定至少可以取到五點形成迴圈 所以 12/27 12:45
→ HEroKuma: 大小是6 12/27 12:45
推 HEroKuma: 2的問題應該是一張圖deg(v)最小為k ,v屬於G, 則必有一cy 12/27 12:47
→ HEroKuma: cle長為k+1 12/27 12:47
推 HEroKuma: 我那個說法有點太簡易了 概念是最差的狀況為每次取的點12/27 12:53
→ HEroKuma: 都是前a個的鄰居 這樣取到最後迴圈長剛好為n+112/27 12:53
不太了解這個定理是想證明“一定可以找到長度為k+1的cycle”還是“每個cycle的長度
至少大於等於k+1”
※ 編輯: newpuma (42.73.172.102), 12/27/2016 13:10:44
→ Gabino: 一定可以找到長度>=k+1的cycle12/27 13:13
如果是這樣我就明白了
推 Transfat: cycle 長度不一定會>= k+1, 但是一定可以找到長度>=k+1 12/27 13:18
原來如此xd 我還一直糾結xd
→ Transfat: 的cycle, 我是用畫圖出來，然後把每個點編號12/27 13:18
第一個問題 如果是任意三個點而不是特定v1 v2 v3，這樣的話是不是就沒辦法算了？
※ 編輯: newpuma (42.73.172.102), 12/27/2016 13:57:30
→ Gabino: 就多一個步驟去決定哪三個點 12/27 14:23
推 w181496: 任意三個點就要多算取哪三個點吧 12/27 14:24
推 gouya: 第一題，n取2是代表Kn的所有邊數，你可以有要與不要兩種選 12/27 16:42
→ gouya: 擇，所以是2^n取2，包含△123代表那三個邊我一定要，所以剩 12/27 16:42
→ gouya: 下n取2個-3個邊可以選擇要或不要，所以是2^(n取2)-3 12/27 16:42
推 PTTleader: simple graph 不是不能有迴圈嗎 有三角形不就是迴圈了? 12/27 22:24
→ yupog2003: simple graph應該還是可以有迴圈，但不能有self-loop 12/27 22:34
→ gouya: loop=迴圈，cycle=環路，simple graph任兩點至多一邊，可以 12/27 22:58
→ gouya: 有cycle，不能有loop 12/27 22:58
推 PTTleader: 了解!!謝謝 12/28 00:36