0

以立方体为例，有8个节点，12条边，每个节点连接3个节点。

使用networkx，我必须手动输入所有边缘。例如，下面的代码是构建一个包含二十面体所有边的图（12 个节点，30 个边，每个节点 5 个相邻节点）。

import networkx as nx
G = nx.Graph()
nodes = list(range(12))
edges = [
    [0, 1], [0, 2], [0, 3], [0, 4], [0, 5],
    [1, 2], [1, 6], [1, 10], [1, 5],
    [2, 3], [2, 6], [2, 7],
    [3, 4], [3, 7], [3, 8],
    [4, 5], [4, 8], [4, 11], 
    [5, 11], [5, 10],
    [6, 7], [6, 9], [6, 10],
    [7, 8], [7, 9],
    [8, 9], [8, 11],
    [9, 10], [9, 11],
    [10, 11],
]
G.add_nodes_from(nodes)
G.add_edges_from(edges)

我的问题是如何在不手动编写的情况下获得所有可能的边缘。每个节点的名称可以随机初始化。

据我所知， igraph中的 Erdős-Rényi 模型无法约束相邻节点。

from igraph import *

g = Graph.Erdos_Renyi(12, m=30, directed=False)
g.get_edgelist()
"""
[(0, 1),
 (0, 2),
 (1, 3),
 (2, 3),
 (0, 4),
 (1, 4),
 (3, 5),
 (4, 6),
 (5, 6),
 (0, 7),
 (2, 7),
 (3, 7),
 (6, 7),
 (0, 8),
 (1, 8),
 (3, 8),
 (0, 9),
 (3, 9),
 (4, 9),
 (6, 9),
 (0, 10),    node10 has more than 5 edges.
 (2, 10),
 (3, 10),
 (5, 10),
 (7, 10),
 (8, 10),
 (1, 11),
 (2, 11),
 (4, 11),
 (9, 11)]
"""
4

1 回答 1

0

您不能仅知道顶点数、边数和每个顶点的边数来创建唯一的平面图。一个简单的反例：

以您的立方体示例为例，每个顶点有 8 个顶点、12 条边和 3 条边，那么您可以拥有：

[
  (A,B),(B,C),(C,D),(D,A), # top face of the cube.
  (E,F),(F,G),(G,H),(H,E), # bottom face of the cube.
  (A,E),(B,F),(C,G),(D,H)  # sides of the cube connecting top and bottom.
]

这将创建一个具有 6 个面的平面图，其中每个面都有 4 条边。

您同样可以拥有：

[
  (A,B),(B,C),(C,D),(D,E),(E,F),(F,G),(G,H),(H,A), # cycle containing all vertices
  (A,C), # connect vertices 2 apart on the cycle.
  (B,D), # overlap previous and also connect vertices 2 apart on the cycle.
  (E,G), # connect vertices 2 apart on the cycle.
  (F,H)  # overlap previous and also connect vertices 2 apart on the cycle.
]

这将创建一个平面图，其中包含 4 个三角形面和 2 个以 6 条边为界的面。

于 2021-11-01T15:32:20.773 回答