完全なグラフの順序付き集合の頂点を見つける

Question

問題：完全なグラフKnの順序付けられた集合Eに対して、エッジEiが与えられた場合、エッジの頂点（v、w）_Eiを見つける。

注：このことは、グラフ理論に固有の問題ではない可能性がありますが、これは、熟知しているためだけに問題を表現することにしました。間違った記法の謝罪が導入されました。

頂点1,2,3,4,5からなる完全なグラフK5から構築されたと仮定すると、グラフのエッジの順序付けられた集合Eがあり、合計10の辺があります。以下のように設定されたEは必ず注文することが知られている：

Eiを=（0 < V < N、W、V < = < n）は任意のEiのために

E1 = (1, 2) 
E2 = (1, 3) 
E3 = (1, 4) 
E4 = (1, 5) 
E5 = (2, 3) 
E6 = (2, 4) 
E7 = (2, 5) 
E8 = (3, 4) 
E9 = (3, 5) 
E10 = (4, 5) 

、我々は今、頂点を見つける必要があります（v、w）_Eiをiだけ使っています。例えば、6を与えると、（2,4）が得られるはずです。

更新： もう一つ、おそらくこの問題を表現する簡単な方法は次のとおりです。

n = 5 
i = 0 

for v = 1 to n - 1 
    for w = v + 1 to n 
     i++ 
     print "E" + i + " = " + v + ", " w 


print "E6 = " + findV(6) + ", " + findW(6) 

、これはどのように行われていますか？

Answer 1

閉じた形で問題を解決するために、我々は最初のk数の和の公式を必要とする：1 + 2 + ... + k = (k + 1) * k/2。これは私たちにエッジ(i, j)からエッジのインデックスへのマッピングを提供します：

def index_to_edge(k, n): 
    b = 1.0 - 2 * n 
    i = int(ceil((-b - sqrt(b**2 - 8 * k))/2)) 
    j = k - n * (i - 1) + i * (i + 1)/2 
    return (i, j) 

テスト：

n = 5 

print "Edge to index and index to edge:" 
for i in range(1, n + 1): 
    for j in range(i + 1, n + 1): 
     k = edge_to_index((i, j)) 
     print (i, j), "->", k, "->", index_to_edge(k, n) 

出力：

from math import ceil, sqrt 

def edge_to_index((i, j)): 
    return n * (i - 1) + j - i * (i + 1)/2 

私たちは、逆マッピングを導き出すことができ

Edge to index and index to edge: 
(1, 2) -> 1 -> (1, 2) 
(1, 3) -> 2 -> (1, 3) 
(1, 4) -> 3 -> (1, 4) 
(1, 5) -> 4 -> (1, 5) 
(2, 3) -> 5 -> (2, 3) 
(2, 4) -> 6 -> (2, 4) 
(2, 5) -> 7 -> (2, 5) 
(3, 4) -> 8 -> (3, 4) 
(3, 5) -> 9 -> (3, 5) 
(4, 5) -> 10 -> (4, 5) 

Answer 2

（pythonで）次のようにまあ、簡単な方法は、をループしていると最初の頂点に対応する値を減算：

def unpackindex(i,n): 
    for v in range(1,n): 
    if v+i<=n: return (v,v+i) 
    i-= n-v 
    raise IndexError("bad index") 

あなたは閉形式を探しているなら、ではなくアルゴリズムでは、ある点で平方根を実行する必要があるので、乱雑でやや遅くなる可能性があります（しかし、上記のループほど遅くなく、十分な大きさのn ...）。適度な値のnについては、パフォーマンスが重要な場合は、事前計算ルックアップテーブルを考慮する必要があります。

Answer 3

が、これは完全にオフトピックである場合、あなたは私に知らせてできるように、私はあなたが求めていると思う質問を言い換えるてみましょう：

整数kとシリーズを考えると（1、2）、 （2,3）、...、（1、k）、（2,3）、（2,4）、...、（2、k）、（3,4）、...、 - 1、k）とインデックスnは、この系列のn番目の項の値を返します。

ここでは、おそらく漸近的に最適ではないこの問題を解決する簡単なアルゴリズムがあります。ペアの最初（k - 1）は1で始まり、次の（k - 2）は2で始まり、次の（k - 3）で3などで始まることに注意してください。 （k-1）+（k-2）+ ...をあなたのインデックスに等しいかそれ以上の値になるまで続けることができます。あなたがこれを行うことができた回数に1を加え、あなたの最初の数字を与える：

ここ

E1 = (1, 2) 
E2 = (1, 3) 
E3 = (1, 4) 
E4 = (1, 5) 
E5 = (2, 3) 
E6 = (2, 4) 
E7 = (2, 5) 
E8 = (3, 4) 
E9 = (3, 5) 
E10 = (4, 5) 

、用語8の最初の番号を確認するには= 5 kは、我々は最初のkを追加 - = 4 1を、どの8未満です。次に、k-2 = 3を加えて7を得る。これはまだ8未満である。しかし、k-3 = 2を追加すると、8を超える9が得られますので、停止します。 2つの数字を一緒に追加したので、最初の数字は3でなければなりません。

最初の数字がわかれば、簡単に2番目の数字を得ることができます。最初の数字を得るためのステップを実行するとき、最初の数字が変わるペアのインデックスをリストします。たとえば、上のケースでは、系列0,4,7がありました。これらのそれぞれに1を加えると1,5,8が得られます。実際には数字1,2,3で始まる最初のペアです。最初の数字が何であるかを知ったら、その番号のペアがどこから始まるかも知っているので、そのポジションから自分の番号のインデックスを差し引くことができます。これは、ゼロインデックスを使用して、その要素からどのように多くのステップを進めたかを示します。さらに、その最初の要素の2番目の値は何かを知っているので、最初の要素に1を加えた値なので、2番目の値は最初の数値と1に加えてインデックスが超えているステップ数最初のペアは指定された番号で始まります。私たちの場合、インデックス8を見ているので、3で始まる最初のペアが8の位置にあることを知っているので、2番目の番号は3 + 1 + 0 = 4で、ペアは（3,4） 。

このアルゴリズムは実際にはかなり高速です。任意のkが与えられた場合、このアルゴリズムは完了までに最大kステップを要するので、O（k）で実行される。これをO（k ）が必要なすべてのスキャンの素朴なアプローチと比較してください。

Answer 4

私の人生を楽にするために、私はあなたの質問と同じように、0ベースで、1ベースではなく、私の計算をします。

まず、用語(v,v+1)（最初はvで始まる）のインデックスの式を導き出します。これはちょうどn-1 + n-2 + ... + n-vの算術合計で、v(2n-v-1)/2です。

インデックスiを指定してvを見つけるには、最大の積分vの式v(2n-v-1)/2 <= iを解いてください。バイナリ検索がうまくいくか、二次方程式を使って二次方程式を解き、丸めることができます（おそらく、それが終わるかどうか考える必要があります）。 Wを見つける

が簡単に与えられたVです：

findW(i): 
    v = findV(i) 
    i_v = v(2n-v-1)/2 
    return i - i_v + 1