グラフが連結である確率（8）

m点でn辺のグラフが連結である確率を疑似乱数を使って計算している。
今回は、PythonからC++に移植して少し工夫した。すると、速度が100倍になった。そこで、繰り返し回数を10万回にして、m=3200を追加した。疑似乱数が少し気になるが、この問題ではあまり気を使わなくていいだろう。

そして、連結である確率が0.5,0.9,0.99,0.999を通過するn/mをプロットした。

かなりよく並ぶ。それぞれの近似式は、

p = 0.5   n = m(0.52522log(m) + 0.000266)

p = 0.9   n = m(0.56929log(m) + 0.627942)

p = 0.99  n = m(0.63550log(m) + 1.338728)

p = 0.999 n = m(0.71830log(m) + 1.922781)

p = 0.9, 0.99, 0.999を取って、それぞれ1,2,3として、近似式の傾きと切片をプロットすると、

この式を使って、p = 1 - 1e-6のときのnの近似式を推定すると、

n = m(0.938log(m) + 3.886)

m = 10000なら、125345辺あればまず間違いなく連結である、らしい。

#include 

#include 

#include 
using namespace std;
class cGraph {

    int         n;

    vector >    g;

    vector a;

    

public:

    cGraph(int n) {

        this->n = n;

        g = vector >(n);

        a = vector(n, 0);

        a[0] = 1;

    }

    

    void clear();

    void add_edge_at_random();

    bool add_edge(int vs, int ve);

    bool exists_edge(int vs, int ve) const;

    void update_connection(int vs, int ve);

    bool is_connective() const;

};
void cGraph::clear() {

    for(int i = 0; i < n; i++) {

        g[i].resize(0);

        a[i] = 0;

    }

    a[0] = 1;

}
void cGraph::add_edge_at_random() {

    while(true) {

        int     vs = rand() % n;

        int     ve;

        while(true) {

            ve = rand() % n;

            if(vs != ve)

                break;

        }

        if(add_edge(vs, ve))

            break;

    }

}
bool cGraph::add_edge(int vs, int ve) {

    if(exists_edge(vs, ve)) {

        return false;

    }

    else {

        g[vs].push_back(ve);

        g[ve].push_back(vs);

        update_connection(vs, ve);

        return true;

    }

}
bool cGraph::exists_edge(int vs, int ve) const {

    return find(g[vs].begin(), g[vs].end(), ve) != g[vs].end();

}
void cGraph::update_connection(int vs, int ve) {

    if(a[vs] + a[ve] == 1) {

        if(a[vs] == 0) {

            int tmp = vs;

            vs = ve;

            ve = tmp;

        }

        a[ve] = 1;

        stack  stk;

        stk.push(ve);

        while(!stk.empty()) {

            int v0 = stk.top();

            stk.pop();

            typedef vector::const_iterator CIT;

            for(CIT p = g[v0].begin(); p != g[v0].end(); ++p) {

                int v1 = *p;

                if(a[v1] == 0) {

                    a[v1] = 1;

                    stk.push(v1);

                }

            }

        }

    }

}
bool cGraph::is_connective() const {

    return find(a.begin(), a.end(), 0) == a.end();

}
int main() {

    for(int m = 25; m <= 3200; m *= 2) {

        srand(m);

        printf("m : %d\n", m);

        

        cGraph  g(m);

        for(int k = 0; k < 100000; k++) {

            g.clear();

            int n = 0;

            while(true) {

                g.add_edge_at_random();

                n++;

                if(g.is_connective()) {

                    printf("%d\n", n);

                    break;

                }

            }

        }

    }

}