彩色数 (chromatic number)
(include/emthrm/graph/chromatic_number.hpp)

• View this file on GitHub
• Last update: 2023-02-24 21:17:22+09:00
• Include: #include "emthrm/graph/chromatic_number.hpp"

隣接頂点間で色が異なるような頂点彩色に必要な最小の色の数である。

時間計算量

$O(2^{\lvert V \rvert} \lvert V \rvert)$

仕様

名前	戻り値
template <typename CostType> int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph);	無向グラフ $\mathrm{graph}$ の彩色数

参考文献

• https://www.slideshare.net/wata_orz/ss-12131479
• http://drken1215.hatenablog.com/entry/2019/01/16/030000
• https://www.learning-algorithms.com/entry/2018/01/27/235959
• https://github.com/spaghetti-source/algorithm/blob/b541e0b06aa4145592527b7de8e2caa8720bac22/graph/chromatic_number.cc

TODO

• 高速化
  • https://www.mathenachia.blog/chromatic-fast/
  • https://atcoder.jp/contests/abc056/editorial/2092
• 二部グラフの辺彩色
  • https://ei1333.hateblo.jp/entry/2020/08/25/015955
  • https://37zigen.com/noga-alon-edge-coloring-bipartite/
  • https://github.com/yosupo06/library-checker-problems/issues/393
  • https://twitter.com/snuke_/status/1246630370415538176
  • https://twitter.com/noshi91/status/1247010856040165377
  • https://github.com/ei1333/library/blob/master/structure/union-find/bipartite-graph.cpp
  • http://www.prefield.com/algorithm/graph/bipartite_coloring.html
  • https://judge.yosupo.jp/problem/bipartite_edge_coloring
  • https://yukicoder.me/problems/no/3071
• $#k$-彩色 ($#k$-coloring)
  • https://atcoder.jp/contests/abc294/tasks/abc294_h
  • https://twitter.com/noshi91/status/1637451650402234373
• 彩色多項式
  • https://github.com/eandbsoftware/libraryCPP/blob/master/%23ChromaticPolynomial.cpp

Submissons

https://judge.yosupo.jp/submission/40942

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/彩色数 (test/graph/chromatic_number.test.cpp)

Code

#ifndef EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_
#define EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_

#include <bit>
#include <numeric>
#include <ranges>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> adj(n, 0);
  for (int i = 0; i < n; ++i) {
    for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
      adj[i] |= 1 << e;
    }
  }
  std::vector<int> indep(1 << n);
  indep[0] = 1;
  for (unsigned int i = 1; i < (1 << n); ++i) {
    const int v = std::countr_zero(i);
    indep[i] = indep[i ^ (1 << v)] + indep[(i ^ (1 << v)) & ~adj[v]];
  }
  int res = n;
  for (const int mod : std::vector<int>{1000000007, 1000000011}) {
    std::vector<long long> f(1 << n);
    for (unsigned int i = 0; i < (1 << n); ++i) {
      f[i] = ((n - std::popcount(i)) & 1 ? mod - 1 : 1);
    }
    for (int c = 1; c < res; ++c) {
      for (int i = 0; i < (1 << n); ++i) {
        f[i] = (f[i] * indep[i]) % mod;
      }
      if (std::reduce(f.begin(), f.end(), 0LL) % mod > 0) {
        res = c;
        break;
      }
    }
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_CHROMATIC_NUMBER_HPP_

#line 1 "include/emthrm/graph/chromatic_number.hpp"



#include <bit>
#include <numeric>
#include <ranges>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/chromatic_number.hpp"

namespace emthrm {

template <typename CostType>
int chromatic_number(const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> adj(n, 0);
  for (int i = 0; i < n; ++i) {
    for (const int e : graph[i] | std::views::transform(&Edge<CostType>::dst)) {
      adj[i] |= 1 << e;
    }
  }
  std::vector<int> indep(1 << n);
  indep[0] = 1;
  for (unsigned int i = 1; i < (1 << n); ++i) {
    const int v = std::countr_zero(i);
    indep[i] = indep[i ^ (1 << v)] + indep[(i ^ (1 << v)) & ~adj[v]];
  }
  int res = n;
  for (const int mod : std::vector<int>{1000000007, 1000000011}) {
    std::vector<long long> f(1 << n);
    for (unsigned int i = 0; i < (1 << n); ++i) {
      f[i] = ((n - std::popcount(i)) & 1 ? mod - 1 : 1);
    }
    for (int c = 1; c < res; ++c) {
      for (int i = 0; i < (1 << n); ++i) {
        f[i] = (f[i] * indep[i]) % mod;
      }
      if (std::reduce(f.begin(), f.end(), 0LL) % mod > 0) {
        res = c;
        break;
      }
    }
  }
  return res;
}

}  // namespace emthrm

Back to top page