スペクトル（Fiedlerベクトル）の二分法によって生成されたサブツリーが切断される条件はありますか？

Question

無向ツリーを2つのサブツリーに分割しようとしています。それぞれのサブツリーが接続されています。私は、hereのようにFiedlerベクターを使ってこれを行うことができたと私は理解していました。しかし、このプロセスに従うと、結果のサブツリーは接続されません。

私が二分法を実装するために使用したコードは以下の通りであり、二分できない木は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) 

Iが得られたサブツリーのいずれも接続されてこれを実行すると、 - 各サブツリーは、1つまたは2つの大きな連結成分といくつかの単離されたノードを有します。フィードラーベクトルの値をプロットし、孤立ノードを識別することは、次のようになります

地球上でここで何が起こっているの？

Answer 1

ツリーの1つの特徴は、ツリー内の頂点の各ペアの間に1つのパスしか存在しないことです。その結果、エッジが切り取られると、そのエッジにあった頂点は、その唯一のパスであったため、接続されなくなりました。接続性は可換性であるため、カットの片側のすべての頂点は、カットの反対側のすべての頂点から切り離されます。その結果、1つのエッジを切り取ったときに常に2つの接続されたサブツリーにツリーが分割されます。そのウィキペディアのページを見ると、スペクトルの二分法を使うと、複数のエッジをカットするソリューションが得られるように見えます。基本的に、1つ以上のエッジをカットする任意の二等分線は、2つ以上の接続されたサブツリーを生成する。