英文:
Generate all non-isomorphic non-bipartite connected graphs of order n
问题
我知道nauty可以生成n个顶点的bipartite graphs（二分图）（!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实现的。或者，是否有生成非二分图的直接算法？
英文:
I know that nauty can generate n-vertex bipartite graphs (!geng n -c -b), but I haven't seen a corresponding command for its opposite (non-bipartite graphs). (I might have missed it.)
SageMath provides a way to filter graphs as follows:
s=[g for g in graphs.nauty_geng('-c 6') if g.is_bipartite()==False]
len(s)
> 95
But I would like to ask if there is a closer approach to nauty, such as using a C version to obtain non-bipartite connected graphs. That's because nauty is implemented in C. Alternatively, is there a direct algorithm for generating non-bipartite graphs?
答案1
得分: 0
当我问 Brendan McKay 时，他告诉我这个可以工作。
pickg -~b
此外，pickg 可以做许多事情。
约束条件：
数值约束条件（以下以#表示）可以采用单个整数
值，或范围表示如#:#，#：或：#。每个约束条件也可以前面加上'~'，表示否定它。
（例如，-~D2:4 将匹配任何不是 2、3 或 4 的最大度数。）约束条件适用于所有输入图形，
只有那些满足所有约束条件的图形才会被计数或选择。
-n# 顶点数 -e# 边数
-d# 最小度数 -D# 最大度数
-m# 最小度数的顶点数 -M# 最大度数的顶点数
-r 正则图 -b 二分图
-z# 半径 -Z# 直径
-g# 回路长度（0=无回路） -Y# 总回路数
-T# 三角形数 -K# 最大独立集数
-H# 诱导回路数
-E 欧拉图（所有度数均为偶数，无需连通性）
-a# 群大小 -o# 轨道数 -F# 固定点数 -t 顶点可传递
-c# 连通性（仅对 0、1、2 实现）。
-i# 相邻顶点的最小公共邻居数； -I# 最大
-j# 非相邻顶点的最小公共邻居数； -J# 最大
英文:
When I asked Brendan McKay, he told me this can works.
pickg -~b
Besides, pickg can do many things.
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论