0

問題: 完全なグラフ Kn のエッジ E の順序付けられたセットについて、エッジ Ei が与えられた場合、エッジの頂点 (v, w)_Ei を見つけます。

注: これはグラフ理論に固有の問題ではありませんが、親しみやすさだけを理由に問題を表現するために選択されました。誤った表記が導入されたことをお詫びします。

頂点 1、2、3、4、5 から構成される完全なグラフ K5 から構築されたものと仮定すると、グラフのエッジの順序付けられたセット E があり、合計 10 個のエッジがあります。集合 E は常に次のように順序付けられることが知られています。

Ei = (0 < v < n, v < w =< n)

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)

任意の Ei について、i のみを使用して頂点 (v, w)_Ei を見つける必要があります。たとえば、6 が与えられた場合、(2, 4) を取得する必要があります。

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

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)

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

4

4 に答える 4

3

この問題を閉形式で解くには、最初のk数の合計の式が必要です1 + 2 + ... + k = (k + 1) * k / 2。(i, j)これにより、エッジからエッジ インデックスへのマッピングが得られます。

from math import ceil, sqrt

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

逆マッピングを導出できます。

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)

出力：

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)
于 2011-01-19T22:20:44.280 に答える
1

これが完全にトピックから外れている場合は、私に知らせてください。

整数 k と系列 (1, 2), (1, 3), ..., (1, k), (2, 3), (2, 4), ..., (2, k) , (3, 4), ..., (k - 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)

ここで、k = 5 です。項 8 の最初の数を見つけるには、最初に k - 1 = 4 を追加します。これは 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 2 )かかるすべてをスキャンする単純なアプローチと比較してください。

于 2011-01-19T21:55:24.213 に答える
1

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

まず、用語のインデックスの公式を導出します(v,v+1)(最初に で始まる用語v)。これは の算術和でありn-1 + n-2 + ... + n-v、これはv(2n-v-1)/2です。

vしたがって、与えられたインデックスを見つけるには、最大の積分iの方程式を解くだけです。二分探索はうまくいくか、二次式を使用して二次を解いて切り捨てることができます (おそらく、それがうまくいくかどうかを考える必要があります)。v(2n-v-1)/2 <= iv

V が与えられれば、W を見つけるのは簡単です。

findW(i):
  v = findV(i)
  i_v = v(2n-v-1)/2
  return i - i_v + 1
于 2011-01-19T22:09:23.660 に答える
0

簡単な方法は、次のように、最初の頂点に対応する値をループして減算することです（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の値が中程度の場合、パフォーマンスが重要な場合は、事前に計算されたルックアップテーブルを検討することをお勧めします。

于 2011-01-19T21:49:02.940 に答える