标签: spanning-tree

我有一个连通的,无向图,边缘分别为黑色或白色,以及整数k.我正在尝试编写一种算法,该算法可以判断生成树是否存在k个黑色边缘(不一定要找到实际的树).

我使用Kruskal的算法来查找生成树中最小和最大可能的黑边数.如果k超出此范围,则不存在具有k个边的生成树.

但是我无法理解是否必须为该范围内的每个k生成一棵生成树.我的直觉是肯定的,它对我尝试过的每个例子都有效,但我无法弄清楚如何证明它.

有什么建议？提前致谢.

最小乘积生成树与最小和生成树不同吗？请解释一下（如果可能的话，举例说明）。我的意思是，添加到最小值的边应该（？）也具有最小乘积。

你们中有人知道使用生成树数据结构的任何实际应用程序吗？

给定一个像这样的简单无向网格网络：

import networkx as nx
from pylab import *
import matplotlib.pyplot as plt
%pylab inline

ncols=3
N=3 
G=nx.grid_2d_graph(N,N)
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds=[(N-j-1,N-i-1) for i,j in inds]
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10)
plt.axis('off')
plt.title('grid')
plt.show()

考虑到每条边都有与其长度相对应的权重：

#Weights
from math import sqrt

weights = dict()
for source, target in G.edges():
    x1, y1 = pos2[source]
    x2, y2 = pos2[target]
    weights[(source, target)] = round((math.sqrt((x2-x1)**2 + …