Chromatic Number(彩色数) (graph/others/chromatic-number.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "graph/others/chromatic-number.hpp"
• Link: https://www.slideshare.net/wata_orz/ss-12131479

概要

グラフの彩色数を求める. 彩色数とは, 隣接する頂点が異なる色となるように彩色するために必要な最小色数である.

あるグラフが $k$ 彩色可能であることと, $k$ 個の独立集合で被覆できることは必要十分条件である. つまり独立集合から $k$ 個の頂点を選んで被覆する方法の総数が求まれば良い. これはbit DPと包除原理を用いて効率的に求められる.

使い方

• chromatic_number(g): 隣接行列 g で表されるグラフの彩色数を求める.

計算量

• $O(2^N N)$

Verified with

• test/verify/aoj-1254.test.cpp
• test/verify/yosupo-chromatic-number.test.cpp

Code

#pragma once

/**
 * @brief Chromatic Number(彩色数)
 * 
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */
template< typename Matrix >
int chromatic_number(Matrix &g) {
  int N = (int) g.size();
  vector< int > es(N);
  for(int i = 0; i < (int) g.size(); i++) {
    for(int j = 0; j < (int) g.size(); j++) {
      if(g[i][j] != 0) es[i] |= 1 << j;
    }
  }
  vector< int > ind(1 << N);
  ind[0] = 1;
  for(int S = 1; S < (1 << N); S++) {
    int u = __builtin_ctz(S);
    ind[S] = ind[S ^ (1 << u)] + ind[(S ^ (1 << u)) & ~es[u]];
  }
  vector< int > cnt((1 << N) + 1);
  for(int i = 0; i < (1 << N); i++) {
    cnt[ind[i]] += __builtin_parity(i) ? -1 : 1;
  }
  vector< pair< unsigned, int > > hist;
  for(int i = 1; i <= (1 << N); i++) {
    if(cnt[i]) hist.emplace_back(i, cnt[i]);
  }
  constexpr int mods[] = {1000000007, 1000000011, 1000000021};
  int ret = N;
  for(int k = 0; k < 3; k++) {
    auto buf = hist;
    for(int c = 1; c < ret; c++) {
      int64_t sum = 0;
      for(auto&[i, x] : buf) {
        sum += (x = int64_t(x) * i % mods[k]);
      }
      if(sum % mods[k]) ret = c;
    }
  }
  return ret;
}

#line 2 "graph/others/chromatic-number.hpp"

/**
 * @brief Chromatic Number(彩色数)
 * 
 * @see https://www.slideshare.net/wata_orz/ss-12131479
 */
template< typename Matrix >
int chromatic_number(Matrix &g) {
  int N = (int) g.size();
  vector< int > es(N);
  for(int i = 0; i < (int) g.size(); i++) {
    for(int j = 0; j < (int) g.size(); j++) {
      if(g[i][j] != 0) es[i] |= 1 << j;
    }
  }
  vector< int > ind(1 << N);
  ind[0] = 1;
  for(int S = 1; S < (1 << N); S++) {
    int u = __builtin_ctz(S);
    ind[S] = ind[S ^ (1 << u)] + ind[(S ^ (1 << u)) & ~es[u]];
  }
  vector< int > cnt((1 << N) + 1);
  for(int i = 0; i < (1 << N); i++) {
    cnt[ind[i]] += __builtin_parity(i) ? -1 : 1;
  }
  vector< pair< unsigned, int > > hist;
  for(int i = 1; i <= (1 << N); i++) {
    if(cnt[i]) hist.emplace_back(i, cnt[i]);
  }
  constexpr int mods[] = {1000000007, 1000000011, 1000000021};
  int ret = N;
  for(int k = 0; k < 3; k++) {
    auto buf = hist;
    for(int c = 1; c < ret; c++) {
      int64_t sum = 0;
      for(auto&[i, x] : buf) {
        sum += (x = int64_t(x) * i % mods[k]);
      }
      if(sum % mods[k]) ret = c;
    }
  }
  return ret;
}

Back to top page