偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
怎么计算概率积分 ∫[0, +∞) (e^(-x²))dx？一千块能做什么提升？
大一被调剂到计算机，但对电脑根本不了解，就只会上上网聊聊天，连入门都算不上，现在应该怎样入门？
凭现在的技术能做出以假乱真的游戏画质吗？
身为一个会做饭，热爱美食的程序员是一种怎样的体验？
球面坐标计算三重积分公式怎么来的？
黑箱里有n个小球，编号为1, 2, ..., n，随机抽一个球的号码是10，能获得什么关于n的信息？
微软有没有可能为Linux系统开发桌面环境？
为什么计算机科学专业背景的人喜欢黑机器学习？
华为出售 X86 服务器业务，你怎么看？会对华为产生哪些影响？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
大学四年如何成为世界级软件工程师？数学这种东西也许有用，但是，如何在现实生活当中用到它？
计算机系统是如何显示一个字符的？
EDA软件(与IC设计相关的如ISE.etc)的发展趋势?
请问这道极限题怎么做?
如何解这个数列的通项公式？
美本本校AI直博概率大吗？
有哪些有趣的或者是反常识的数学问题？
计算机能不能真正意义上存储一个无理数？
此题应该怎么解？思路是什么？
计算机系为什么要学数据库原理和设计？
底下那步怎么转化的啊 是忽略了吗?
我这个数有葛立恒数的大吗？
抛物线为何属于圆锥曲线？
多核之后，CPU 的发展方向是什么？
C 语言是否需要改进，甚至重新设计一门语言取代 C 语言？
反正切函数arctanx平方后的无穷级数怎么证明?
关于这个函数项级数，有没有一些研究成果？
如何简明地解释曲率（curvature）？
请问这道不定积分的题目怎么做？
如何看待代码中的中文变量名？
9.99循环这个数存不存在，如果存在，那么它是整数还是无限循环小数？
B 格最高的的数学或物理学公式是什么？
向各领域业内人士求助，有什么注意事项？
AI 算法在芯片设计方法学和 EDA 工具中有哪些应用和潜力？
为什么会对微积分有种「这个思路不是严格推导出来的，而有一点人为规定的成分」的感觉？
”返回在函数内malloc的内存是安全的，但是容易造成问题，最好的做法是返回传入的指针。“怎么理解？
如何评价南方科技大学2020届计算机系毕业去向？
学习编译原理有什么好的书籍?
0 的 0 次方等于 1 吗？怎么证明？