gpt4 book ai didi

algorithm - 查找图中的所有关键节点集

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:30:26 24 4
gpt4 key购买 nike

给定一个图,我想找到节点的集合 S1、S2、...,这些节点的移除可能会导致网络断开。这些集合中的每一个都可能包含一个或多个节点。此外,这些集合中的任何一个都不是彼此的子集,即我们不考虑 S3=S1 U S2,尽管它也会断开网络连接。

我们不想找到:

  1. 只有一个关键节点集但所有
  2. 最大程度断开网络连接的单个节点集。

关于这些的任何建议:

  1. 问题的难度
  2. 解决方案的一些方向/论文引用
  3. 我可能需要提供的任何证明

最佳答案

删除后会断开图形连接的顶点集称为分隔符。参见例如A. Berry、J-P Bordat、O. Cogis:Generating all the Minimal Separators of a Graph .

关于algorithm - 查找图中的所有关键节点集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17441319/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com