偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
如何看待代码中的中文变量名？人脑的图形处理能力相当于什么显卡？
你所知道的最黑的黑科技是什么？
这个不定积分如何化简呢？
如何评价KDD 2021的审稿结果？有哪些亮眼的成果？
你认为程序员的最高境界是什么？
如何学习练习给电脑清灰？
如何烤一块π分熟的牛排？
人的大脑相当于什么水平的 GPU 和 CPU ?
C语言能用指针修改其他程序的地址的值吗？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
如何评价Remove China Apps在印度被追捧？函数连续且任意方向的方向导数存在，那么它可微吗？
为什么微软不把 Windows 下的 API 做得更「安全」些？
集成电路会成为下一个计算机吗？
如何解∫√x^2+a^2dx?
无法理解高等数学怎么办？
反正切函数arctanx平方后的无穷级数怎么证明?
下列证明题（积分不等式）怎么证明?
为什么大学C语言课不用linux的gcc编译器上，而是用vs呢？
深入讨论N卡A卡色彩真的有区别吗？
如果有一个初三学生说他懂微积分，我该怎么应对？
为什么小时候去计算机教室要穿鞋套？
cos²x为什么一定要变换一下？
Windows 在提示 USB 设备被占用而无法弹出时为何不指明进程名？
如何看待中国企业“霸榜”全球隐私技术专利排行榜，目前国内的隐私计算做的怎么样？
准大学生在知乎上看大学专业时，发现所有专业都存在大量劝退，如何在其中筛选出哪些是有用的，哪些是牢骚？
很厉害的程序员都读过CSAPP,SICP,操作系统,算法导论,编译原理这些书吗?
如何计算函数 f(x)=log(x)/x 的 n 阶导数？
为什么物理科普读物读起来津津有味，计算机科普却很枯燥且很少见？
如何用初等函数证明 π 不是有理数？
假设中国人最先开发电脑和设计程序语言，那么各种程序语言会使用汉字吗？
这个用什么方法呢？
一个浮点数到底是怎么被转换为字符串输出？一个浮点数不精确，那么其输出的值是怎么被确定的呢？
大学生如何实现一个数据库？
请问这个人的数学水平如何？
德国与法国哪个国家数学贡献更大？
对神经网络某一层做了小改进，效果却提升显著，可以发论文吗？
在集合论里，对于二元公式φ，如何证明(任意X)(存在{x∈X：φ(x,X)})？
线性代数对于计算机专业的作用是什么呢？
把一个视频文件后缀改成txt，得到是一串代码，那么反过来，有没有一种规律，编写一段代码然后生成视频?