偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
如何构造一个初值，使得这个数列是发散的?美国CS授课硕士应该重排名还是重城市？
CPU 只能进行数值运算，那么计算机是怎么显示出字符的？
网站如何升级成https的？
如何看待全民代数几何的现象？
圆周率 π 的这个连根式展开公式怎么证明？
碳纳米管会代替传统硅材料成为更优质的计算机电子元件材料吗，现在大规模应用的阻碍是什么？
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
视觉算法的工业部署及落地方面的技术知识，怎么学？
C++ 有多难？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
黑客有可能攻击已经关机的电脑吗（有电源，网线连着）？如何确定该双变量函数的所有间断点？
98年586电脑多少钱？
C 语言自带函数返回值为指针类型的数组为什么不需要释放内存?
读 CS PhD 之前没有工业界经历真的没关系吗？
微积分中的隐函数定理为什么那么重要？
N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？
大容量移动硬盘的选择，有电源是否很重要，买8T的稳定吗？
运维是计算机行业里技术含量最低的岗位吗？
高中生提前接触计算机好吗？
这个极限咋算？
为什么 Linux 指针越界时程序会立即被中断，而 Windows 不会？
去互联网公司/软件公司(技术岗) 实习要注意哪些问题？
程序计数器（Program Counter）是一个实际存在的寄存器吗？
网传华为研发出属于我国的编程语言「仓颉」，这是真的吗？这意味着什么？
如何解决这个数学分析问题？
能不能出一道很难的数学题，答案是 629，宿舍当门牌用？
有哪些结合医学、计算机、人工智能的研究领域？
如图，这道题中的隐函数为什么可以设y=tx？
你认为程序员的最高境界是什么？
有哪些诗与数学有关？它们的作者又是谁？
晾一件刚洗的衣服，有可能计算出每滴水落地的时间间隔吗？
理工男，我感觉 win10 挺好用的，一点不卡，为什么有那么多人买Macbook 呢?
如果有人想走遍中国所有的省级行政区（含港澳台），总路程最小可以是多长？
大学生如何实现一个数据库？
这类型的定积分怎么求解呢，第一个我只知道用那个积分中值定理写，第二个呢？
Linux的ls -l命令输出的第二列的数字代表什么?
如何看待现在小学生学习微积分？
底下那步怎么转化的啊 是忽略了吗?
这个高阶导数怎么写?