1

だから、私はグラフを楽しみたいと思っていましたが、今では夢中になっています。

まず、指定された数のエッジを持つ連結グラフを生成します。これは私の呪いになった簡単な部分です。基本的には意図したとおりに動作しますが、得られた結果はかなり奇妙です (まあ、そうではないかもしれませんが、ここでの問題です)。グラフを生成するアルゴリズムは非常に単純です。

02 つの配列があり、そのうちの 1 つは からまでの数値で満たされ、もう 1 つn - 1は空です。

最初に、最初の要素をシャッフルして、最後の要素を空の要素に移動します。

次に、ループで、最初の配列の最後の要素と2番目の配列のランダムな要素の間にエッジを作成し、その後、最後の要素を最初の配列から別の配列に移動します。

その部分が完了したら、必要な数が得られるまで、頂点間にランダムなエッジを作成する必要があります。これも非常に簡単です。0からまでの範囲の 2 つの数値をランダムに選択しn - 1、これらの頂点間にエッジがない場合は、1 つ作成します。

これはコードです：

void generate(int n, double d) {
    initMatrix(n); // <- creates an adjacency matrix n x n, filled with 0s
    int *array1 = malloc(n * sizeof(int));
    int *array2 = malloc(n * sizeof(int));
    int j = n - 1, k = 0;
    for (int i = 0; i < n; ++i) {
        array1[i] = i;
        array2[i] = 0;
    }

    shuffle(array1, 0, n); // <- Fisher-Yates shuffle
    array2[k++] = array1[j--];
    int edges = d * n * (n - 1) * .5;
    if (edges % 2) {
        ++edges;
    }
    while (j >= 0) {
        int r = rand() % k;
        createEdge(array1[j], array2[r]);
        array2[k++] = array1[j--];
        --edges;
    }

    free(array1);
    free(array2);

    while (edges) {
        int a = rand() % n;
        int b = rand() % n;
        if (a == b || checkEdge(a, b)) {
            continue;
        }
        createEdge(a, b);
        --edges;
    }
}

さて、これを印刷すると立派なグラフです。次に、ハミルトニアン サイクルを見つけたいと思います。この部分は機能します。次に、私の悩みの種であるオイラーサイクルに行き着きます。どうしたの？

まず、すべての頂点が偶数かどうかを確認します。そして、そうではありません。いつも。完全なグラフを生成することを選択しない限り、毎回。

私は今、自分のコードによって破壊されていると感じています。何か間違えている？それともこうあるべきなのか？オイラー回路がまれであることはわかっていましたが、それほどまれではありませんでした。助けてください。

4

1 に答える 1

3

オイラー サイクルを持つ確率を分析してみましょう。簡単にするためにn、エッジの数に関係なく、頂点を持つすべてのグラフについて分析してみましょう。

サイズ のグラフ G が与えられたとき、n任意の頂点を 1 つ選びます。次数が偶数である確率はおおまかにです(各,1/2を仮定)。u1,u2P((v,u1) exists) = P((v,u2) exists)

次に、 からを削除vし、頂点を持ち、すべての辺が に接続されていないG新しいグラフG'を作成します。n-1v

v'同様に、G'-の任意の頂点(v,v')が のエッジである場合、奇数G'である必要があります。d(v')それ以外の場合は、偶数である必要d(v')があります (両方ともG')。いずれにせよ、それの確率はまだおおよそ~1/2です。(以前の度とは無関係v)。

....

に接続されている現在のグラフに到達するまでに破棄されたエッジの数を としiます。が奇数の場合、現在の次数が奇数である確率は であり、 が偶数の場合、現在の次数が偶数である確率も であり、現在の確率は#(v)v#(v)~1/2#(v)~1/2~1/2

これで、それがどのように機能するかを理解し、グラフがオイラー巡回である確率の漸化式を作成できます。

P(n) ~= 1/2*P(n-1)
P(1) = 1

これで が得られますがP(n) ~= 2^-n、これは合理的ではありませんn。

1/2 は大まかな見積もりに過ぎないことに注意してください (そして の場合は正しいですn->infinity)。確率は実際には少し高くなりますが、それでも指数関数的で-nあり、妥当なサイズのグラフではほとんどありません。

于 2015-05-21T08:58:31.490 に答える