二部グラフの辺彩色

う？

見た目よりも簡単です

König's Line Coloring Theorem

König's Line Coloring Theorem -- from Wolfram MathWorld

任意の二部グラフの辺彩色数は, そのグラフの頂点の最大次数に一致する.

辺彩色の例

f:id:ei1333:20200825165144p:plain

次数の最大値が ${3}$ なので ${3}$ 色の辺彩色が存在する. 各頂点から生える色は相異なる.

実際の構成

左側の頂点数 ${L}$ , 右側の頂点数 ${R}$ , 辺の本数 ${M}$ とする. また頂点の最大次数(=辺彩色数) を ${D}$ とする. 以下では ${D}$ 色の彩色をする実際の構成方法を説明する.

次の2つのステップからなる.

D-正則二部グラフに変形する
D-正則二部グラフの辺彩色を求める

正則二部グラフ

アルゴリズム

正則グラフ は, すべての頂点の次数が等しいグラフである. 特に頂点の次数がすべて ${k}$ の正則グラフを k-正則グラフ と呼ぶ.

まず, 与えられたグラフを D-正則二部グラフ に変形することからはじめる. (当然 D-正則グラフの辺彩色数はもとのグラフの彩色数と一致する.)

左側, 右側それぞれについて, 足して ${D}$ 以下となる頂点がある場合はそれらを縮約して, 次数 ${\frac {D} {2}}$ 以下の頂点が左右それぞれ ${1}$ 個以下になるように変形する.
左右にダミーの頂点を追加して, 左右の頂点数を合わせる.
例が悪くすでに一致してしまった
次数が ${D}$ に満たない頂点にダミーの辺を追加して, D-正則二部グラフにする.

実装例

[縮約の実装] 縮約を楽に扱うために, Union Find で管理するといいかも. priority_queue で次数が小さい順に取り出せるようにして, top 2 を unite することを繰り返すとよい.

UnionFind contract(valarray< int > &deg, int k) {
  using pi = pair< int, int >;
  priority_queue< pi, vector< pi >, greater<> > que;
  for(int i = 0; i < (int) deg.size(); i++) {
    que.emplace(deg[i], i);
  }
  UnionFind uf(deg.size());
  while(que.size() > 1) {
    auto p = que.top();
    que.pop();
    auto q = que.top();
    que.pop();
    if(p.first + q.first > k) continue;
    p.first += q.first;
    uf.unite(p.second, q.second);
    que.emplace(p);
  }
  return uf;
}

[全体の実装] 普通に実装をする.

RegularGraph build_k_regular_graph(int L, int R, const vector< int > &A, const vector< int > &B) {
  valarray< int > deg[2];
  deg[0] = valarray< int >(L);
  deg[1] = valarray< int >(R);
  for(auto &p : A) deg[0][p]++;
  for(auto &p : B) deg[1][p]++;

  int k = max(deg[0].max(), deg[1].max());

  /* step 1 */
  UnionFind uf[2];
  uf[0] = contract(deg[0], k);
  uf[1] = contract(deg[1], k);

  vector< int > id[2];
  int ptr[] = {0, 0};
  id[0] = vector< int >(L);
  id[1] = vector< int >(R);
  for(int i = 0; i < L; i++) if(uf[0].find(i) == i) id[0][i] = ptr[0]++;
  for(int i = 0; i < R; i++) if(uf[1].find(i) == i) id[1][i] = ptr[1]++;

  /* step 2 */
  int N = max(ptr[0], ptr[1]);
  deg[0] = valarray< int >(N);
  deg[1] = valarray< int >(N);

  /* step 3 */
  vector< int > C, D;
  C.reserve(N * k);
  D.reserve(N * k);
  for(int i = 0; i < (int) A.size(); i++) {
    int u = id[0][uf[0].find(A[i])];
    int v = id[1][uf[1].find(B[i])];
    C.emplace_back(u);
    D.emplace_back(v);
    deg[0][u]++;
    deg[1][v]++;
  }
  int j = 0;
  for(int i = 0; i < N; i++) {
    while(deg[0][i] < k) {
      while(deg[1][j] == k) ++j;
      C.emplace_back(i);
      D.emplace_back(j);
      ++deg[0][i];
      ++deg[1][j];
    }
  }

  return {k, N, C, D};
}

