偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
如何评价姜新文老师提出的NP=P这篇文章？如何证明牛顿―莱布尼兹公式？
一头雾水计算机小白求问：软件工程师（程序员）究竟干什么的？
本科俄亥俄州立大学和马里兰大学选哪个好？
为什么手机最后 1% 的电量有时很耐用？
数学上积分结果的本质是什么？
西方学习编程的学生训练打代码时每年要敲坏多少个键盘？
如何对R中每一行数据求和？
人们专门弄了一个自然对数函数的底数 e，是为什么？
如何证明韦达给出的圆周率的计算公式？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
泊松换元公式有直接用二重积分换元而不变为曲面积分的方法吗？为什么在应用上高斯消元法很少被用来求逆矩阵?
想学计算机系却报错志愿进了数学系，该怎么办？
从语言学的角度，为什么拉丁字母比汉字更适合编程语言？
Linus 真心诚意地夸过哪些人或技术？
应用统计专业是虚假需求吗？
计算机系如何写出优雅的实验报告？
IT 圈里有哪些经常被读错的词？
为什么高质量计算机书籍几乎都是外国人写的？
如何计算下面的级数？
读计算机的博士未来出路在哪里？
以目前的技术对于恐龙外形模拟或复原的精确度能达到多少？
为什么网上关于C#的资源那么少呢？
如何看待方舟编译器于 2019 年 8 月 31 日开源？
这道有理数不定积分怎么算?
为什么编程语言对异步编程都是很晚近才开始支持的？
计算机中，假设键盘同时按下两个键，会优先生效哪一个？
为什么条件收敛的级数重排后，即使收敛，也不一定收敛于原来的级数和？
有没有两个不相等的数 a 和 b，满足 a 的 b 次幂等于 b 的 a 次幂？
IOI国际金牌是什么水平，在此之上更高的水平是什么样的？
在极限和导数证明中引入无穷小α的意义是什么？
请问这道重积分的题如何做？
MYSQL 什么时候返回空，什么时候返回NULL,为什么这两条语句返回结果不一样？
为什么大多数程序主函数成功时都return 0; 不return 1; ？
Deep Learning 的专家如此急缺，它难在何处？
如何看待南开大学一同学一边走路一边开着电脑写代码？当代大学生学习现状是怎样的呢？
请问这个式子有没有简便算法（写法）？
active directory是不是很难学？
如何证明魏尔斯特拉斯函数处处不可导？
小平邦彦《微积分解析入门》第五页怎么等于1?