c++ - 将图拆分为循环，然后拆分为路径

Question

首先，我应该说我对图论不熟悉，而且我的数学知识也很差。无论如何，我正在使用图形概念进行分析。

基本上，我将一个无向图(例如 G)分解为循环(闭合图)。我的循环的特点是它们是一个人可以在两个顶点之间遍历的最短循环(因为它们是循环，虽然开始和结束是相同的)。根据我的示例图，我的循环是 (1,4,5,1)(1,2,3,4,1)(7,9,8,7) (我忽略了长度小于 3 的循环) .

编辑:我使用深度优先搜索来获取循环，然后获取最小的循环。

稍后，我进一步将这些循环制动到有向路径中。在这里，我打破了边缘的循环(通过图中的红线)，以便为我的新路径图插入开始和结束节点。所以对于循环 (7,9,8,7)=> 新的有向路径是 (a,9,c)(d,8,7,b) 编辑:进一步中断仅针对选定的周期进行。它只是插入一个新 vector 并更新元素。这里不涉及任何图论相关的算法。

然后我对我的数据进行一些分析。

I did all above things. So, my problem is how to describe the entire things with mathematical notations (without example like I said). This is very hard for me as I do not have even basics.

我尝试并使用谷歌搜索，但仍然找不到描述我所做的事情的方法。我想，我所做的事情对你来说是清楚的。

So, Could you please help me, How to describe

1. decomposing a undirected graph into cycles (shortest cycles)
2. Cycle breaking via edges and make directed path graphs (as shown in figure)

用数学符号(根据图论)

我见过很多作者用不同的记法和符号来定义图和子图，但是对于我来说，我不能定义这样的东西，因为我的基础太差了。所以，请帮我用一种正式的、数学的方式来表达这些东西。提前致谢。

我也插入了示例图来了解一下。

注意:我添加了 c++ 标签，因为许多计算机科学家使用图论并希望得到回应。

Answer 1

在尝试用数学描述您的操作时，您可能会遇到的第一个问题是您对“最短循环”的定义，因为循环通常被定义为由边连接的一系列顶点，其中第一个也是最后一个。

数学速成类

在数学中，图 通常由两个集合 V(如顶点)和 E(如边)描述 集合 E 由两个元素组成的集合组成，每个元素都是一个顶点。 比如

• V = { v1, v2, ...., vn }

• E = { ..., {vi, vk}, ... }

E 中的每个集合对应于图中的一条边。

这样一个(连接的)路径通常被定义为:

一个顶点序列 v1, ...., vn 其属性为对于序列中的每两个连续顶点 vi 和vi+1 集合{ vi, vi+1 } 是集合E 的一个元素。

(实际上:从顶点 vi 到顶点 vi+i 有一条边)

循环 通常被定义为具有以下属性的路径:v1 = vn(因此第一个顶点也是最后一个顶点)

这个定义和你的例子已经是序列:1, 4, 1 形成一个循环(在数学意义上)

因此，图中的每条边都算作“最短”循环，而给出的示例肯定更长!

你说的是你

... neglect the cycles whose length is less than 3

作为您的描述的起点，这看起来不错。遗憾的是，我没有完全理解您想执行的后续步骤。

建议

我的建议，或者至少是我处理问题的方法，是将相当长的描述转换为某种较短的算法描述，同时细化您尝试执行任务的确切方式。通过这种方式获得最终描述应该不会太难。特别是不要忘记告诉您算法的输入到底是什么。即使从您的描述中似乎也不太清楚。

• 您是否从一组已知的“最短”周期开始？
• 或者您只是给了一个图表作为输入并且必须自己确定“最短”周期？
• 如果您自己检测到它们，具体是怎么做到的？ 尤其不要忘记讲述故事的这一部分(如果它适用)，因为它似乎是对您的问题最关键的部分之一。