k-正則二部グラフの辺彩色

k-正則二部グラフの辺彩色は, 分割統治によって効率的に求めることができる. 頂点の次数の偶奇で場合分けする.

すべての頂点の次数が偶数

各連結成分についてオイラー閉路を求める.

オイラー閉路で奇数番目に通った辺と偶数番目に通った辺の ${2}$ つに分けると, ${\frac {k} {2}}$ -正則二部グラフが ${2}$ つ生える. (それぞれの辺をオイラー路に基づいて向き付けすると, 各頂点について入次数も出次数も ${\frac {k} {2}}$ 回となる)

生えた ${2}$ つの正則二部グラフについて, 再帰的に求める.

f:id:ei1333:20200825172904p:plain

すべての頂点の次数が奇数

この場合はちょっと難しい. k-正則二部グラフの完全マッチング(求め方は後述) を求め, 完全マッチングに使われた辺と使われなかった辺に分ける.

(ちなみにHallの結婚定理より k-正則二部グラフには常に完全マッチングが存在することが示せる.)

使われた辺はそれらをすべて同じ色で塗る. 使われなかった辺からなるグラフを考えると ${k-1}$ 正則二部グラフになっている(完全マッチングなのでそれぞれの頂点の次数が ${1}$ ずつ減る).

生えた ${k-1}$ 正則二部グラフについて, 再帰的に求める.

f:id:ei1333:20200825171847p:plain

これらの操作により実際に ${D}$ 色の辺彩色を構成できる.

k-正則二部グラフの完全マッチング

k-正則二部グラフの完全マッチングがボトムネックとなるため, これを高速に求めることが重要である.

単純な方法としては最大流のアルゴリズムなどを用いて二部グラフの最大マッチングを求めればよい. Hopcroft-Karp または Dinic を用いると, ${N}$ 頂点の k-正則二部グラフの完全マッチングを求めるための計算量は ${O(Nk \sqrt N)}$ となる.

もっと賢いアルゴリズムを使うと ${O(Nk \log N)}$ とかになるらしいので, 興味がある人は調べてみてね( ${2^k}$ -正則二部グラフの辺彩色がオイラー閉路を繰り返し取ることで求まることを使う, 気が向いたら追記します).

実装例

[各連結成分についてオイラー閉路を求める] Hierholzer's Algorithm により, 辺の本数を ${E}$ として ${O(E)}$ で求められる(詳細はしらべてください). スタックを使うとなんかできる.

/* alive番目の辺たちを使ってオイラー路を構成する */
vector< int > euler_trail(const RegularGraph &rg, const vector< int > &alive) {
  int V = rg.n + rg.n;
  vector< vector< pair< int, int > > > g(V);
  int M = 0;
  for(auto &i : alive) {
    g[rg.A[i]].emplace_back(rg.B[i] + rg.n, M);
    g[rg.B[i] + rg.n].emplace_back(rg.A[i], M++);
  }
  vector< int > used_vertex(V), used_edge(M);
  vector< int > ans;
  for(int i = 0; i < V; i++) {
    if(used_vertex[i]) continue;
    stack< pair< int, int > > st;
    vector< int > ord;
    st.emplace(i, -1);
    while(!st.empty()) {
      int idx = st.top().first;
      used_vertex[idx] = true;
      if(g[idx].empty()) {
        ord.emplace_back(st.top().second);
        st.pop();
      } else {
        auto e = g[idx].back();
        g[idx].pop_back();
        if(used_edge[e.second]) continue;
        used_edge[e.second] = true;
        st.emplace(e);
      }
    }
    ord.pop_back();
    reverse(ord.begin(), ord.end());
    ans.insert(ans.end(), ord.begin(), ord.end());
  }
  for(auto &p : ans) p = alive[p];
  return ans;
}

