偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
所有人都劝退机械，然后又看到大部分人都回答计算机35岁危机严重，大家怎么看？请问一下如何求解下面这个积分的值？
化工硕士在读是否该转行计算机？
对于很多知乎大佬说的随便一个数学系的学生就能秒杀考研数学？
如果让你重新开始学计算机，你的学习路线会是怎么选择?
请问这道求和极限题应该怎么处理？
为什么在数轴上随便取一个点，一定取到的是无理数？
「C++ 早就过时了，大部分写工程不用 C++，学习这个语言只是为了竞赛」的观点是否正确？
如何求和这个级数?
无穷大可以比较大小，有没有一个量来描述无穷大的大小？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
量子计算机的出现会给实际生活带来怎样的改变？如何用数学严谨证明 宾语前置=前置宾语?
为什么四进制在计算机科学中不常见？
为什么我们总能听到计算机图形学，而很少听到计算机音频学之类的？
历史上，AMD超越过Intel吗？
你看过/写过哪些有意思的代码？
非高中oi选手在清华计算机系就读是什么体验？
新买了笔记本电脑后，需要进行哪些基本的设置和下载？
高考数学导数题是怎么命制的？
非计算机专业学生怎么走上计算机技术之路？
这个不等式缩放怎么证明？
为什么对于一阶、二阶导，人们通过直观可以轻易地认识，三阶及以上就很难直观地认识了？
要想完全放弃Windows操作系统而使用 Linux需要多少勇气？
为什么计算机无法精确计算小数？
这个第二型曲面积分用书上的方法怎么做不出正确结果，第二型曲面积分转化成重积分怎么理解？
计算机还能火多久呢?
高中数学有必要学习一些高数知识吗?
为什么高等教材中极少出现 ÷（除号）？
你写过哪些比较酷的十行以内的 Matlab 代码？
Cpu访问cache未命中，是否还需要访问一次cache? ?
计算机领域有哪些经典的典故或笑话？
为什么会对这个用三角函数的那个公式？
如何证明函数单调有界判别法？
非常硬核的数学题，大家能否解出？
一个函数的不定积分存在有哪些必要条件或者充分条件？
python的numpy向量化语句为什么会比for快？
人工「神经网络」技术在信息处理上有何特点，工作原理是什么？
如何看待王垠的2020新年寄语？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
为什么没有显存条？