谱（费德勒向量）二分生成的子树是否存在断开连接的条件？

Question

我正在尝试将无向树划分为两个子树，其中每个子树都是连接的。我的理解是，这可以使用 Fiedler 矢量来完成，如here所述。但是，当我遵循此过程时，生成的子树未连接。

我用来实现二分的代码如下，无法二分的树定义在here。

import networkx as nx
from itertools import compress

g = nx.from_dict_of_dicts(broken_g)

def split_graph(graph):
    """Split a graph into two pieces using the Fiedler vector.

    See https://en.wikipedia.org/wiki/Graph_partition#Fiedler_eigenvalue_and_eigenvector
    """

    assert nx.is_connected(graph), 'must pass connected graph'

    fiedler_vec = nx.fiedler_vector(graph, normalized=True, weight=False)

    mask_a = fiedler_vec > 0
    mask_b = ~ mask_a

    subgraph_a_nodes = compress(graph.nodes(), mask_a)
    subgraph_b_nodes = compress(graph.nodes(), mask_b)

    subgraph_a = graph.subgraph(subgraph_a_nodes)
    subgraph_b = graph.subgraph(subgraph_b_nodes)

    assert nx.is_connected(subgraph_a) and nx.is_connected(subgraph_b), 'split did not produce connected subgraphs'

    return [subgraph_a, subgraph_b]

split_graph(g)

当我运行此命令时，生成的子树都没有连接 - 每个子树都有一个或两个大型连接组件和几个孤立的节点。绘制 Fiedler 矢量的值并识别孤立节点如下所示：

这里到底发生了什么？

Answer 1

树的一个特征是树中的每一对顶点之间只有一条路径。结果，当一条边被切割时，该边上的顶点不再连接，因为这是它们唯一的路径。由于连通性是可交换的，因此切割一侧的每个顶点都与切割另一侧的每个顶点断开连接。结果是，当你切割一条边时，你总是将一棵树分成两个相连的子树。查看该维基百科页面，看起来使用光谱二分可能会产生切割多个边缘的解决方案。基本上任何切割多于 1 个边的二分都会产生多于 2 个相连的子树。