给定无向图中的边，什么是限制图的最大度数同时最大化图度的算法

Question

这是我在蛋白质折叠方面的研究(所以我想从技术上讲是一个学校项目)

总结： 我有一个加权无向图的边缘。图形的每个顶点都有 1 到 20 条左右的边。我想修剪这个图表，以便没有顶点有超过 6 条边。我还希望图形保留尽可能多的连接性(最大化程度)。

背景： 我有一个使用scipy库的蛋白质中原子(本质上是点云)的Delaunay Tesselation。我用它来创建一个彼此接触的所有残基对的列表(我存储它们之间的距离)。此列表包含每对(两次)以及对之间的距离。(残基包含许多原子，所以我使用它们的平均位置来获得残基的位置)

pairs
[(ALA 1, GLU 2, 2.7432), (ALA 1, GLU 2, 2.7432), (ALA 4, ASP 27, 4.8938), (ALA 4, ASP 27, 4.8938) ... ]

我尝试过的(有效但并不完全是我想要的)是只存储六个最亲密的联系人。(我对残留名称进行排序，以便以后可以使用集合)

for contact in residue.contacts[:6]:
pairs.append( tuple( sorted([residue.name, contact.name], key=lambda r: r.name) + [residue.dist[contact]] ) )

然后删除任何未往复的联系人。(我想从技术上讲，添加的联系人是)

new_pairs = []
counter=collections.Counter(pairs)
for key, val in counter.items():
if val == 2:
new_pairs.append(key)

这有效，但我丢失了一些我想保留的信息。我把这个问题表述为图论问题，因为我觉得这个问题已经在那个领域解决了。

我在想贪婪的算法可能会起作用：

while run_greedy:
# find the residue with the maximum number of neighbors
# find that residues pair with the maximum number of neighbors but only if the pair exists in pairs
# remove that pair from pairs
# if maximum_degree <= 6: run_greedy = False

贪婪算法有效吗？是否有已知的算法可以很好地做到这一点？是否有一个库可以做到这一点(我非常愿意更改数据的格式以适应库)？

我希望这是足够的信息，提前感谢您的帮助。

Answer 1

编辑这是背包问题的一个变体：您逐个添加边，并希望在构建的图形不超过给定度数时最大化边数。

以下解决方案使用动态规划。

让我们m[i, d]边的最大子集，e_0, ..., e_{i-1}创建一个最大度数<= d的子图。

• m[i, 0] = {}
• m[0, d] = {}
• m[i, d] = m[i-1, d] + {e_i}图形的度数是否<= d
• m[i, d] = m[i-1, d-1] + {e_i}如果它的边比m[i-1][d]多，否则m[i-1][d]。

因此，算法(未测试)：

for i in 0..N:
m[i][0] = {}
for d in 1..K:
m[0][d] = {}
for d in 1..K:
for i in 1..N:
G1 = m[i-1][d] + {e_i}
if D(G1) == d: # can add e_i with degree <= k
m[i][d] = G1
else:
m[i][d] = max(m[i-1][d-1] + {e_i}, m[i-1][d]) # key=cardinal

解决方案是：m[N-1][K-1]。时间复杂度O(K N^2)(不和谐循环：K N+ 图的最大度数(以N或更小为单位)

以前的答案

TLDR;我不知道如何找到最佳解决方案，但贪婪的算法可能会给你可接受的结果。

问题所在

让我根据您的问题和代码重新表述问题：您希望从图形中删除最小数量的边，以便将图形的最大度数降低到6。那就是从GD(u) <= 6 for all u in G'获得最大子图G'。

我发现的最接近的想法是图的K核心，但这不是完全相同的问题。

您的方法

您的方法显然不是最佳的，因为您最多保留每个顶点的6条边，并使用这些边重新创建图形。取图表A-B-C：

A -> 1. B, 2. C
B -> 1. C, 2. A
C -> 1. A, 2. B

如果您尝试使用您的方法将此图的最大度数减小到1，则第一次传递将删除A-B(B是A的第 2 个邻居)、B-A(A是B的第 2 个邻居)和C-B(B是C的第二个邻居)：

A -> 1. B
B -> 1. C
C -> 1. A

为了确保图形是无向的，第二次传递将删除所有剩余的边(和顶点)。

最佳减少是：

A -> 1. B
B -> 1. A

或A、B、C中的任何其他顶点对。

一些策略

让：

• k = 6
• D(u) = max(d(u)-k, 0)：k以上邻居的数量，或0
• w(u-v)(resps(u-v)) = 边缘的弱(或强)端点：具有最低(或最高)度
• m(u-v) = min(D(u), D(v))
• M(u-v) = max(D(u), D(v))

让S = sum(D(u) for u in G).目标是在去除最少数量的边缘的同时进行S = 0。如果移除：

(1)浮边：m(u-v) > 0，则S减少2(两端点松动1度)

(2)下沉沿：m(u-v) = 0M(u-v) > 0，则S降低1(弱终点的程度已经<= 6)

(3)凹边：M(u-v) = 0，则S不变

请注意，在以下情况下，浮动边可能会成为下沉边缘：1.其弱端点具有一定程度的k+1;2. 移除连接到此端点的另一个 Edge。同样，下沉的边缘可能会下沉。

您必须删除浮动边缘，同时避免创建下沉边缘，因为删除浮动边缘可以更有效地减少S。让我们K删除的浮动边缘的数量，并L删除的下沉边缘的数量(我们不删除沉没的边缘)以S = 0。我们想要2*K + L >= S.显然，这个想法是使L尽可能小，因为我们希望删除少量的边缘(K + L)。

我怀疑你会找到一个最佳的贪婪算法，因为一切都取决于删除的顺序，并且当前删除的远程后果很难预测。

但是，您可以使用常规策略来限制下沉边缘的创建：

1. 除非别无选择，否则不要用m(u-v) = 1去除边缘。
2. 如果必须删除带有m(u-v) = 1的边，请选择其弱端点具有较少浮动边的边(它们将成为下沉边)。

一种算法

下面是实现此策略的贪婪算法：

while {u, v in G | m(u-v) > 0} is not empty: // remove floating edges first
remove the edge u-v with:
1. the maxmimum m(u-v)
2. w(u-v) has the minimum of neighbors t with D(t) > 0
3. s(u-v) has the minimum of neighbors t with D(t) > 0
remove all edges from {u, v in G | M(u-v) > 0} // clean up sinking edges
clean orphan vertices

终止算法终止，因为我们在每次迭代时都会删除一条边，因此{u in G | D(u) > 0}将在某个时候变为空。

注意：您可以在每次删除后使用堆和更新m(u-v)。