Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

FindIndependentEdgeSet

FindIndependentEdgeSet[g]

求图 g 的具有最大边数的独立边集.

FindIndependentEdgeSet[{vw,…}]

使用规则 vw 指定图 g.

更多信息和选项

独立边集也称为匹配.
一个独立边集是不与相同的顶点相关联的边组成的集合.

FindIndependentEdgeSet 返回由边组成的列表.
FindIndependentEdgeSet 适用于无向图、有向图、加权图和多重图.

范例

打开所有单元关闭所有单元

基本范例 (1)

求图的独立边集：

显示边集：

范围 (6)

FindIndependentEdgeSet 适用于无向图：

有向图：

加权图：

多重图：

使用规则指定图：

FindIndependentEdgeSet 可用于大规模图：

应用 (3)

一个公司有大量不同的工作. 每个职员适合于某些任务，每个人最多可以一次执行一个任务：

最大化同时能够执行的任务数：

给定一组女生，每个女生对某些男生组成的子集感兴趣，求最大匹配方式，其中只有感兴趣的才进行匹配：

计算最大匹配：

一个艺术历史系想要提供六门课. 这里有8个教授，每个教授愿意教某些课. 求最大匹配方法，其中每个教授只讲授自己感兴趣的课程：

将兴趣与课程匹配：

属性和关系 (3)

使用 IndependentEdgeSetQ 检验一个边集是否是独立边集：

二分图具有相同长度的独立边集和顶点覆盖：

对于不含有孤立顶点的图，独立边集的大小和边覆盖的大小之和等于顶点数：

顶部