偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
弧的长度与弦的长度之比的极限为1，能严格证明吗？转行去日本从事计算机工作现实吗?
为什么物理科普读物读起来津津有味，计算机科普却很枯燥且很少见？
格林公式的几何意义是什么？
计算机执行一条指令要多长时间？
编程应该纳入高考吗？
211化学大四本科生想考研转金融或者计算机，金融零基础，计算机只学过C语言。正在纠结，希望给点建议？
腾讯阿里顶级工程师和普通 985 博导，谁的计算机水平更高，各自强项都是什么？
复变函数中，z=0是函数f(z)=1/√z 的什么奇点，留数怎么算？
这个极限怎么写?
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
奥赛生做高考题是种怎样的体验？不等式e^x＞1+x x≠0怎么证明？
请问为什么无穷个无穷小量的乘积不一定是无穷小量？
请问一道难度很大定积分，有什么好的解法吗，如下？
如何评价知乎用户@逍遥自在？
假设中国人最先开发电脑和设计程序语言，那么各种程序语言会使用汉字吗？
给RISC-V设计自定义指令，有什么需要注意的事情吗?
元宇宙和数字孪生的异同是什么？
如果“P=NP”得到证明，意味着什么？
如果计算机是中国发明的，键盘应该是怎样的？
为什么 0.9 的循环等于 1？
突然产生一个想法，本人是学计算机的一个妹子，录视频会有人看吗？
人工智能是不是走错了方向？
如何证明 sin(a+b)＝sina·cosb＋sinb·cosa？
大牛Bengio 团队最新的研究和我自己之前的研究成果重复了，应该怎么办？
为什么很多IT公司不喜欢进过培训机构的人呢？
一道复变函数证明题怎么做？
如何通俗地解释一下 TCP/UDP 协议和 HTTP、FTP、SMTP 等协议之间的区别？
为什么计算机科学专业背景的人喜欢黑机器学习？
学计算机，不太喜欢编程，有哪些出路？
教材上说铁路订票系统是实时操作系统，可是服务器的Linux不是分时操作系统吗？
如何证明求导是线性变换?
「闰秒」会对 IT 行业造成多大影响？有什么好的解决方法？
有哪些程序员才懂的梗？
你写过的自己觉着最牛的黑程序是什么？
机器学习到底是什么，如何使用这项技术？
如何在公网下载学术文献？
洛必达法则为什么会存在失效的情况？
sinx无限嵌套的图像到底会怎么样?
用计算器打 CS，实际上真的可以实现吗？