偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
为什么 CPU 的浮点运算能力比 GPU 差，为什么不提高 CPU 的浮点运算能力？如何计算如下极限？本人高三刚毕业，正在预习大学知识，希望得到简易的解法。？
为什么保护模式只能向更高特权级代码段转移控制？
圆周率 π 的这个连根式展开公式怎么证明？
国外名校计算机女博士生的生活是怎样的？
推荐算法岗是否存在严重人才过剩?
程序计数器（Program Counter）是一个实际存在的寄存器吗？
学计算机，不太喜欢编程，有哪些出路？
显示器显示的黑色是直接让关闭那个区域的色彩显示吗？
我是一个计算机学院的学生，用4000多电脑够用了么？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
究竟如何理解 dx？如何判别一个方程所表征的曲线是否封闭？
人工智能翻译技术大概还需要多少年才能达到基本成熟的水准？
这个不定积分如何化简呢？
高数问题求解，不懂为什么做法不可行？
这个不定积分如何化简呢？
人工智能是不是走错了方向？
y=sinω0x在［-π/2，π/2］的傅里叶变换后的函数到底是什么？
在信息学竞赛中，你见过哪些"这都能AC!?"的题?
「贝塞尔曲线」有哪些作用和特点，该如何正确使用？
在 linux 中，用 c 语言如何判断 yum 源是否配置好？
有没有这样的函数，其一阶导等于1，二阶导等于2，三阶导等于3，n阶导等于n，n一直趋于无穷大？
如何计算下面这个级数？
为什么这个世界是混沌无序的，而人们发现的用于解释这个世界的原理却都是有序简洁而优美的？
「计算」会改变信息量么？
不用直接观察的方法怎么由倒数求原函数？
ISP给的100M带宽到底是怎么算的?
这个用分部积分法求不出来，应该用什么方法求啊?
如何反对同学这样解释无理数和有理数一样多？
未来会不会出现这样的编程语言？
设计师应该学编程吗？
如何证明呢？
为什么高质量计算机书籍几乎都是外国人写的？
到了 2022 年，人工智能有哪些真正可落地的应用？
有哪些c++的书推荐？
请教如何计算这个反常积分？
晾一件刚洗的衣服，有可能计算出每滴水落地的时间间隔吗？
如何求和这个级数?
如何判断这个反常积分的判敛性？
下面的结论是否正确？