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

Question

这是我在蛋白质折叠方面的研究（所以我猜在技术上是一个学校项目）

总结：我有一个加权无向图的边。图的每个顶点都有 1 到 20 条边。我想 trim 将此图缩小，使得没有顶点的边数超过 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

EDIT 这是 knapsack problem 的一个变体：你一条一条地添加边，并且想要最大化边的数量，而构建的图形却没有超过给定的程度。

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

让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。即从G和D(u) <= 6 for all u in G'.

得到最大子图G'

我发现最接近的想法是 K-core of a graph，但这不是完全相同的问题。

你的方法

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

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

如果您尝试使用您的方法将此图的最大度减少到 1，则第一遍将删除 A-B（B 是 [=38 的第二个邻居=]), B-A（A 是 B 的第二个邻居）和 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) (resp s(u-v)) = 边的弱（resp. 强）端点：具有最低（resp. 最高）度数
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) = 0和M(u-v) > 0，则S减少1（弱端点的度数已经是<= 6)

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

请注意，如果出现以下情况，浮边可能会变成下沉边： 1. 其弱端点的度数为 k+1； 2. 删除连接到此端点的另一条边。同样，下沉的边缘可以下沉。

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

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

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

除非别无选择，否则不要使用 m(u-v) = 1 删除边缘。
如果你必须用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)。

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

Given edges in a undirected graph, what is an algorithm for limiting the maximum degree of the graph while maximizing the degree of the graph?

python

algorithm

graph-theory

问题

你的方法

一些攻略

一个算法