在我从事的一个项目中，出现了同构与单态的主题。

一点背景知识：我不是图论专家，也没有接受过正规培训。但是这个主题在化学中非常重要，化学家期望在他们使用的结构搜索系统中发生一种特定类型的子图匹配。

如果目标图 A 有 n 个节点和 m 条边，那么化学家将接受子图匹配，其中查询图 B 有 n 个节点和 m-1 条边。唯一的要求是 B 中的每条边都应该出现在 A 中。例如，6 个节点的线性链应该匹配 6 个节点的循环。

这种匹配同构还是单态？也许完全是别的东西？

我有一个图表，其中包含未知数量的断开连接的子图。什么是找到它们的好算法（或 Java 库）？

如何以伪代码从图中获取固定大小的所有子图？（蛮力）

如果可能的话，没有外部库。谢谢！

在 for 的DOT语言中GraphViz，我试图表示一个依赖关系图。我需要能够在容器内拥有节点，并且能够使节点和/或容器依赖于其他节点和/或容器。

我subgraph用来代表我的容器。节点链接工作得很好，但我不知道如何连接子图。

鉴于下面的程序，我需要能够使用箭头进行连接cluster_1，cluster_2但是我尝试过的任何操作都会创建新节点而不是连接集群：

我正在寻找一种算法来检查给定图是否是另一个给定图的子图。

我几乎没有条件让这个 NP 完全问题更可行..

• 这些图有大约 <20 个顶点。
• 图表是 DAG。
• 所有顶点都是非唯一标记的，并且主图和子图中的对应顶点应该具有相同的标签。我不知道我是否使用了正确的术语（因为我没有上过图论课程......）。它会是这样的：

折线图 A--B 是 A--B--A 的子图，但 A--A 不是 A--B--A 的子图。

任何建议都很好。顺便说一句，这不是作业问题。:D

子图同构是一个NP完全问题。使用最广泛的算法是Ullman提出的算法。

有人可以用外行的语言向我解释算法吗？我读了他的上述论文，但看不懂。

这个问题还有哪些其他算法？

我正在做一个图像处理项目。

我有一个具有以下属性的图表：

• 无向的
• 未加权
• 每个顶点至少有 2 条和最多 6 条连接到它的边。
• 顶点数将小于 100
• 图形是静态的，不能添加/删除或编辑任何顶点/边。

我正在寻找顶点的随机子集（至少 2 个）之间的路径。路径应该是只经过任何顶点一次的简单路径。

我的最终目标是拥有一组路线，以便您可以从一个子集顶点开始并到达任何其他子集顶点。跟随路线时不必通过所有子集节点。

我发现的所有算法（Dijkstra、深度优先搜索等）似乎都在处理两个顶点之间的路径和最短路径。

是否有一种已知的算法可以为我提供连接这些顶点子集的所有路径（我想这些是子图）？

编辑：

我创建了一个（警告！程序员艺术）动画 gif 来说明我想要实现的目标：http: //imgur.com/mGVlX.gif

有两个阶段预处理和运行时。

预处理

1. 我有一个图和顶点的子集（蓝色节点）
2. 我生成连接所有蓝色节点的所有可能路线

运行

1. 我可以从任何蓝色节点开始，选择任何生成的路线，然后沿着它到达我的目标蓝色节点。

所以我的任务更多是关于创建连接所有蓝色节点的所有子图（路由），而不是创建从 A->B 的路径。

是否有已知的算法或方法可以在图中找到所有完整的子图？我有一个无向、未加权的图，我需要找到其中的所有子图，其中子图中的每个节点都连接到子图中的其他节点。

有没有现成的算法呢？

我有一个未加权的连接图。我想找到一个连接的子图，它肯定包含一组特定的节点，并且尽可能少的额外节点。这怎么可能实现？

以防万一，我将使用更精确的语言重申这个问题。令 G(V,E) 是一个未加权、无向、连通图。让 N 是 V 的某个子集。找到 G(V,E) 的最小连通子图 G'(V',E') 以使 N 是 V' 的子集的最佳方法是什么？

近似值很好。

我正在尝试旋转一个节点（或一个包含节点的子图 - 无论哪个可能/更容易），如下图所示：

（请注意，“B”标签是否旋转对我来说并不重要 - 只是记录中的“verti-*”文本[或者更确切地说，整个记录节点]如图所示旋转）

但是，我能做到的最接近的是以下dot代码：

我在subgraph clusterSubRotateBox那里的唯一原因（以及它嵌套在 内部的唯一原因clusterMasterBox）是因为我希望我可以为它分配旋转，但显然我不能 - 因为上面的代码生成了这个图像：

所以我的问题是 - 有没有办法旋转记录节点？如果不是单独的，那么可能作为子图的一部分（或不同类型的“对象”）？

提前感谢您的任何建议，
干杯！