Tìm tất cả các chu kỳ không đổi trong một đồ thị vô hướng

Question

Làm cách nào để tìm tất cả chordless cycles trong biểu đồ không bị chiếu xạ?

Ví dụ, với đồ thị

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

thuật toán nên trở về 1-2-3 và 0-1-3-4, nhưng không bao giờ 0-1-2-3-4.

---

(Lưu ý: [1] Câu hỏi này là không giống như small cycle finding in a planar graph vì đồ thị là không nhất thiết phải phẳng [2] Tôi đã đọc các giấy Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion nhưng tôi không hiểu những gì họ. đang làm :). [3] Tôi đã thử CYPATH nhưng chương trình chỉ cung cấp số lượng, thuật toán EnumChordlessPath trong readme.txt có lỗi chính tả đáng kể và mã C là một mớ hỗn độn. [4] Tôi không cố gắng tìm một tập hợp tùy ý là fundametal cycles. Cơ sở chu kỳ có thể có hợp âm.)

Answer 1

Gán số cho các nút từ 1 đến n.

1. Chọn số nút 1. Gọi tên là 'A'.

2. Liệt kê các cặp liên kết sắp ra từ 'A'.

3. Chọn một. Hãy gọi các nút lân cận 'B' và 'C' với B nhỏ hơn C.

4. Nếu B và C được kết nối, sau đó xuất chu trình ABC, quay lại bước 3 và chọn một cặp khác.

5. Nếu B và C are not connected:

   • liệt kê tất cả các nút kết nối với B. Giả sử nó kết nối với D, E, và F. Tạo một danh sách các vectơ CABD, CABE, CABF. Đối với mỗi:
   • nếu nút cuối cùng được kết nối với bất kỳ nút nội trừ C và B, loại bỏ các vector
   • nếu nút cuối cùng được kết nối với C, sản lượng và loại bỏ
   • nếu nó không được kết nối với một trong hai , tạo danh sách các vectơ mới, thêm tất cả các nút mà nút cuối cùng được kết nối.

   Lặp lại cho đến khi bạn hết các vectơ.

6. Lặp lại các bước 3-5 với tất cả các cặp.

7. Xóa nút 1 và tất cả các liên kết dẫn đến nút đó. Chọn nút tiếp theo và quay lại bước 2.

Chỉnh sửa: và bạn có thể thực hiện với một vòng lặp lồng nhau.

Điều này dường như làm việc ở cái nhìn đầu tiên, có thể có lỗi, nhưng bạn sẽ nhận được các ý tưởng:

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); 
       } 
      } 
     } 
    } 
} 

Answer 2

@aioobe có một điểm. Chỉ cần tìm tất cả các chu kỳ và sau đó loại trừ những người không phải là vô điều kiện. Điều này có thể quá kém hiệu quả, nhưng không gian tìm kiếm có thể được cắt tỉa dọc theo cách để giảm sự thiếu hiệu quả. Dưới đây là một thuật toán chung:

void printChordlessCycles(ChordlessCycle path) { 

    System.out.println(path.toString()); 
    for(Node n : path.lastNode().neighbors()) { 

    if(path.canAdd(n)) { 

     path.add(n); 
     printChordlessCycles(path); 
     path.remove(n); 
    } 
    } 
} 

Graph g = loadGraph(...); 
ChordlessCycle p = new ChordlessCycle(); 
for(Node n : g.getNodes()) { 
    p.add(n); 
    printChordlessCycles(p); 
    p.remove(n); 
} 

class ChordlessCycle { 
    private CountedSet<Node> connected_nodes; 
    private List<Node> path; 

    ... 

    public void add(Node n) { 
    for(Node neighbor : n.getNeighbors()) { 
     connected_nodes.increment(neighbor); 
    } 
    path.add(n); 
    } 

    public void remove(Node n) { 
    for(Node neighbor : n.getNeighbors()) { 
     connected_nodes.decrement(neighbor); 
    } 
    path.remove(n); 
    } 

    public boolean canAdd(Node n) { 
    return (connected_nodes.getCount(n) == 0); 
    } 
} 

Answer 3

Làm thế nào về việc này. Đầu tiên, giảm bớt vấn đề để tìm tất cả các chu kỳ không đổi mà đi qua đỉnh A. Một khi bạn đã tìm thấy tất cả, bạn có thể loại bỏ A khỏi đồ thị, và lặp lại với một điểm khác cho đến khi không còn gì.

Và làm cách nào để tìm tất cả các chu kỳ không đổi mà đi qua đỉnh A? Giảm điều này để tìm tất cả các đường đi vô tận từ B đến A, đưa ra một danh sách các đỉnh được phép và tìm kiếm một trong hai chiều rộng đầu tiên hoặc chiều sâu. Lưu ý rằng khi lặp qua các đỉnh có thể truy cập (trong một bước) từ B, khi bạn chọn một trong số chúng, bạn phải loại bỏ tất cả những cái khác khỏi danh sách các đỉnh được phép (chú ý đặc biệt khi B = A, để không loại bỏ ba đường dẫn).

Answer 4

Chỉ cần một ý nghĩ:

Hãy nói rằng bạn đang liệt kê chu kỳ trên ví dụ đồ thị của bạn và bạn đang bắt đầu từ nút 0.

Nếu bạn làm một tìm kiếm theo chiều rộng cho mỗi cạnh nhất định, ví dụ 0 - 1, bạn đạt đến một ngã ba tại 1. Sau đó, các chu kỳ đạt 0 lần nữa đầu tiên là vô số, và phần còn lại là không và có thể được loại bỏ ... ít nhất tôi nghĩ rằng đây là trường hợp.

Bạn có thể sử dụng phương pháp như thế này không? Hoặc là có một counterexample?

Answer 5

Tìm tất cả các chu kỳ.

Định nghĩa chu trình không đổi là một tập hợp các điểm trong đó chu kỳ tập hợp con của những điểm đó không tồn tại. Vì vậy, một khi bạn có tất cả các vấn đề chu kỳ chỉ đơn giản là để loại bỏ chu kỳ mà có một chu kỳ tập hợp con.

Để đạt hiệu quả, cho mỗi chu kỳ bạn tìm thấy, lặp qua tất cả các chu kỳ hiện tại và xác minh rằng nó không phải là tập con của chu kỳ khác hoặc ngược lại, và nếu có, hãy loại bỏ chu kỳ lớn hơn.

Ngoài ra, chỉ khó khăn là tìm ra cách viết một thuật toán xác định xem tập hợp có phải là tập hợp con của nhóm khác hay không.