偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
图形方面的函数的参数为什么多用浮点？为什么 Win 98 时代风格的安装程序很多都自带一个最大化的蓝／绿色背景？有什么用？
Windows系统控制台初始界面为什么是黑色的？用黑色的意义在哪？
为什么国家将加快人工智能研究生培养？又为什么很多研究生评论人工智能是个大坑呢？
数学必修四最后一课叫简单的三角恒等变换，就想问问是不是还有什么更难的三角函数？
电脑外接 USB，当需要拔出 USB 设备时，直接物理性拔出与「安全退出硬件并弹出媒体」有何差别？
反正切函数arctanx平方后的无穷级数怎么证明?
有一台不会坏掉的电脑，这台电脑上只有vc++6.0，给一个人一亿年的时间，能创造出现在的各种软件吗？
电脑关机再开黑屏2分钟才能看到主板LOGO，重启或者是reset就一切正常。请问是什么原因，如何修复？
你感情最深的电脑是哪一台？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
目前计算机能精确计算小数了么？如何优雅地叫一个程序员给我修电脑呢？
高等数学中学泰勒公式，感觉几何意义很模糊，怎么理解？
科学史上有哪些令人惋惜的遗憾？
如何考虑这个2022贺年题？
为什么大学物理要用积分和微分？
美本本校AI直博概率大吗？
计算机专业到底是不是“围城”？
f(x)=sin(x), x∈[0, π/2] 是不是某个椭圆的一部分？
这个用分部积分法求不出来，应该用什么方法求啊?
三阶魔方公式的最大周期是多少？对应的公式是什么？
计算机专业的学生如何系统的学习前端技术？
用一句话讲微积分是干什么的？
普朗克长度和普朗克时间的存在是否意味这个宇宙可能是虚拟的？
如何不依赖任何外界现成软件和其他计算机设备运行没安装操作系统的电脑？
如何看待全球超级计算机 TOP 500 榜单日本登顶，中国跌出前三？近年中国超算发展现状如何？
GPU 与 CPU 比较，为什么说 GPU 更适合深度学习？
Java 位与0xff 和位或0x00 得到的结果为什么不同?
想问问数学大神们几个问题，学习数学的兴趣来源是什么？数学在生活中的具体应用？
f(x)=sin(x), x∈[0, π/2] 是不是某个椭圆的一部分？
如何看待全民代数几何的现象？
想学计算机系却报错志愿进了数学系，该怎么办？
为什么char *a="xxxxx", *b="xxx"; strcpy(a, b);的用法不行？
一个N*N的矩阵，取值为0或1，有什么好的算法判断一行或一列全为1啊？
这个的n阶导函数怎么求？
你在写程序的时候经历过哪些有趣的事？
可以用ACM/ICPC竞赛成绩来判定一个高校的计算机专业水准吗?
人工智能可以作曲吗？
有没有什么上古的程序代码至今依然没被更替？
如何计算下面这个级数？