Bỏ qua

Clique cực đại

Kiến thức nền tảng: Khái niệm về Clique (Đoàn)

Giới thiệu

Trong khoa học máy tính, bài toán clique (đoàn) là bài toán tìm một clique (tập con các đỉnh mà mọi cặp đều kề nhau, còn gọi là đồ thị con đầy đủ) trong một đồ thị cho trước.

Bài toán clique cũng xuất hiện trong thực tế. Ví dụ, xét một mạng xã hội, mỗi đỉnh là một người dùng, mỗi cạnh là hai người quen biết nhau. Khi tìm được một clique, tức là tìm được một nhóm người mà ai cũng quen biết nhau.

Nếu muốn tìm nhóm lớn nhất mà mọi người đều quen biết nhau trong mạng xã hội này, ta cần thuật toán tìm clique lớn nhất.

Khái niệm clique cực đại đã được giới thiệu, clique lớn nhất là clique cực đại có số đỉnh nhiều nhất.

Giải thích

Ý tưởng là sử dụng đệ quy và quay lui (backtrack), dùng một danh sách lưu các đỉnh, mỗi lần thêm một đỉnh vào đều kiểm tra xem các đỉnh này còn tạo thành một clique không. Nếu thêm vào mà không còn là clique, thì quay lui về trạng thái trước, thử đỉnh khác.

Lý do dùng quay lui là vì ta không biết trước một đỉnh \(v\) cuối cùng có thuộc clique lớn nhất hay không. Nếu chọn \(v\) mà không tìm được clique lớn nhất, cần quay lui và thử nghiệm các clique không chứa \(v\).

Quy trình

Thuật toán Bron–Kerbosch tối ưu hóa ý tưởng này. Dạng cơ bản là đệ quy với ba tập hợp: \(R\), \(P\), \(X\). Các bước như sau:

  1. Khởi tạo \(R, X\) rỗng, \(P\) là tập tất cả các đỉnh của đồ thị.
  2. Mỗi lần lấy một đỉnh \(v\) từ \(P\), khi cả \(P\) và \(X\) đều rỗng thì có hai trường hợp:
    1. \(R\) là một clique cực đại, khi đó \(X\) rỗng
    2. Không phải clique cực đại, khi đó quay lui
  3. Với mỗi đỉnh \(v\) lấy từ \(P\):
    1. Thêm \(v\) vào \(R\), sau đó đệ quy với \(R, P, X\)
    2. Xóa \(v\) khỏi \(P\), thêm \(v\) vào \(X\)
    3. Nếu cả \(P\) và \(X\) đều rỗng, \(R\) là clique lớn nhất

Phương pháp này còn có thể tối ưu thêm. Để tăng tốc quay lui, có thể chọn đỉnh chốt (pivot vertex) để tìm kiếm. Một cách khác là sắp xếp các đỉnh ngay từ đầu, khi liệt kê thì theo thứ tự chỉ số để tránh lặp lại.

Cài đặt

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
R := {}
P := node set of G 
X := {}

BronKerbosch1(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

C++ Implementation

Mã nguồn minh họa 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 105;

struct MaxClique {
  bool g[MAXN][MAXN];
  int n, dp[MAXN], st[MAXN][MAXN], ans;

  // dp[i]表示第i个点之后能组成的最大团的大小，
  // st[i][j]表示算法中第i层dfs所需要的点的集合，保存有可能是最大团其中之一的点

  void init(int n) {
    this->n = n;
    memset(g, false, sizeof(g));
  }

  void addedge(int u, int v, int w) { g[u][v] = w; }

  bool dfs(int sz, int num) {
    if (sz == 0) {
      if (num > ans) {
        ans = num;
        return true;
      }
      return false;
    }
    for (int i = 0; i < sz; i++) {  // 在第num层的集合中枚举一个点i
      if (sz - i + num <= ans) return false;  // 剪枝1
      int u = st[num][i];
      if (dp[u] + num <= ans) return false;  // 剪枝2
      int cnt = 0;
      for (
          int j = i + 1; j < sz;
          j++) {  // 在第num层遍历在i之后的且与i所相连的点，并且加入第num+1层集合
        if (g[u][st[num][j]]) st[num + 1][cnt++] = st[num][j];
      }
      if (dfs(cnt, num + 1)) return true;
    }
    return false;
  }

  int solver() {
    ans = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = n; i >= 1; i--) {
      int cnt = 0;
      for (int j = i + 1; j <= n; j++) {  // 初始化第1层集合
        if (g[i][j]) st[1][cnt++] = j;
      }
      dfs(cnt, 1);
      dp[i] = ans;
    }
    return ans;
  }

} maxclique;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  while (cin >> n, n) {
    maxclique.init(n);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        int x;
        cin >> x;
        maxclique.addedge(i, j, x);
      }
    }
    cout << maxclique.solver() << '\n';
  }
  return 0;
}

