问题标签 [subgraph]

我假设我们有 2 个标记图 G 和 T 并且算法确定 G 是否是 T 的子图以及主图 T 中的相应顶点和子图 G 应该具有相同的标签

我有一个主图和另一个小图，假设小图可以在主图中重复为具有一定相似度的子图（不一定是相同的小图） 什么是找到它们的好算法（或 Java 库）全部？

这是生成的图表当前的样子： 这是代码：

如果我删除 2 条红线，那么它会按照我想要的方式排列：

我怎样才能让它像这样排列并且同时有两条红线？

我正在尝试找到用于搜索与定向图中指定模式相对应的部分的工具/算法，例如：

A->B->C 或 或 A<->B->C

请建议我搜索的方向。

我的意思是模式匹配。我需要找到与指定模式匹配的所有节点和边组

我有一个算法，用于通过给定顶点创建 P 顶点上所有可能的子图的列表。它并不完美，但我认为它应该可以正常工作。问题是当我尝试计算它的时间复杂度时我迷路了。

我想出了类似的东西T(p) = 2^d + 2^d * (n * T(p-1) )，在哪里d=Δ(G), p=#vertices required, n=|V|。这真的只是一个猜测。谁能帮我这个？

使用的 powerSet() 算法应该是O(2^d)or O(d*2^d)。

对不起，文字墙，它尽可能简洁！

我有一个非常大的有向图 G 和 G 内的顶点子集 S p 和 G 中的一个顶点 q，即在诱导子图中这两个顶点之间存在一条边。这是关键；它比通常的诱导子图问题更复杂（我认为）。

我能想到的解决问题的最基本方法如下（我意识到它可能不是最有效的，如果您有其他不太复杂的建议，请告诉我）： 对于 S 中的每一对顶点，在 G 中测试它们之间是否存在路径。如果存在这样的路径，则在诱导子图中插入 p 和 q 之间的边。就我的目的而言，n^2 次还不错。

所以，我想我有两个问题：1）确定两个顶点之间是否存在路径的最快方法是什么？我不需要知道路径，只需要知道它是否存在。此外，如果我可以对整个图形进行一些预处理以加快计算速度，那可能是什么，因为我必须在每对顶点之间执行此计算？

2）有没有比我建议的更快的方法来找到我描述的诱导子图的类型？

非常感谢你的帮忙！

我使用 jgrapht。我将生成子图。

我认为jgrapht-0.8.2/jgrapht-0.8.2/src/org/jgrapht/graph/DirectedSubgraph.java对这个目的很有用。但我找不到如何使用这个类？你能帮助我吗 ？

例如：jgrapht-0.8.2/jgrapht-0.8.2/src/org/jgrapht/demo/HelloJGraphT.java 有向图构造函数的使用与 HelloJGraphT.java 类中的一样

我想让我的图表看起来像这样：

但我只能得到这个：

问题是，rankdir 在subgraph. 那么，如何模仿呢？

编码：

我有两个顶点列表：V和S.

我想从等生成所有可能的有向图V，S每个顶点V只有一个出边和一个入边，每个顶点S可以有任意数量的入边和出边。结果中的每个图都应包含来自V和 的所有顶点S。结果可以包含连通图和不连通图。

首先我认为这是一个与 powerset 相关的问题，但是 powerset 有许多其他的集合可能只包含一个元素（我不需要那些）。

我目前的策略是：

• 找到顶点之间的所有对V，添加到Pairs；
• 找到顶点之间的所有对S，添加到Pairs；
• V从和中找到所有顶点之间的对S，添加到Pairs;
• 生成大小不小于V这样的对子集，每个子​​集在第一个位置恰好有一个顶点v实例，在第二个位置有一个顶点实例，以及来自任何位置v的任意数量的任何顶点实例.sS

我不确定这是否正确，我想知道任何想法。

也许我可以从中创建一个完全连接的图G，V然后S以某种方式从中提取子图？（也许在 digraph:utils 的帮助下）

PS 我正在尝试在 Erlang 中解决这个问题，因为它是我现在正在使用并积极学习的语言。但我很高兴在答案中看到 Java、Ruby 或伪代码。

我正在尝试解决以下问题：

给定一个连通图 G = (V, E) 和一个顶点 t ∈ V，我需要找到一个子图 G'= (V', E')，其中 t ∈ V'。G' 应该最大化一些目标函数并最小化它包含的顶点数。

在这个多目标优化问题中，最大化 f (G') 比最小化顶点数更重要。

让我们检查一个有类似问题的实际情况：

假设我们必须在客户端设备具有固定位置并且只有一个接入点连接到有线网络的建筑物中设计一个自组织无线网络。最初，我们在每个房间放置一个 AP，并使用传播模型计算可以连接的 AP 以及它们提供覆盖的客户端设备。在这个初始分布中，可能有几个 AP 会为同一个客户端设备提供覆盖，因此我们需要对其进行优化。

图 1. 红点表示连接到有线网络的 AP，黑点表示其余的 AP。AP 之间的实线向我们展示了它们是如何连接的。

图 1 中形成 AP 连接的图表示我们问题的连接图 G，连接到有线网络的 AP 是节点 t。优化表示此初始网络设计的图意味着找到一个包含连接到有线网络的 AP 的子图，并最大化覆盖客户端设备的百分比 (Max f(G') ) 最小化 AP 的数量 (Min |V'| ）。与问题一样，最大化覆盖客户端设备的百分比是主要目标。

图 2. 一种可能的解决方案。

使用蛮力算法，这似乎是一个 NP-Completeness 问题；找到最佳解决方案需要检查所有可能的子图（都包含节点 t）并证明一个可能的解决方案。你有什么想法？