[理工] 離散 圖論

看板Grad-ProbAsk作者 (還很新)時間9年前 (2016/12/27 10:12), 9年前編輯推噓14(14推 0噓 17→)
留言31則, 8人參與, 最新討論串7/16 (看更多)
1. n個點包含三角形(v1,v2,v3)的simple graph為什麼是2^(n取2 - 3) 我知道n個點可以決定n取2個邊，再分可取可不取，但是包括三角形v1v2v3，代表有3個邊 不取，為什麼會是在次方扣3？ 2. 每個點的degree至少為2保證一定有cycle這個定理我可以瞭解，因為有進入邊一定有出來 邊 但是每個點degree至少為k時，為什麼保證cycle長>=k+1，證明怎麼樣也看不懂，為什麼 抓一點vk(以degree當做點編號是為了什麼？) 3 連通圖，|E|>=|V|-1 這個證明我看的懂，是用數學歸納法推出來的，但是我拼命在想什麼情況下剛好|E|=|V|- 1 是一個剛好由起點拜訪到終點的walk嗎？ 比如5個點的圖{v1,v2,v3,v4,v5}四個邊，這樣我的想法有想錯嗎？(因為這樣每個點都可 以拜訪到其他點) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.237.32 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482804771.A.6DA.html ※ 編輯: newpuma (223.137.237.32), 12/27/2016 10:13:42
推
12/27 10:19, , 1F
3無迴圈連通圖, 也就是tree
12/27 10:19, 1F
推
12/27 10:41, , 2F
1.應該是一定要先選那三條邊 剩下n取2 -3條可取可不取 這
12/27 10:41, 2F
→
12/27 10:41, , 3F
樣就包含三角形了
12/27 10:41, 3F
推
12/27 10:44, , 4F
1.你都講說可取可不取，那我要取一個三角形不就等於一定
12/27 10:44, 4F
→
12/27 10:44, , 5F
要取三個便，所以扣掉3。我是這樣理解，有錯請告知
12/27 10:44, 5F
推
12/27 10:48, , 6F
2 ,每個人deg至少k 所以大家至少k個鄰居
12/27 10:48, 6F
→
12/27 10:49, , 7F
從點v0開始 每取一個其他人deg就-1
12/27 10:49, 7F
每取一個，其他人的deg就-1 那不就代表每個點都彼此相連嗎 意思是指至少我能保證一條v1至vk再到v1的cycle嗎 還是覺得很抽象，如果有十個點，deg最少為5好了，不也能找到長度為3的cycle嗎？(v1v 2v3v1) 請問這個證明的在證最大的cycle嗎？
→
12/27 10:49, , 8F
取完k個結束 迴圈長=點數+1
12/27 10:49, 8F
→
12/27 10:50, , 9F
這是概念 嚴謹證明要再翻一下
12/27 10:50, 9F
推
12/27 10:52, , 10F
1是一定要有某三角形abc所以-3
12/27 10:52, 10F
※ 編輯: newpuma (42.73.172.102), 12/27/2016 12:30:10
推
12/27 12:45, , 11F
(3)的話取一個Tree 就是graph 且|E|=|V|-1
12/27 12:45, 11F
瞭解
→
12/27 12:45, , 12F
(1)和(2) 有沒有完整一點的描述啊，有點看不懂想要問什
12/27 12:45, 12F
定理跟筆記這樣寫，我也想找完整一點描述，比較好理解QQ
推
12/27 12:45, , 13F
10個點每人5個鄰居 確定至少可以取到五點形成迴圈 所以
12/27 12:45, 13F
→
12/27 12:45, , 14F
大小是6
12/27 12:45, 14F
推
12/27 12:47, , 15F
2的問題應該是一張圖deg(v)最小為k ,v屬於G, 則必有一cy
12/27 12:47, 15F
→
12/27 12:47, , 16F
cle長為k+1
12/27 12:47, 16F
推
12/27 12:53, , 17F
我那個說法有點太簡易了 概念是最差的狀況為每次取的點
12/27 12:53, 17F
→
12/27 12:53, , 18F
都是前a個的鄰居 這樣取到最後迴圈長剛好為n+1
12/27 12:53, 18F
不太了解這個定理是想證明“一定可以找到長度為k+1的cycle”還是“每個cycle的長度 至少大於等於k+1” ※ 編輯: newpuma (42.73.172.102), 12/27/2016 13:10:44
→
12/27 13:13, , 19F
一定可以找到長度>=k+1的cycle
12/27 13:13, 19F
如果是這樣我就明白了
推
12/27 13:18, , 20F
cycle 長度不一定會>= k+1, 但是一定可以找到長度>=k+1
12/27 13:18, 20F
原來如此xd 我還一直糾結xd
→
12/27 13:18, , 21F
的cycle, 我是用畫圖出來，然後把每個點編號
12/27 13:18, 21F
第一個問題 如果是任意三個點而不是特定v1 v2 v3，這樣的話是不是就沒辦法算了？ ※ 編輯: newpuma (42.73.172.102), 12/27/2016 13:57:30
→
12/27 14:23, , 22F
就多一個步驟去決定哪三個點
12/27 14:23, 22F
推
12/27 14:24, , 23F
任意三個點就要多算取哪三個點吧
12/27 14:24, 23F
推
12/27 16:42, , 24F
第一題，n取2是代表Kn的所有邊數，你可以有要與不要兩種選
12/27 16:42, 24F
→
12/27 16:42, , 25F
擇，所以是2^n取2，包含△123代表那三個邊我一定要，所以剩
12/27 16:42, 25F
→
12/27 16:42, , 26F
下n取2個-3個邊可以選擇要或不要，所以是2^(n取2)-3
12/27 16:42, 26F
推
12/27 22:24, , 27F
simple graph 不是不能有迴圈嗎 有三角形不就是迴圈了?
12/27 22:24, 27F
→
12/27 22:34, , 28F
simple graph應該還是可以有迴圈，但不能有self-loop
12/27 22:34, 28F
→
12/27 22:58, , 29F
loop=迴圈，cycle=環路，simple graph任兩點至多一邊，可以
12/27 22:58, 29F
→
12/27 22:58, , 30F
有cycle，不能有loop
12/27 22:58, 30F
推
12/28 00:36, , 31F
了解!!謝謝
12/28 00:36, 31F
‣ 更多 newpuma 的文章
文章代碼(AID): #1OOSuZRQ (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 16 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共16篇)
‣ 更多 newpuma 的文章
文章代碼(AID): #1OOSuZRQ (Grad-ProbAsk)