偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
在计算资源有限的情况下，有什么深度学习的选题可以推荐/避免？计算机专业的学生如何系统的学习前端技术？
这个不可测集的外侧度是多少？
未来的主流半导体材料会是什么？
1，2，3，…，n。去掉1，将2挪在n后；去掉3，将4挪在2后，按此规律进行下去，最后留下的数字是？
怎么积∫[0, 1] ln(1＋x²)/(1＋x) dx？
python是用C实现的，Java是用C++实现的，那为什么不直接用C或C++呢？
当年的网络游戏《金庸群侠传 Online》究竟是怎样走向没落的？
什么情况下比值判别法失效？
计算机标准时间中“上午11:59”和“上午12:01”之间隔了多长时间？是否有bug？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
USB芯片到底完成了哪些工作？计算机是如何在物理层面实现“递归”的？
回顾人类历史，计算机的出现和进化对人类的进程造成了多大的影响？
为什么不把路由器集成在计算机里？
江苏一博士“虎爸”拳脚相加逼六七岁儿女学高数。如何评价这位父亲的做法？
如何看待 CMU 新开设的 AI 专业？
格林公式为什么不对称啊？
在计算机和芯片技术出现前，地铁怎样按里程计费售票？
有人真正理解数列极限的定义吗？
这道积分题如何计算？
有哪些只有程序员才能 get 到笑点的故事？
人工智能达到了什么程度？
为什么中国的计算机教育这么落后?
这两个级数该怎么解答？
如何看待 NOIP2020 某选手通过修改输入文件获得了第三题的满分？
国内研究生不小心跟了一个水货老师是什么样的体验？
学物理为什么会觉得计算机很难？
腾讯阿里顶级工程师和普通 985 博导，谁的计算机水平更高，各自强项都是什么？
如何看待 HTTP/3 ？
为什么Windows更新需要多次重启？而Linux不需要？
高数问题求解，不懂为什么做法不可行？
为什么上微机课要穿鞋套？
计算机大一学生见过的最牛逼的学长或学姐可以达到什么水平？
'如何计算该定积分?
求极限limn→∞∫n→2n cosx/xdx？
积分不就是找反导数吗，为什么还有稀奇古怪的积分技巧？
我想找个程序员男朋友，请问上哪去找好呢？
计算机大牛们，看C++有关书籍是不是一遍就看懂了，总感觉自己笨，有些地方需要看几遍才懂?
有哪些古代军事难题可以用物理公式、化学公式或高等数学解决的？
想问问数学大神们几个问题，学习数学的兴趣来源是什么？数学在生活中的具体应用？