2

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

基本上，我将无向图（比如 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) 编辑：仅对选定的循环进行进一步的破坏。它只是插入一个新向量并更新元素。这里不涉及任何图论相关的算法。

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

我做了以上所有事情。所以，我的问题是如何用数学符号来描述整个事物（没有我说的例子）。这对我来说很难，因为我连基础都没有。

我正在尝试和谷歌搜索，但仍然找不到描述我所做的事情的方法。我想，我所做的事情对你来说很清楚。

所以，你能帮我吗，如何描述

  1. 将无向图分解为循环（最短循环）
  2. 通过边进行循环并制作有向路径图（如图所示）

用数学符号（根据图论）

我见过很多作者使用不同的符号和符号来定义图形及其子图，但对我来说，我无法定义我的基础太差之类的东西。所以，请帮助我以一种正式的、数学的方式来表达这些事情。提前致谢。

我也插入了示例数据以获取想法。 在此处输入图像描述

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

4

1 回答 1

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 形成一个循环（在数学意义上）

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

你说过你

...忽略长度小于 3 的循环

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

建议

我的建议，或者至少我将解决问题的方法是将相当长的描述转换为某种更短的算法描述，同时精确地改进您尝试执行任务的方式。这样得到你的最终描述应该不会太难完成。特别是不要忘记告诉算法的输入到底是什么。即使从您的描述中似乎也不太清楚。

  • 您是否从一组已知的“最短”周期开始？
  • 还是您只是将图表作为输入，并且必须自己确定“最短”周期？
  • 如果您自己检测到它们，这是如何完成的？特别是不要忘记讲述故事的这一部分，如果它适用，因为它似乎是对您的问题最关键的部分之一。
于 2013-03-03T00:17:10.943 回答