在无向图中找到所有无弦环 [英] Find all chordless cycles in an undirected graph

问题描述

如何在无向图中找到所有无弦环?

How to find all chordless cycles in an undirected graph?

例如，给定图表

0 --- 1
|     | 
|     |  
4 --- 3 - 2

算法应该返回 1-2-3 和 0-1-3-4，但永远不会返回 0-1-2-3-4.

the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4.

(注意:[1] 这个问题与 在平面图中寻找小环 因为该图不一定是平面图.[2] 我已经阅读了论文 根据排除原理生成所有循环、无弦循环和哈密顿循环 但我不明白他们在做什么:).[3] 我试过 CYPATH但是程序只给出了计数，readme.txt中的算法EnumChordlessPath有明显的错别字，C代码一团糟.[4] 我不是想找到一组任意的 基本周期.循环基础可以有和弦.)

(Note: [1] This question is not the same as small cycle finding in a planar graph because the graph is not necessarily planar. [2] I have read the paper Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion but I don't understand what they're doing :). [3] I have tried CYPATH but the program only gives the count, algorithm EnumChordlessPath in readme.txt has significant typos, and the C code is a mess. [4] I am not trying to find an arbitrary set of fundametal cycles. Cycle basis can have chords.)

推荐答案

从 1 到 n 为节点分配数字.

Assign numbers to nodes from 1 to n.

1. 选择节点编号 1.将其命名为A".

1. Pick the node number 1. Call it 'A'.

枚举来自A"的链接对.

Enumerate pairs of links coming out of 'A'.

选择一个.让我们将 B 小于 C 的相邻节点称为B"和C".

Pick one. Let's call the adjacent nodes 'B' and 'C' with B less than C.

如果 B 和 C 连接，则输出循环 ABC，返回步骤 3 并选择不同的对.

If B and C are connected, then output the cycle ABC, return to step 3 and pick a different pair.

如果 B 和 C 没有连接:

If B and C are not connected:

• 枚举连接到 B 的所有节点.假设它连接到 D、E 和 F.创建向量 CABD、CABE、CABF 的列表.对于每一个:
• 如果最后一个节点连接到除 C 和 B 之外的任何内部节点，则丢弃向量
• 如果最后一个节点连接到C，则输出并丢弃
• 如果它没有连接到任何一个，创建一个新的向量列表，附加最后一个节点连接到的所有节点.

重复直到用完向量.

对所有对重复步骤 3-5.

Repeat steps 3-5 with all pairs.

删除节点 1 和所有指向它的链接.选择下一个节点并返回到步骤 2.

Remove node 1 and all links that lead to it. Pick the next node and go back to step 2.

您可以取消一个嵌套循环.

and you can do away with one nested loop.

这乍一看似乎有效，可能存在错误，但您应该明白:

This seems to work at the first sight, there may be bugs, but you should get the idea:

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}

这篇关于在无向图中找到所有无弦环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！