问题:给定一个q规则无向图，我正在寻找一种算法，通过边删除来识别n规则无向子图。N & lt;Q(很明显)，在算法中实现一定程度的随机性是很重要的，因为我需要对n个正则子图的空间进行采样。
我试过了:目前为止，我最好的方法是找到一个哈密顿循环，然后删除循环上的其他边。这很好地创建了一个(Q-1)正则子图，原则上可以重复，直到达到所需的正则程度，或者我无意中创建了一个没有哈密顿循环的图。然而，这种方法是缓慢的(这是我的主要问题)，它有点问题，它依赖于哈密顿循环的其他完全不必要的限制。
我的问题:有没有人能提出一种替代哈密顿循环方法的方法，或者干脆告诉我这个问题本身就很难，比哈密顿循环检测更快的解决方案是不可能的?我意识到我在这里玩弄了一些图论概念，但恐怕我没有专业知识来更正式地构建它。
感谢您的宝贵时间:)
编辑:我忘了说原始网络中的顶点数(= L)是偶数。我做这个限制是为了确保可以创建一个正则图，因为如果L和Q都是奇数，这是不可能的，我希望对Q有尽可能少的限制。其次，我确实希望保留所有顶点(因此我只提到了边删除)。
在本文中，作者提供了一种在O(n^3)中将一个特殊的Q-regular图转化为Q-1 - regular图的方法，这意味着对于某些特殊情况，你的问题在O(n^4)中是可以解决的。你可能想看看这篇文章，看看它是否对你有帮助。
另一种方法是构造一个最大匹配(例如使用Edmond's Blossom算法)。
这构造了一组边，使得每个顶点最多连接一条边。
这可能比寻找哈密顿路径更有效，更有可能工作(例如，对于断开的图)。
删除最大匹配中的边将得到Q-1正则图，当且仅当每个顶点与匹配中的恰好一条边相连。(一个顶点不可能连接到多个边，但有些顶点可能连接到0个边。然而，我相信这只会发生在不可能有Q-1正则子图的情况下。
为了使其随机化，您可以考虑使用加权匹配算法并使用随机权重。
我想到Peter de Rivaz的答案的一个变体是从原始图中找到N个连续的完全匹配，然后构建网络作为这N个匹配的连接。如果N <Q-N，这比通过修剪创建更快，并且有一个优点，即如果原始图本身不是正则的，它也可以工作。>