頂点数と次数を指定して正則グラフを生成する

アルゴリズム

概要

AtCoder Heuristic Contest 016 に参加したときに、頂点数 n と次数 d とを任意に指定して正則グラフを生成するアルゴリズムを調べて実装しました。せっかくなので、それについて書きます。生成されるグラフのランダム性などは考えず、とりあえず所望の正則グラフがひとつ得られたら満足するものとします。この記事は文献 https://ipsj.ixsq.nii.ac.jp/ej/action=repository_uri&item_id=32553&file_id=1&file_no=1 で紹介されているアルゴリズムの、目的に必要な部分だけを紹介するものですが、正当性の証明なども補足したいと思います。正則グラフの生成アルゴリズムの研究に関してしっかり調べたわけではないので、もっとよいアルゴリズムがあるかもしれません。

アルゴリズム

n 頂点の d -正則グラフを生成するアルゴリズムです。ただし、 d\lt n かつ nd は偶数とします
（各辺は２回ずつ次数の総和 nd に寄与するので、偶数でなければならないことがわかります）。逆に、この条件を満たせば正則グラフが構成できることが以下のアルゴリズムにより保証されます。

手順1

完全グラフ K_{d+1} を、頂点数が超過しない限り並べる。最大で \lfloor{\frac{n}{d+1}}\rfloor 個並べることができる。こうしてできるグラフは、 d -正則グラフである。

手順2

d -正則グラフであることを保ったまま頂点を増やしていき、目的の頂点数 n の d -正則グラフを得る。 d の偶奇によって操作が異なる。

手順2-a （ d が偶数のとき）

頂点を 1 つずつ増やしていく。
d/2 本の互いに隣接しない辺を選ぶ。辺の端点すべてに対して、新たに加える頂点 v との間に辺を張る。そして、選んだ辺をすべて取り除く。

手順2-b （ d が奇数のとき）

頂点を 2 つずつ増やしていく（頂点数が偶数でなければならないので、 1 つだけ増やすことは不可能）。
長さ d の単純パス (x_0,x_1,\dots,x_d) をとる。新たに加える頂点を v_1,v_2 として、 v_1 は x_0,\dots,x_{d-1} に、 v_2 は x_1,\dots,x_d に接続する。そして、パス上の辺をすべて取り除く。


手順2に関しては、文献にわかりやすい図が載っているので参照してください。

アルゴリズムの正当性

d/2 本の互いに隣接しない辺を選ぶには（ d は偶数）

まだ辺の端点として選ばれていない頂点の集合が誘導する部分グラフから、任意に1つの辺を選ぶことを繰り返せばよいです。これが必ず可能なことを示します。
（証明）まだ辺の端点として選ばれていない頂点の集合を S とする。 v\in S を任意にとる。このとき、ある u\in S が存在して 辺 (v,u) が存在することを示す。このような u が存在しない状況を考える。 v が隣接する頂点がすべて既に辺の端点として選ばれていることになるが、 v の次数は d なので、既に d/2 本の互いに隣接しない辺が選ばれていることになる。 □

長さ d の単純パスをとるには（ d は奇数）

はじめに任意に頂点を選び、1頂点からなるパスとします。そのあと、現時点でのパスの終点と、パスに含まれない頂点との間に辺を張ることを繰り返せばよいです。これが必ず可能なことを示します。
（証明）各時点において、パスに含まれない頂点であって、パスの終点との間に辺が張られたものが存在することを示す。このような頂点が存在しない状況を考える。パスの終点を v とする。 v に隣接する頂点がすべてパスに含まれることになるが、 v の次数は d なので、既に d+1 頂点からなる単純パスが得られていることになる。 □

実装例

1000頂点くらいまでなら高速に動作します。

#include <vector>

// n頂点のd-正則グラフを生成し、その隣接行列を返す
// ただし、d*nは偶数でd<nとする
std::vector<std::vector<bool>> generate_regular_graph(int n, int d) {
    std::vector<std::vector<bool>> graph(n, std::vector<bool>(n, false));

    // d+1頂点の完全グラフを可能な限り作る
    const int num{n / (d + 1)};
    for (int i = 0; i < num; ++i) {
        const int begin{i * (d + 1)};
        const int end{(i + 1) * (d + 1)};
        for (int a = begin; a < end; ++a) {
            for (int b = a + 1; b < end; ++b) {
                graph[a][b] = graph[b][a] = true;
            }
        }
    }

    // d-正則グラフのまま頂点数を増やしていく
    int now_n{num * (d + 1)};
    if (d % 2 == 0) {  // dが偶数のときは1頂点ずつ増やす
        std::vector<int> from(d / 2), to(d / 2);
        std::vector<bool> used(n, false);
        while (now_n < n) {
            std::fill(std::begin(used), std::end(used), false);

            // d/2本の互いに隣接しない辺を選ぶ
            int a{0};
            for (int i = 0; i < d / 2; ++i) {
                while (used[a]) ++a;
                for (int b = a + 1; b < now_n; ++b) {
                    if (used[b]) continue;
                    if (graph[a][b]) {
                        from[i] = a, to[i] = b;
                        used[a] = used[b] = true;
                        break;
                    }
                }
            }

            // 頂点を増やしてグラフを組み替える
            for (int i = 0; i < d / 2; ++i) {
                const int a{from[i]}, b{to[i]};
                graph[a][b] = graph[b][a] = false;
                graph[a][now_n] = graph[now_n][a] = true;
                graph[b][now_n] = graph[now_n][b] = true;
            }
            ++now_n;
        }
    } else {  // dが奇数のときは2頂点ずつ増やす
        std::vector<int> path;
        std::vector<bool> used(n, false);
        while (now_n + 1 < n) {
            std::fill(std::begin(used), std::end(used), false);
            path = {0};  // 頂点0から始める
            used[0] = true;

            // 長さdの単純パスを選ぶ
            for (int i = 0; i < d; ++i) {
                const int from{path.back()};
                for (int to = 0; to < now_n; ++to) {
                    if (used[to] || !graph[from][to]) continue;
                    path.emplace_back(to);
                    used[to] = true;
                    break;
                }
            }

            // 頂点を増やしてグラフを組み替える
            for (int i = 0; i < d; ++i) {
                const int a{path[i]}, b{path[i + 1]};
                graph[a][b] = graph[b][a] = false;
            }
            for (int i = 0; i < d; ++i) {
                graph[path[i]][now_n] = graph[now_n][path[i]] = true;
            }
            for (int i = 1; i < d + 1; ++i) {
                graph[path[i]][now_n + 1] = graph[now_n + 1][path[i]] = true;
            }
            now_n += 2;
        }
    }

    return graph;
}

感想

思ってたよりも簡単なアルゴリズムで正則グラフが生成できて驚き。