line_graph#

line_graph(G, create_using=None)[source]#

返回图或有向图 G 的线图。

图 G 的线图具有 G 中每个边的节点，并且如果 G 中的两条边共享一个公共节点，则在这些节点之间有一条边。对于有向图，节点相邻当且仅当它们表示的边形成长度为二的有向路径。

线图的节点是原始图中节点的 2-元组（对于多重图，则为 3-元组，其中边的键作为第三个元素）。

有关自环和更多讨论，请参见下面的 注释 部分。

Parameters:
G图

一个 NetworkX 图、有向图、多重图或多重有向图。

create_usingNetworkX 图构造函数，可选（默认=nx.Graph）

要创建的图类型。如果是图实例，则在填充之前清除。

Returns:
L图

G 的线图。

Notes

图、节点和边数据不会传播到新图。对于无向图，G 中的节点必须是可排序的，否则构造的线图可能不正确。

无向图中的自环

对于没有多重边的无向图 G ，每条边可以写成集合 {u, v} 。其线图 L 具有 G 中的边作为其节点。如果 x 和 y 是 L 中的两个节点，则 {x, y} 是 L 中的边当且仅当 x 和 y 的交集非空。因此，所有边的集合由 G 中所有边的成对交集确定。

显然， G 中的每条边都会与自身有非零交集，因此 L 中的每个节点都应该有一个自环。这并不有趣，线图的原始上下文是简单图，没有自环或多重边。线图也被设计为简单图，因此， L 中的自环不属于线图的标准定义。在成对交集矩阵中，这类似于在线图定义中排除对角线项。

G 中的自环和多重边以自然的方式向 L 添加节点，并且不需要对定义进行根本性更改。可以认为之前排除的自环现在应该包括。然而，这些自环在某种意义上仍然是“平凡”的，因此通常被排除。

有向图中的自环

对于没有多重边的有向图 G ，每条边可以写成元组 (u, v) 。其线图 L 具有 G 中的边作为其节点。如果 x 和 y 是 L 中的两个节点，则 (x, y) 是 L 中的边当且仅当 x 的尾部与 y 的头部匹配，例如，如果 x = (a, b) 且 y = (b, c) 对于 G 中的某些顶点 a 、 b 和 c 。

由于边的有向性质， G 中的每条边在 L 中不再应该有自环。现在，只有当 G 中的节点本身有自环时，才会出现自环。因此，这些自环不再是“平凡”的，而是代表了 G 拓扑结构的重要特征。出于这个原因，线有向图的历史发展包括了自环。当图 G 有多重边时，再次只需要对定义进行表面上的更改。

References

  • Harary, Frank, and Norman, Robert Z., “Some properties of line digraphs”, Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161–168.

  • Hemminger, R. L.; Beineke, L. W. (1978), “Line graphs and line digraphs”, in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.

Examples

>>> G = nx.star_graph(3)
>>> L = nx.line_graph(G)
>>> print(sorted(map(sorted, L.edges())))  # 形成一个 3-团，K3
[[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]]

G 的边属性不会作为节点属性复制到 L 中，但可以手动复制属性：

>>> G = nx.path_graph(4)
>>> G.add_edges_from((u, v, {"tot": u + v}) for u, v in G.edges)
>>> G.edges(data=True)
EdgeDataView([(0, 1, {'tot': 1}), (1, 2, {'tot': 3}), (2, 3, {'tot': 5})])
>>> H = nx.line_graph(G)
>>> H.add_nodes_from((node, G.edges[node]) for node in H)
>>> H.nodes(data=True)
NodeDataView({(0, 1): {'tot': 1}, (2, 3): {'tot': 5}, (1, 2): {'tot': 3}})
On this page