Chromatic Number
(graph/chromatic_number.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/chromatic_number.hpp"

Description

グラフの彩色数は，グラフの隣り合う頂点の色が異なるように頂点を彩色するために必要な最小の色の数である．

Operations

• int chromatic_number(vector<vector<bool>> G)
  • グラフ $G$ の隣接行列が与えられたとき，$G$ の彩色数を求める
  • 時間計算量: $O(n 2^n)$

Reference

• 指数時間アルゴリズム入門

Verified with

• test/yosupo/chromatic_number.test.cpp

Code

#pragma once
#include <bit>
#include <vector>

int chromatic_number(std::vector<std::vector<bool>>& G) {
    const int n = G.size();
    std::vector<int> neighbor(n);
    for (int i = 0; i < (int)G.size(); ++i) {
        for (int j = 0; j < (int)G.size(); ++j) {
            if (G[i][j]) neighbor[i] |= 1 << j;
        }
    }
    // number of subsets of S that are independent
    std::vector<int> ind(1 << n);
    ind[0] = 1;
    for (int S = 1; S < (1 << n); ++S) {
        int v = std::countr_zero((unsigned int)S);
        // (not containing v) + (containing v)
        ind[S] = ind[S ^ (1 << v)] + ind[(S ^ (1 << v)) & ~neighbor[v]];
    }
    // number of ways to choose k subsets of S that are independent
    auto f = ind;
    for (int k = 1;; ++k) {
        // numer of ways to choose k subsets of S so that they cover S
        int g = 0;
        for (int S = 0; S < (1 << n); ++S) {
            g += (std::popcount((unsigned int)S) & 1 ? -1 : 1) * f[S];
        }
        if (g) return k;
        for (int S = 1; S < (1 << n); ++S) {
            f[S] *= ind[S];
        }
    }
}

#line 2 "graph/chromatic_number.hpp"
#include <bit>
#include <vector>

int chromatic_number(std::vector<std::vector<bool>>& G) {
    const int n = G.size();
    std::vector<int> neighbor(n);
    for (int i = 0; i < (int)G.size(); ++i) {
        for (int j = 0; j < (int)G.size(); ++j) {
            if (G[i][j]) neighbor[i] |= 1 << j;
        }
    }
    // number of subsets of S that are independent
    std::vector<int> ind(1 << n);
    ind[0] = 1;
    for (int S = 1; S < (1 << n); ++S) {
        int v = std::countr_zero((unsigned int)S);
        // (not containing v) + (containing v)
        ind[S] = ind[S ^ (1 << v)] + ind[(S ^ (1 << v)) & ~neighbor[v]];
    }
    // number of ways to choose k subsets of S that are independent
    auto f = ind;
    for (int k = 1;; ++k) {
        // numer of ways to choose k subsets of S so that they cover S
        int g = 0;
        for (int S = 0; S < (1 << n); ++S) {
            g += (std::popcount((unsigned int)S) & 1 ? -1 : 1) * f[S];
        }
        if (g) return k;
        for (int S = 1; S < (1 << n); ++S) {
            f[S] *= ind[S];
        }
    }
}

Back to top page