偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
如何理解 Farkas 引理？有哪些比 Macbook 性价比高的笔记本？
有哪些程序员才懂的梗？
美本计算机 去 cmu-sv 卡内基梅隆硅谷校区 读 Software Management怎么样？
李林高数辅导讲义这题怎么算的?
当人工智能复杂到超出任何人类的理解能力时应该如何管理？
大一计算机专业怎么利用好寒假?
大型网络公司有没有在西北开分公司的必要？
有哪些算法惊艳到了你？
是否存在仅在一点可导且该点导数不为0的函数？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
如何看待武大 94 年博士生入选华为「天才少年」，最高年薪达 201 万元？此项目对华为意味着什么？一天做完一百道积分题是一种什么感觉？
在 Minecraft 中是否能搭建出足够运行 Minecraft 游戏本身的计算机？
能分享一道如果“注意不到”就出不来的数学题吗？
子网掩码与ip地址有实际关系吗？
是否存在这样一个非常数函数，定义域是实数集或其子集，值域仅为有理数集子集？是否有这样的函数是连续的呢？
大学学高数需要几个脑子？
学习计算几何是什么样的体验？
李林高数辅导讲义这题怎么算的?
要怎么处理这个反常积分？
请问这道题用麦克劳林该怎么做?
如何判断下面这个级数的敛散性？
如何看待复旦大学重点实验室多篇论文被质疑抄袭美国教授?
零基础如何学习计算机图形学？
人工智能达到了什么程度？
怎么计算这个广义积分∫[1-x(x^4+1)^(-1/4)]dx,从0到无穷大?
精通 C++ 是种怎样的体验？
1/3+1/6=计算机是如何得出0.5的?
计算机大二分方向，人工智能和网络安全哪个好？
牛顿莱布尼兹公式指出求导和积分互为逆运算。从几何的角度看求斜率和求面积似乎并没有直接联系？
这道数列极限有简单点的做法吗？
如何证明以下关于ζ(2n)的式子？
「闰秒」会对 IT 行业造成多大影响？有什么好的解决方法？
为什么国内技术社区的影响力越来越弱呢？
圆周率 π 的这个连根式展开公式怎么证明？
如果计算机是中国发明的，键盘应该是怎样的？
如何看待 NOI 金牌、清华姚班毕业张昆玮放弃 Google 工作，选择回到老家二本当人民教师？
UEFI 引导与 BIOS 引导在原理上有什么区别？
linux如何赋予用户sudo权限？
如何求这个复杂的函数的不定积分?