断开图中所有顶点的连接-算法
我正在寻找一个算法，找到顶点的最小子集，这样从图中移除这个子集（以及连接这些顶点的边），所有其他顶点都变得不连通（即，图将没有任何边）。
-
null
我有图论的基础知识，所以请原谅任何不正确的地方。
共有1个答案
这是经典的最小顶点覆盖问题，不幸的是，它是NP完全的。
幸运的是，在这种情况下，最直观、最贪婪的可能算法是尽可能好的。
-
在这里，我试图断开图中的两个顶点，尽可能减少边的去除。 对此有没有具体的算法？ 我找到了一些用最大流最小割问题来解决这一问题的建议，但我还没有得到将这一问题转化为最大流最小割定理的一般思想。同样，在这个过程中，我可能会在F和G之间去掉一条边，这是无用的。
-
给定无向连通图，查找其删除会断开该图的所有节点对（通过边连接） 没有平行边，也没有将节点连接到自身的边。 这个问题似乎类似于寻找一个连通的无向图的连接点（或桥），但有一个转折点，我们必须移除一对由边连接的顶点（以及所有其他与该对连接的边）。 这是一个家庭作业问题。我一直在尝试解决这个问题，阅读有关DFS和关节点算法（即每个节点的深度和低点）的文章，但这些方法都不能解决这个特定的问题。我查阅了科曼的
-
这是史蒂文·斯基纳（StevenSkiena）提出的算法设计问题（用于面试准备）： 图G的一个连接点是一个顶点，其删除与G断开。设G是一个有n个顶点和m条边的图。给出一个简单的O（n m），该O（n m）可以为n个顶点找到一个删除顺序，以便没有删除会断开图形。 这就是我的想法： > 在图上运行DFS并不断更新每个节点最古老的可达祖先（我们根据它来决定它是桥切节点、父可爱节点还是根切节点） 如果我们
-
如何在Gremlin查询中检索从根顶点开始的所有顶点属性？ 我们有以下结构： 根顶点：Employee 边缘：EdCompany，EdDepartment，EdRole顶点：公司，部门，角色 我们试图接收与根顶点连接的其他顶点的数据。有人这样想： 我们尝试了该查询，但返回了一个复杂的JSON： 编辑： 我们还尝试了Kelvin建议的查询： 堆栈跟踪：提交查询失败：g.V（）.hasLabel（“E
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
在jgrapht中，我添加了一些顶点。 我想知道如何获得所有我添加的顶点或jgrapht中已经存在的顶点？ 有办法弄到吗？