偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
学习 Linux 有哪些好处？为什么计算机科学如密码学喜欢用 Alice 和 Bob 举栗子？
是否存在仅在一点可导且该点导数不为0的函数？
人们专门弄了一个自然对数函数的底数 e，是为什么？
为什么图片反复压缩后普遍会变绿，而不是其他颜色？
如何让两台电脑同步接收到单个键盘的指令？
为什么图片反复压缩后普遍会变绿，而不是其他颜色？
为什么 .NET 平台在技术上远强过 Java，而多数大公司却仍采用后者？
柯西审敛原理是证得收敛还是一致收敛?
如果从来不用IE，还有必要打上微软发布的IE安全补丁么？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
sinx求导为什么是cosx？泰勒公式展开到任意阶，都不用管后面的高阶无穷小项么？
电子（EE）专业犹豫要不要研究生转计算机专业（CS）？
如何思考这道定积分不等式？
为什么总有一些人推荐计算机学生把重点放在高数和线代？
一头雾水计算机小白求问：软件工程师（程序员）究竟干什么的？
Linux下有哪些给你带来「快感」的软件？
请问这个级数是怎么求和的?
丁同仁常微分方程第二版2.2第五题怎么解？
为什么会对这个用三角函数的那个公式？
在耳机相同的情况下，电脑的音质会比不上 CD 机吗？为什么？
Node.js是用来做什么的？
民科是不是很少拿计算机科学开涮？为什么？
大学专业是计算机科学与技术，大一是否需要买电脑？
请问这个圆旋转所形成的立体体积为什么这样计算？
「初等函数在其定义域内必连续」的说法是对是错，为什么？
为什么数列可以用不动点法，到底表示什么意思啊？
这个极限怎么做呢？
为什么 CPU 不做成可以换插槽的，或者把除内存插槽 PCIe 之外的东西都外置？
为什么软件要自动安装在系统盘呢？
导数最早在明朝王文素算学宝鉴，为什么所有的教材都不提，而将一切归功于牛顿莱布尼茨？
请问这个不等式的证明思路是怎样的？
请问下面两个极限问题如何解决？
Yann LeCun、Geoffrey Hinton或Yoshua Bengio能得图灵奖吗？
这条语句违背了C++哪个原则？
CS专业工资那么高为什么大家不都去学CS？
如何评价某985老师所说的「C语言至少学10年才能懂」?
计算机专业真的如此完美吗？
以π指代圆周率是偶然的约定俗成还是特别的另有深意？
不定积分中dx和定积分的含义是什么？