完全断开二分图的连接
我有一个不连通的二分无向图。我想把图完全断开。我能执行的唯一操作是删除一个节点。删除节点将自动删除其边。任务是最小化要删除的节点数。图中的每个节点最多有4条边。
通过完全断开一个图的连接，我的意思是不应该通过一个链接连接两个节点。基本上是一个空边集。
共有1个答案
我认为，你不能证明你的算法是最优的，因为，事实上，它不是最优的。
要完全断开图的连接，最小化要移除的节点数，必须移除属于图的最小顶点覆盖的所有节点。搜索最小顶点覆盖通常是NP-完全的，但对于二部图存在多项式时间解。
在图中找到最大匹配（可能使用Hopcroft-Karp算法）。然后用König定理得到最小顶点覆盖：
考虑一个二分图，其中顶点被划分为左(L)集和右(R)集。假设存在一个最大匹配，它将边划分为在匹配中使用的边(E_m)和未使用的边(E_0)。设T由来自L的所有不匹配顶点组成，以及由沿E_0的边从左到右和沿E_m的边从右到左到达的所有顶点组成。这实质上意味着对于L中的每一个不匹配的顶点，我们将出现在从E_0到E_m的边之间交替的路径中的所有顶点加到T中。
则(L\T)或（R和T）是一个最小顶点覆盖。
-
问题内容： 我将Go（Golang）1.4.2和Gorilla WebSockets一起使用在nginx 1.4.6反向代理后面。打开页面大约一分钟后，我的WebSocket断开连接。在Chrome和Firefox上会发生相同的行为。 最初，我在使用WebSockets连接服务器和客户端时遇到问题。然后，我读到我需要调整我的nginx配置。这就是我所拥有的。 我的Go代码基本上是在回显客户的消息。
-
断开mqtt连接，前提是必须已经通过Iot_id，Iot_pwd建立过一次mqtt连接。 请求方式： "|4|1|4|\r" 返回值： "|4|1|4|1|\r" 断开成功 "|4|1|4|2|\r" 断开失败 Arduino样例： softSerial.print("|4|1|4|\r");
-
使一个无向加权（正权）图断开连接的最小代价是什么。 我的意思是，我必须找出那些边，这些边的去除断开了图的连接，并且它们的代价最小化。 我有以下想法... 1.找出图的所有桥。则最小重量的桥边为ANS。 该图没有自循环。 这个阿尔戈对吗？
-
我正在寻找一个算法，找到顶点的最小子集，这样从图中移除这个子集（以及连接这些顶点的边），所有其他顶点都变得不连通（即，图将没有任何边）。 null 我有图论的基础知识，所以请原谅任何不正确的地方。
-
我需要一个算法来将无向图的顶点划分为一个或多个子图，这样每个子图都是一个完整的图（每个顶点与每个其他顶点相邻）。每个顶点都需要恰好位于其中一个子图中。 这里有一个例子： 下面的图片更好地描述了这个问题： Kosaraju算法：它只适用于有向图。