偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
名校计算机专业出来的只能当苦逼的程序员吗?如果计算机是中国发明的，键盘应该是怎样的？
随着各个领域越来越多的人都开始学习编程，计算机专业的人优势在哪里?
计算机如何理解图像?
如何思考这道定积分难题？
Ln(-3-3i)等于多少？
跟计算机有关的专业学什么好？
请问一道难度很大定积分，有什么好的解法吗，如下？
为什么埃式筛法的时间复杂度是O(nloglogn)？
为什么连离我很远很远的服务器会很慢？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
如何求这个复杂的函数的不定积分?怎么找到姚班或者ACM班或者其他高校计算机巨强的男生做男朋友呀?
照亮一个球面至少需要几个点光源？
为什么学了一个学期的c语言，感觉一直都是在用代码去做一些简单的数学题，没有什么实际用途？
为何从一元五次方程开始就没有由有限次加、减、乘、除、开方运算构成的求根公式了？
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？
就代码能力和开发经验来说，姚期智是不是根本就不如稍微有三到四年开发经验的程序员？
你心中希望的本科CS教育应该是怎样的?
学计算机的朋友们有时候一个错误几小时才会弄清楚，会崩溃吗?
如果把电脑主机的两个 USB 接口用一根数据线连起来，会发生什么？
工科双非考博，有高质量论文过不了名校申请审核？
为什么编程语言中没有一种 if，来判断大概率为真（或假）的情况，来提升 CPU 分支预测的速度呢？
AI 20年内将会给我们的生活带来什么改变？
计算机专业未来就业方向有哪些？
程序（软件）打开文件的工作原理？
你靠哪些讲解学会了曾经怎么也学不会的算法？
怎样评价光电领域本科浙大、硕博伯克利的曾博老师转行CS这件事？
数学课有江湖吗？
(lnx)'＝1/x，为什么 (ln3)'≠1/3？
y=x^x的原函数是多少，能求出来吗?
linux的TCP连接数量最大不能超过65535个，那服务器是如何应对百万千万的并发的？
如果现在微软重写Windows会怎么样？
回顾人类历史，计算机的出现和进化对人类的进程造成了多大的影响？
这个式子对吗？若是，具体步骤是什么？
为什么几乎所有教科书上对微分的讲解都不明不白？
欧洲国家是否有墙？
计算机中，假设键盘同时按下两个键，会优先生效哪一个？
为什么这两年没再听说有什么大规模的电脑病毒爆发？
大型客机有没有假冒伪劣产品？
禁止使用sqrt等返回浮点数的函数，如何最高效的得到最小的不小于给定正整数的完全平方数？