如何用nauty（C版本）生成n阶非同构非二分连通图？求替代算法

背景 #

已知nauty工具的geng命令可生成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 API，生成连通图后过滤二分图：

1. 调用geng接口生成所有n顶点连通图（对应命令行geng n -c）
2. 对每个生成的图，用BFS染色法判断是否为二分图：给顶点交替染色，若相邻顶点出现同色则为非二分图；也可检查图是否包含奇环（二分图等价于无环或所有环均为偶环）
3. 收集并处理所有非二分连通图

核心逻辑示例（C风格）：

struct graph g;
int n = 6;
// 初始化生成n顶点连通图
init_geng(n, "-c");

while (next_graph(&g)) {
    if (!is_bipartite(&g)) {
        // 保存或处理该非二分连通图
        process_graph(&g);
    }
}

直接生成非二分连通图的算法 #

无需先全量生成再过滤，可直接构造：

• 奇环扩展法：从三角形（3顶点奇环）出发，逐步添加顶点并连接到图中任意顶点，保证连通性的同时，因奇环存在，图始终为非二分图
• 二分图改造法：先生成连通二分图，再在同一顶点分区内添加一条边（引入奇环），得到非二分连通图；结合nauty的同构检测可避免生成重复图

命令行管道过滤方案 #

若使用nauty命令行工具，可通过管道结合自定义C脚本过滤：

geng 6 -c | ./filter_non_bipartite

其中filter_non_bipartite为自定义程序，读取geng输出的图数据，判断是否为二分图，仅输出非二分图结果。

内容的提问来源于stack exchange，提问作者licheng