如果图是路径的不相交并集，则返回真

Question

我正在尝试做一个 if 语句，条件是图形是使用 networkx 的路径的不相交联合，但我不确定如何去做

我尝试在每个节点迭代中删除一条边 (u,v)，然后检查图中的第一个节点到没有边的第一个节点（node1 到 u）是否是一条路径，然后检查从第二个节点到最后一个节点（v 到节点 2）。

            for i in G1.nodes:
                node_count = node_count+1
                nodes.append(i)
                p = nx.neighbors(G1, i)
                for o in p:
                    neigh.append(o)
                    
                for j in neigh:
                    G1.remove_edge(i, j)
            no = len(nodes)
            for k in range(0, node_count-1):
                path.append(nodes[k])
            if nx.is_path(G1, path):
                for l in range(node_count-1, no-1):
                    path2.append(nodes[l])
                if nx.is_path(G1, path2):
                    return True

Answer 1

路径并集，你的意思是路径图，那么我们可以通过将图分解为连接的组件，然后确定每个连接的组件是否形成路径图来解决问题。

（我认为）这可以通过检查每个连接的组件是否具有度数序列来完成

[1, 1, 2 ... 2]

：

import networkx as nx

def is_disjoint_path_union(G):
    for c in nx.connected_components(G):
        n = len(c)
        if n == 1: continue
        if not sorted(dict(nx.subgraph(G, c).degree()).values()) == [1, 1] + [2]*(n - 2):
            return False
    return True

似乎工作：

>>> is_disjoint_path_union(nx.disjoint_union(nx.path_graph(3), nx.path_graph(3)))
True
>>> is_disjoint_path_union(nx.complete_graph(3))
False

Answer 2

有限图 G 是路径的不相交并当满足以下条件之一：

• 每个顶点的度数都是 0
• 每个顶点都有度数<= 2 and there are no cycles

请注意，在这两种情况下，|E| < |V|.

您可以使用 BFS 来检查循环。

BFS 是 O(|V| + |E|)，但由于 |E| <= |V|, this is O(|V|), or linear.