[完全マッチング] Hopcroft Karp ってな～んだ？　なに　わたしの Hopcroft Karp はこちら！

struct HopcroftKarp {
  size_t n, m, time_stamp;
  vector< vector< int > > g, rg;
  vector< int > match_l, match_r, dist, used;

public:
  explicit HopcroftKarp(size_t n, size_t m) :
      n(n), m(m), g(n), rg(m), match_l(n, -1), match_r(m, -1), used(n), time_stamp(0) {}

  void add_edge(int u, int v) {
    g[u].push_back(v);
  }

  vector< pair< int, int > > max_matching() {
    for(;;) {
      build_augment_path();
      ++time_stamp;
      int flow = 0;
      for(int i = 0; i < n; i++) {
        if(match_l[i] == -1) flow += find_min_dist_augment_path(i);
      }
      if(flow == 0) break;
    }
    vector< pair< int, int > > ret;
    for(int i = 0; i < n; i++) {
      if(match_l[i] >= 0) ret.emplace_back(i, match_l[i]);
    }
    return ret;
  }

private:
  void build_augment_path() {
    queue< int > que;
    dist.assign(g.size(), -1);
    for(int i = 0; i < n; i++) {
      if(match_l[i] == -1) {
        que.emplace(i);
        dist[i] = 0;
      }
    }
    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : g[a]) {
        int c = match_r[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool find_min_dist_augment_path(int a) {
    used[a] = time_stamp;
    for(auto &b : g[a]) {
      int c = match_r[b];
      if(c < 0 || (used[c] != time_stamp && dist[c] == dist[a] + 1 && find_min_dist_augment_path(c))) {
        match_r[b] = a;
        match_l[a] = b;
        return true;
      }
    }
    return false;
  }
};

[分割統治により辺彩色を求める] 完全マッチングでは多重辺があるのでいい感じの処理をする

struct EdgeColorBip {
  const RegularGraph &g;
  vector< vector< int > > ans;

  explicit EdgeColorBip(const RegularGraph &g) : g(g) {}

  void rec(const vector< int > &ord, int k) {
    if(k == 0) {
      return;
    } else if(k == 1) {
      ans.emplace_back(ord);
      return;
    } else if((k & 1) == 0) {
      auto path = euler_trail(g, ord);
      vector< int > beet[2];
      for(int i = 0; i < (int) path.size(); i++) {
        beet[i & 1].emplace_back(path[i]);
      }
      rec(beet[0], k / 2);
      rec(beet[1], k / 2);
    } else {
      HopcroftKarp flow(g.n, g.n);
      for(auto &i : ord) flow.add_edge(g.A[i], g.B[i]);
      flow.max_matching();
      vector< int > beet;
      ans.emplace_back();
      for(auto &i : ord) {
        if(flow.match_l[g.A[i]] == g.B[i]) {
          flow.match_l[g.A[i]] = -1;
          ans.back().emplace_back(i);
        } else {
          beet.emplace_back(i);
        }
      }
      rec(beet, k - 1);
    }
  }

  vector< vector< int > > build() {
    vector< int > ord(g.A.size());
    iota(ord.begin(), ord.end(), 0);
    rec(ord, g.k);
    return ans;
  }
};

verify: https://judge.yosupo.jp/submission/19953

計算量

${O(M \sqrt N \log D)}$

定数倍は軽い気がするが, よくわからん

う

し

た

ぷ

じょ

えくん　おともだち

ら

らてまるたくん　研究　就活がんばってください

び

ーとくん　たくさんのお気持ち表明　たのしみにしています

ら

ずひるどくん　元気ですか　また遊ぼうね

こ

こまでよんでくれた人々　ありがとう

う

自信作です

ei1333.github.io

ei1333の日記

ぺこい