0

我正在尝试将无向树划分为两个子树，每个子树都连接在一起。我的理解是，这可以使用此处描述的 Fiedler 矢量来完成。但是，当我遵循这个过程时，结果子树没有连接。

我用来实现二等分的代码如下，这里定义了不能二等分的树。

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 向量的值并识别孤立节点如下所示：

在此处输入图像描述

这到底是怎么回事？

4

1 回答 1

0

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

于 2017-02-24T04:31:20.473 回答