偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
Linux中使用sudo产生文件的所有者究竟是？该如何正确看待c中的字符串常量？
有哪些程序员特有的技能？
分析、抽象代数这种课对搞 data science 帮助大吗？
球面坐标计算三重积分公式怎么来的？
今年刚上岸，跟一个老师学习了一段时间后，可以换老师吗？
如何证明这两个微分方程具有相同的轨线？
如何对R中每一行数据求和？
CPU 能否和内存集成在一起？
伟大的数学家是如何培养的呢？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
28岁可以通过考研二战top2的计算机专业改变人生吗？如何证明韦达给出的圆周率的计算公式？
计算机行业领先的公司大多在美国，Linux为什么却是芬兰人发明的？
装满的硬盘中是 1 多还 0 多？
计算机开发岗和算法岗都有些什么区别？
马上计算机研一，想问一下机器学习、深度学习…大家都是怎么入门的？
认为大学基础物理比数分简单很多，是说明自己更擅长学物理吗？
这个9题不等式右边怎么证明呢？
这个积分可以算吗，怎么算？
日本科技那么发达，为何不在PC的CPU领域和Intel、AMD竞争？
为什么 Windows 上还没有普及 64 位的软件？
「C++ 早就过时了，大部分写工程不用 C++，学习这个语言只是为了竞赛」的观点是否正确？
为什么要开源？
cpu的核心模式和用户模式是不是就是root和不root的区别？
南开大学软件学院怎么样？
为什么很多人喜欢动不动就重装系统？
为什么多方安全计算（或者隐私计算/联邦学习）在中国这么火？
为什么现在网上普遍低估公务员的收入?
机械类的优秀答主为什么那么少？
为什么在应用上高斯消元法很少被用来求逆矩阵?
哪些看似毫不相干的事物具有相同的数学原理？
HDMI传输无损信号，音画质会有区别么？
如何看待微博女权发起「拒绝男程序员」活动？
这道有理数不定积分怎么算?
如何计算如图极限？
国外名校计算机女博士生的生活是怎样的？
一道难题求助大佬?
计算机语言是如何做到靠0和1就表达出这么多东西的?
在信息学竞赛中，你见过哪些"这都能AC!?"的题?
如果把 AES、DES 等各种加密算法排列组合，然后对一明文进行逐一加密，这样的组合加密算法强度大吗？