作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 离散 图论×3
时间Sun Sep 15 18:57:12 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1568545034.A.2CE.html
1F：→ DLHZ: 我认为是 {a1, a1, a3}跟一个空集合且都是independent set09/15 20:48
2F：→ DLHZ: 既然他是必须的(可能是一个cut edge等) 那不管怎样一定会被09/15 20:53
3F：→ DLHZ: 算进去 移除或把他算进去都不影响其他部分的运算09/15 20:53
D大不好意思请问您这边的推文在回答1还是3 _
4F：→ DLHZ: 我想了一下 有错还请指点 如果主对角线不设成1的话会造成有09/15 21:00
5F：→ DLHZ: 些情况下算到一半 本来应该adjacent的点下一步却不adjacent09/15 21:00
6F：→ DLHZ: 但似乎都没有说明 主对角线都会是1 但不见得是真的有路径可09/15 21:00
7F：→ DLHZ: 以到自己09/15 21:00
8F：→ DLHZ: 如果以定义下去处理那第一步的矩阵主对角线都应该是0 明显这09/15 21:01
9F：→ DLHZ: 方法就不能用了09/15 21:01
12F：推 DLHZ: 感谢指正09/15 23:08
13F：→ mi981027: 不会不会 我也是参考了D大的推文才敢下结论的09/15 23:57
14F：→ mi981027: 这种不同定义的东西真的很让人模棱两可...09/15 23:57
第三题了解了，感谢D大，mi大
※ 编辑: mistel (223.137.50.75 台湾), 09/16/2019 00:12:38