r - 如何在 R 中绘制哈密顿图？

Question

我有以下无向图(图片)，其中包含一个循环或长度为 |V|= 8 的哈密顿路径。没有重复边和顶点的循环(路径)是红线。邻接矩阵是:

<表类="s-表"><头>ABCDEFGH<正文>A01011000B10100100C01010001D10100010E10000110F01001001G00011001H00100110

如何在 R 中绘制此图？

Ham = matrix(c(0,1,0,1,1,0,0,0,
             1,0,1,0,0,1,0,0,
             0,1,0,1,0,0,0,1,
             1,0,1,0,0,0,1,0,
             1,0,0,0,0,1,1,0,
             0,1,0,0,1,0,0,1,
             0,0,0,1,1,0,0,1,
             0,0,1,0,0,1,1,0),8,8)
Ham

Answer 1

更新

如果你只需要所有汉密尔顿圈中的一个，你可以尝试graph.subisomorphic.lad(感谢@Szabolcs 的建议)，如果你不需要，它会加快很多列出所有的可能性，例如，

g <- graph_from_adjacency_matrix(Ham, "undirected")
es <- graph.subisomorphic.lad(make_ring(vcount(g)), g)$map
g %>%
  set_edge_attr("color", value = "black") %>%
  set_edge_attr("color",
    get.edge.ids(g, c(rbind(es, c(es[-1], es[1])))),
    value = "red"
  ) %>%
  plot()

---

如果你想找到所有的汉密尔顿圆:

你应该知道汉密尔顿圆同构于一个由所有顶点组成的环，所以我们可以求助于 subgraph_isomorphisms 来找出所有这些类型的“环”，例如，

g <- graph_from_adjacency_matrix(Ham, "undirected")
lst <- lapply(
  subgraph_isomorphisms(make_ring(vcount(g)), g),
  function(es) {
    g %>%
      set_edge_attr("color", value = "black") %>%
      set_edge_attr("color",
        get.edge.ids(g, c(rbind(es, c(es[-1], es[1])))),
        value = "red"
      )
  }
)

其中lst是一个图表列表，可以看到

1. plot(lst[[1]] 给出
2. plot(lst[[2]] 给出

等等等等。