偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
数字信号在物理层传输时，本质上是数字信号还是模拟信号，为什么？为什么32位机之后直接发展64位机，而没有33位机或者48位机？
理工男，我感觉 win10 挺好用的，一点不卡，为什么有那么多人买Macbook 呢?
计算机科学能辉煌多久？
请问这个人的数学水平如何？
我该放弃.NET吗？
Linux 图形界面的显示原理是什么？
Power Point 应该是PPT 还是ppt 还是PPt？
有哪些新概念电子产品值得推荐？
什么叫做学计算机有天赋？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
计算机领域有哪些「将错就错」被沿用至今？精通 C++ 是种怎样的体验？
C++ 有多难？
如何计算下面无穷级数的值？
如何研究e^x·lnx和e^x/lnx的单调性？
买到一台新笔记本电脑之后要做些什么？
现在的图灵测试体系能否发现“故意不通过图灵测试来隐藏自己的人工智能”？
这两道的极限怎么求?
信息技术中文字到底是什么？
「杀毒软件之父」75 岁约翰·迈克菲死于西班牙监狱中，他做出了哪些贡献，如何评价他的一生？
计算机科学与技术专业的学生要怎样做才能避免成为低级的码农？
「贪心算法」的算法思路是什么，它存在什么缺陷？
为什么小时候去计算机教室要穿鞋套？
如何运用积分的知识去解这一道数学分析的题目？
该如何正确看待c中的字符串常量？
想裸写编译器，除了编译原理外还有那些资料可以参考？应该从什么开始写起？（用c/c++）？
表哥说机械比计算机经管都好，如何看待他的言论?
计算机系学生应该怎样正确管理自己的电脑？
如何向完全不懂编程的小伙伴解释「程序写死」？
如何计算此多重积分不等式？
32位的cpu只能寻址4GB的内存空间，那么硬盘,flash这些存储设备是如何寻址的的？cpu怎样读取其中某个地址的数据？
小平邦彦《微积分解析入门》第五页怎么等于1?
在线教育平台上有哪些让你相见恨晚的计算机或互联网课程？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
瞬间之中真的包含永远吗，瞬间之中怎么包含永远？
大一学生，刚开始学习编程，但感觉自己并没有天赋怎么办？
AI 20年内将会给我们的生活带来什么改变？
硅谷的软件工程师收入情况如何？
互联网世界中有可能诞生类生物的东西吗？
是否存在一个级数的∑an使得任何其他级数,只要通项大于它的都发散,小于的都收敛?