Bài tập ví dụ

POJ 2989: All Friends

Đề bài: Có \(n\) người, \(m\) cặp bạn bè, hỏi số lượng clique lớn nhất.

Ý tưởng: Bài mẫu, dùng thuật toán Bron–Kerbosch.

Pseudocode:

1
2
3
4
5
6
7
8
 BronKerbosch(All, Some, None):  
     if Some and None are both empty:  
         report All as a maximal clique // Tất cả đỉnh đã chọn, không còn đỉnh không chọn, cộng đáp án  
     for each vertex v in Some: // Duyệt từng đỉnh trong Some  
         BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))   
         // Thêm v vào All, chỉ những người là bạn với v mới có thể tiếp tục, None cũng chỉ giữ lại các đỉnh là bạn với v  
         Some := Some - {v} // Đã duyệt xong, xóa khỏi Some, thêm vào None  
         None := None ⋃ {v}

Để tăng tốc và giảm lặp, có thể chọn pivot \(v\) để tối ưu.

Như đã nói, thuật toán trên có nhiều phép tính lặp lại các clique cực đại đã xét.

Xét ba tập \(R, P, X\):

Chọn một đỉnh \(u\) trong \(P\cup X\), muốn cùng \(R\) tạo thành clique cực đại thì chỉ cần xét các đỉnh trong \(P\cap N(u)\) (\(N(u)\) là tập đỉnh kề \(u\)).

Nếu sau khi chọn \(u\) mà các đỉnh kề \(u\) như \(v\) cũng có thể vào clique cực đại, thì chỉ cần chọn \(u\) là đủ. Như vậy giảm được lặp lại với \(v\). Sau đó chỉ cần xét các đỉnh không kề \(u\).

Cài đặt C++ tối ưu hóa:

Mã nguồn minh họa 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 130;
bool mp[MAXN][MAXN];
int some[MAXN][MAXN], none[MAXN][MAXN], all[MAXN][MAXN];
int n, m, ans;

void dfs(int d, int an, int sn, int nn) {
  if (!sn && !nn) ++ans;
  int u = some[d][0];
  for (int i = 0; i < sn; ++i) {
    int v = some[d][i];
    if (mp[u][v]) continue;
    for (int j = 0; j < an; ++j) all[d + 1][j] = all[d][j];
    all[d + 1][an] = v;
    int tsn = 0, tnn = 0;
    for (int j = 0; j < sn; ++j)
      if (mp[v][some[d][j]]) some[d + 1][tsn++] = some[d][j];
    for (int j = 0; j < nn; ++j)
      if (mp[v][none[d][j]]) none[d + 1][tnn++] = none[d][j];
    dfs(d + 1, an + 1, tsn, tnn);
    some[d][i] = 0, none[d][nn++] = v;
    if (ans > 1000) return;
  }
}

int work() {
  ans = 0;
  for (int i = 0; i < n; ++i) some[1][i] = i + 1;
  dfs(1, 0, n, 0);
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n >> m) {
    memset(mp, 0, sizeof mp);
    for (int i = 1; i <= m; ++i) {
      int u, v;
      cin >> u >> v;
      mp[u][v] = mp[v][u] = true;
    }
    int tmp = work();
    if (tmp > 1000)
      cout << "Too many maximal sets of friends.\n";
    else
      cout << tmp << '\n';
  }
  return 0;
}

Bài tập

Tài liệu tham khảo

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Persdre
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply