生成所有n阶非同构非二分连通图

Question

我知道nauty可以生成n个顶点二分图（

!geng n -c -b

），但我还没有看到其相反的相应命令（非二分图）。 （我可能错过了。）

SageMath提供了一种过滤图表的方法，如下所示：

 s=[g for g in graphs.nauty_geng('-c 6') if g.is_bipartite()==False]
 len(s)

95

但我想问是否有更接近

nauty

的方法，例如使用C版本来获取非二分连通图。那是因为 nauty 是用 C 实现的。或者，是否有直接生成非二分图的算法？

Answer 1

当我问 Brendan McKay 时，他告诉我这可行。

pickg -~b

此外，

pickg

还可以做很多事情。

              Constraints:

              Numerical constraints (shown here with following  #)  can  take  a  single  integer
              value,  or  a  range  like #:#, #:, or :#.  Each can also be preceded by '~', which
              negates it.   (For example, -~D2:4 will match any maximum degree which is _not_  2,
              3,  or 4.)  Constraints are applied to all input graphs, and only those which match
              all constraints are counted or selected.

       -n#    number of vertices     -e#  number of edges

       -d#    minimum degree         -D#  maximum degree

       -m#    vertices of min degree -M#  vertices of max degree

       -r     regular                -b   bipartite

       -z#    radius                 -Z#  diameter

       -g#    girth (0=acyclic)      -Y#  total number of cycles

       -T#    number of triangles    -K#  number of maximal independent sets

       -H#    number of induced cycles

       -E     Eulerian (all degrees are even, connectivity not required)

       -a#    group size  -o# orbits  -F# fixed points  -t vertex-transitive

       -c#    connectivity (only implemented for 0,1,2).

       -i#    min common nbrs of adjacent vertices;     -I# maximum

       -j#    min common nbrs of non-adjacent vertices; -J# maximum