偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
如何计算如下极限？本人高三刚毕业，正在预习大学知识，希望得到简易的解法。？为什么 CPU 主频很难超过 4GHz？
如何用数学方法计算灯泡的体积？
是否存在仅在一点可导且该点导数不为0的函数？
为什么会对微积分有种「这个思路不是严格推导出来的，而有一点人为规定的成分」的感觉？
利用微分法计算定积分的结果是真实值吗?
1pb硬盘在未来10年内有可能普及吗？
为什么 0.9 的循环等于 1？
为什么计算机采用补码而不是原码或反码？
为什么开源软件往往都支持Linux/Mac/Windows，而闭源软件往往只支持Win和Mac？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
这个不可测集的外侧度是多少？搜索引擎给出完全相同的两个结果，但一个是广告链接，另一个才是正常结果，你会选择哪个呢？
如何在修电脑时不被宰？
有没有一个函数求导后幂会变高？
如何理解「香农定理」，包含哪些内容，它的发现有什么意义？
IT 圈里有哪些经常被读错的词？
为什么不用汉语来开发一个高级计算机语言直接对应01?汉语的横竖撇捺解构比英语要有效的多啊?
为什么国家将加快人工智能研究生培养？又为什么很多研究生评论人工智能是个大坑呢？
为什么现在有会照相的手机而没有可以通话的相机？
武汉大学计算机学风真的很差吗？
Windows 没有 mac OS 流畅吗，为什么？
有哪些神奇的级数求和？
当今社会真的需要电脑吗?
想提升Excel运算速度，该换SSD还是升级CPU？
为什么C语言整型常量十进制形式的类型与八进制、十六进制的不一样？
怎么解释「监督学习」？
如何通俗地解释一下 TCP/UDP 协议和 HTTP、FTP、SMTP 等协议之间的区别？
抛开一切暂时不可能的因素，若是Linux系统收费或者停止开源，我们现状又会怎么样？
64位操作系统，64位CPU，加SSD硬盘，是不是就可以省去内存，让CPU直接读取硬盘里的数据？
参加 2021 年丘成桐大学生数学竞赛是什么体验？如何评价今年的竞赛？
本科211或985，研究生双非是怎样一种体验？
如何评价游戏主机PS3？
如何评价全球定位系统（GPS）周计数器即将第二次归零这一事件？
为什么不用汉语来开发一个高级计算机语言直接对应01?汉语的横竖撇捺解构比英语要有效的多啊?
《三体》中让你印象最深的科幻点子有哪些？以及他们的科学背景？
笔记本电脑的屏幕素质有啥用？
程序员的价值会随工作经验增多而增长么？
开发人员如何构建自己的学习笔记系统？
这怎么求？ ？
如果从来不用IE，还有必要打上微软发布的IE安全补丁么？