graph6 格式如何工作？

Question

我一直在到处寻找 .g6 或 graph6 格式的工作原理，但我什至不知道它是如何工作的，我发誓它就像魔术一样。

F?B~w

那是以 ASCII 形式表示的图形。它可以由 Wolfram Mathematica、Sage 和 Maple 解释，仅举几例，并为我们提供视觉效果。然而，在深入研究 Sage 的开源代码数小时后，我终生无法弄清楚他们如何将其解读为图表。

我想知道是否可以在上面的图中搜索哈密顿循环而不必将它们转换为邻接矩阵？或者，如果这不可能，我们如何将其转换为邻接矩阵？

任何帮助，将不胜感激。

Answer 1

Oliver Charlesworth 已经提供了对格式描述的参考，但简而言之，基本思想是将图形大小和邻接矩阵的上三角形编码为 ASCII 可打印字符。

1. 从原始无向图中，计算邻接矩阵。这保证是对称的，所以我们只关心这个矩阵的上三角形，不包括完全为零的对角线。

2. 接下来，n*(n-1)/2通过逐行遍历矩阵的上三角形来构建大小的位向量。例如，对于 4x4 矩阵，遍历将是 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)。

3. 在您的位向量前面加上图形大小 n（作为一个二进制字），并将生成的位向量分解为每个 6 位的块。

4. 将每个 6 位块转换为 63 到 126 范围内的整数，然后将每个转换为相应的 ASCII 字符并将它们连接起来。

请注意，graph6 格式不支持有向图或加权图。我相信它是由 Brendan McKay 创建的（在nauty 源中有一个它的实现）并且有两种相关的格式：sparse6（用于稀疏图）和 digraph6（用于有向图）。

digraph6 格式似乎相当新（在 nauty 2.6 中添加）并且类似于 graph6，除了为了处理有向图，该格式编码整个邻接矩阵减去对角线，而不仅仅是上三角形。