line_graph#

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

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

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

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

有关自环和更多讨论的信息，请参阅下面的 备注 部分。

参数:
G图

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

create_usingNetworkX 图构造器，可选（默认为 nx.Graph）

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

返回:
L图

G 的线图。

备注

图、节点和边的数据不会传播到新图。对于无向图，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 有多条边时，定义上只需要进行一些表面上的改动。

参考文献

  • 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.

示例

>>> G = nx.star_graph(3)
>>> L = nx.line_graph(G)
>>> print(sorted(map(sorted, L.edges())))  # makes a 3-clique, 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}})
在本页