[理工] 離散 圖論×3

看板Grad-ProbAsk作者 (Mistel)時間4年前 (2019/09/15 18:57), 4年前編輯推噓2(2推 0噓 12→)
留言14則, 2人參與, 4年前最新討論串1/1
1. https://i.imgur.com/S9Zu1X7.jpg
請問第八題，我取一個K3,1的bipartite再取a1,a2,a3為子圖 那a1,a2,a3有符合題目嗎？ 2. https://i.imgur.com/d2arjLJ.jpg
計算最小生成樹數量部分 為什麼畫線部分包含e的生成樹個數是N(G‧e)？有點難想像 3. https://i.imgur.com/0qDmkcq.jpg
請問演算法定義的遞移閉包跟離散的遞移閉包定義不一樣嗎？ 想知道為什麼(1,1)也是這個圖的遞移包 謝謝考題版 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.50.75 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1568545034.A.2CE.html
→
09/15 20:48, 4年前 , 1F
我認為是 {a1, a1, a3}跟一個空集合且都是independent set
09/15 20:48, 1F
→
09/15 20:53, 4年前 , 2F
既然他是必須的(可能是一個cut edge等) 那不管怎樣一定會被
09/15 20:53, 2F
→
09/15 20:53, 4年前 , 3F
算進去 移除或把他算進去都不影響其他部分的運算
09/15 20:53, 3F
D大不好意思請問您這邊的推文在回答1還是3 _
→
09/15 21:00, 4年前 , 4F
我想了一下 有錯還請指點 如果主對角線不設成1的話會造成有
09/15 21:00, 4F
→
09/15 21:00, 4年前 , 5F
些情況下算到一半 本來應該adjacent的點下一步卻不adjacent
09/15 21:00, 5F
→
09/15 21:00, 4年前 , 6F
但似乎都沒有說明 主對角線都會是1 但不見得是真的有路徑可
09/15 21:00, 6F
→
09/15 21:00, 4年前 , 7F
以到自己
09/15 21:00, 7F
→
09/15 21:01, 4年前 , 8F
如果以定義下去處理那第一步的矩陣主對角線都應該是0 明顯這
09/15 21:01, 8F
→
09/15 21:01, 4年前 , 9F
方法就不能用了
09/15 21:01, 9F
推
09/15 22:49, 4年前 , 10F
09/15 22:49, 10F
→
09/15 22:50, 4年前 , 11F
09/15 22:50, 11F
推
09/15 23:08, 4年前 , 12F
感謝指正
09/15 23:08, 12F
→
09/15 23:57, 4年前 , 13F
不會不會 我也是參考了D大的推文才敢下結論的
09/15 23:57, 13F
→
09/15 23:57, 4年前 , 14F
這種不同定義的東西真的很讓人模稜兩可...
09/15 23:57, 14F
第三題瞭解了，感謝D大，mi大 ※ 編輯: mistel (223.137.50.75 臺灣), 09/16/2019 00:12:38
‣ 更多 mistel 的文章
文章代碼(AID): #1TVXaABE (Grad-ProbAsk)