偏序性质的有向无环图的最大独立集如何求解? 第1页
1
feng-kuang-shen-shi-92 网友的相关建议:
偏序关系就是一个关系矩阵。
关系矩阵就是一个布尔方阵。
任意的一个布尔方阵，求解出它的一般性骨架矩阵，即哈斯矩阵，也就是缩边矩阵就是你要的东西。
偏序性质的有向无环图的最大独立集等于最小路径覆盖。
也就是你上面那拗口的一句话。什么最小路径覆盖云云。
情况复杂一点，那么现在来看具体求解。
在之前请自行搜索 对抗解释结构模型，或者搜索对抗哈斯图技术。两者是等价的。
上面是对抗哈斯图技术的运算地址。
其中没有回路的时候 即哈斯矩阵，也称为骨架矩阵，也就是去掉了覆盖路径即重复路径的。
比如上面的原始关系矩阵（偏序集）
可达矩阵如上
上面的叫缩点可达矩阵。f6与f7够成回路，当成一个结点处理
上面的就叫哈斯矩阵，骨架矩阵，由缩点骨架矩阵缩边得到。
上面是一般性骨架矩阵
上面两边的都是哈斯图。分层级的
上面的就是最大独立集。
计算很简单
I为单位矩阵。
1
相关话题
程序员的bug解决不了怎么办？顶级数学家有多厉害？
本科渣校的学生如何进入美帝牛校读PhD？
为何一个byte有8bit而不是7/9/4/16bit ?
为什么全网都在推崇计算机、写代码，难道大学除了计算机专业其他专业真的一无是处吗?
相对论刚提出时，号称全球能完全理解的人不超过十人，现在却成为理工科必修课程，是我们智商提高了吗？
为什么计算机对人类的冲击要远大于其他科学?
学计算机，不太喜欢编程，有哪些出路？
如何看待计算机科学几乎渗透到所有学科的研究当中？
被高数虐是一种怎样的体验？
前一个讨论
买毒品准备用于贩卖是否构成贩卖毒品罪？
下一个讨论
如何从某一角度批判社会达尔文主义？
相关的话题
「C++ 早就过时了，大部分写工程不用 C++，学习这个语言只是为了竞赛」的观点是否正确？如何通过很多组相互包含的换算数据求解尽可能精确的换算比例？
「微积分」的建立和发展经过了哪些阶段，它的研究对其它学科产生了什么影响？
江苏一公司要求员工改用国产手机，称买苹果辞退买华为补贴，这类「支持国货」的行为值得提倡吗？
对于所有的无穷小，能否把它们趋于0的速度定义为一个数，使得趋于0速度较小的一定是较低阶的无穷小？
c语言中的sizeof()是如何分辨数组名和指针的？
三角函数到底是怎么发展来的？
为什么微积分那么难学？
今年高中毕业，自学高数，遇到一道题不知道如何去解，请教下各位大佬。题目：？
如何才能让学的数学灵活起来，或者说融会贯通？
如何反驳如下说法: 1不是无穷大，且若正整数n不是无穷大，则n+1不是无穷大，所以无穷大不存在？
计算机未来应该纳入高考学科吗？
为何目前有eGPU（外接显卡）， 而没有eCPU（外接中央处理器）？
如何评价上海交大计算机系的保研事故？
为什么前端不能一直做？难道要转行？？
计算机图形学是不是计算机专业方向中对数学要求最高的？
晾一件刚洗的衣服，有可能计算出每滴水落地的时间间隔吗？
为什么很多人觉得计算机专业的会修电脑？
请教如何计算这个反常积分？
普通一本计算机类大一新生如何在今后make a difference？
C 语言的「void main」是怎么一代代传下来的？
如何用数学语言描述数列Xn不是单调数列?
如何评价 SDCC (Small Device C Compiler) 编译器套件？
程序计数器（Program Counter）是一个实际存在的寄存器吗？
为什么要开源？
如何用高中数学知识证明 ln(ln88)＜3/2？
有哪些计算机术语的翻译，让你第一次学的时候感到十分别扭？
为什么有人在挤破脑袋卷师医公金融计算机的时代还在畅谈中国高端制造？
如何证明 1＋1/2^p＋1/3^p＋…＋1/n^p（1＜p＜2，p 为实数）收敛？
这个反常积分怎么推导呢?