偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
Linux 系统有没有关于 rm -rf /* 的保护机制？请问这个不定积分有什么比较直观且符合逻辑的推导过程吗？
如何看待大量国产输入法被下架？
球面坐标计算三重积分公式怎么来的？
为什么计算机对人类的冲击要远大于其他科学?
为什么即使世界最知名的软件程序，也无法阻止被人破解的命运？
如何评价Linus Torvalds编写的LINUX内核的技术含量？
如果你有一台超级计算机，你会拿来做什么？
大学专业是计算机科学与技术，大一是否需要买电脑？
如何证明魏尔斯特拉斯函数处处不可导？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
这个级数怎么处理?dos时代的doublespace磁盘压缩现在是windows的什么程序？
fx在R上连续可微，limf‘x=c，且f(x+1)-f(x)=f’(x) 如何证明f’x恒等于c?
为什么身边的人都想学计算机，计算机真的有那么好吗？
有哪些计算机术语的翻译，让你第一次学的时候感到十分别扭？
有哪些计算机术语的翻译，让你第一次学的时候感到十分别扭？
本校是985，要开第二学士学位，值得去读吗？
数学中有哪些让你感到赏心悦目或是震惊的构造手法？
为什么编程语言中没有一种 if，来判断大概率为真（或假）的情况，来提升 CPU 分支预测的速度呢？
最近几年 Intel 处理器的架构进步不大，是遇到了技术困难，还是 Intel 在有意控制节奏？
为什么有些人在报考大学时会放弃某些被普遍认为薪酬高的专业，转而报考同学部的其他专业？
如何证明一个同时以1和π为周期的函数无最小正周期？
最近几年 Intel 处理器的架构进步不大，是遇到了技术困难，还是 Intel 在有意控制节奏？
这个不等式如何证明呢 ？
当年的网络游戏《金庸群侠传 Online》究竟是怎样走向没落的？
要想完全放弃Windows操作系统而使用 Linux需要多少勇气？
高数真的好难，就是不会 打死我也不会…也不是没有数学天赋。当今世界中国大学生不会数学有错吗？
什么情况下被积函数的原函数不能用初等函数表示？怎么判断呢？
造轮子厉害是一种什么样的体验？
如何看待 Google 2004 年在硅谷公路旁一巨型广告牌上贴出的那道数学题用于招聘？
计算机随机生成一个数是不是真的是随机的？
为什么手机最后 1% 的电量有时很耐用？
[x]表示小于x的最大整数已知[√1]+[√2]+[√3]+……+[√n]≤2022，求n的最大值?
微软声明「因超出合理控制范围的情况而导致无法履行或延迟履行其义务，不承担任何责任或义务」，意味着什么？
「贪心算法」的算法思路是什么，它存在什么缺陷？
如何计算如下极限？本人高三刚毕业，正在预习大学知识，希望得到简易的解法。？
所有人都劝退机械，然后又看到大部分人都回答计算机35岁危机严重，大家怎么看？
如何证明魏尔斯特拉斯函数处处不可导？
这个反常积分怎么推导呢?
使用泰勒公式进行估算时，在不同点展开的区别和意义是啥?