グラフペブリング
グラフ上で行われる数学ゲーム

グラフペブリングは、各頂点に0個以上の小石が置かれたグラフ上で行われる数学ゲームです。「ゲームプレイ」は、一連のペブリング動作で構成されます。グラフ上のペブリング動作は、少なくとも2つの小石が置かれた頂点を選択し、そこから2つの小石を取り除き、隣接する頂点に1つ小石を追加する動作で構成されます（2番目に取り除かれた小石はゲームから除外されます）。グラフGのペブリング数であるπ( G )は、以下の条件を満たす最小の自然数nです。

グラフ内の任意のターゲット頂点または「ルート」頂点と、グラフ上のn個の小石の任意の初期構成が与えられると、おそらく空の一連の小石移動の後に、指定されたルート頂点に 1 つ以上の小石がある新しい構成に到達する可能性があります。

例えば、2つの頂点とそれらを結ぶ1つの辺を持つグラフでは、ペブリング数は2です。2つのペブルをグラフの頂点にどのように配置しても、選択した頂点にペブルを配置するという望ましい結果に常に到達できます。初期配置が各頂点にペブルが1つずつ配置されている場合、ペブリング移動を0回行うだけで目的が達成されます。グラフペブリングにおける中心的な問題の一つは、与えられたグラフGにおける π( G ) の値です。

目標頂点を赤で示した2つのグラフ。

左：3つの小石を使ったゲームで、2手で勝てる。

右：左よりも小石の数が多いにもかかわらず、1つの小石しかない頂点では手が進まないため勝てないゲーム。つまり、このグラフの小石数π( G )は少なくとも6でなければならない。

ペブリングに関するその他のトピックには、カバー ペブリング、最適ペブリング、支配カバー ペブリング、ペブリング数の境界としきい値、およびディープ グラフが含まれます。

ペブリングゲームの応用例の一つは、暗号におけるメモリ困難な関数のセキュリティ分析である。[1]

π(G） — グラフのペブリング数

ペブリングゲームは、ラガリアスとサックスによって、数論における特定の問題を解くためのツールとして初めて提案されました。1989年にFRK Chungがこの概念を文献[2]で紹介し、ペブリング数π( G )を定義しました。

n頂点の完全グラフのペブリング数はnであることが簡単に証明できます。グラフにn  − 1 個のペブルを置くことができたとすると、対象頂点を除く各頂点に 1 個ずつペブルを置くことができます。2 個以上のペブルを持つ頂点は存在しないため、移動は不可能であり、対象にペブルを置くことはできません。したがって、ペブリング数はn  − 1 より大きくなければなりません。n 個のペブルがある場合、2 つのケースが考えられます。各頂点に 1 個のペブルがある場合、移動は不要です。いずれかの頂点が裸である場合、少なくとも他の 1 つの頂点に 2 個のペブルが配置されている必要があり、1 回のペブリング移動で完全グラフの任意の対象頂点にペブルを追加できます。[2]

π(Gグラフ族の）

ペブリング数は、次のグラフ族で知られています。

  • π （ K n ） ＝ n {\displaystyle \pi (K_{n})=n} はn頂点の完全グラフである。[ 2] K n {\displaystyle K_{n}}
  • π （ P n ） ＝ 2 n − 1 {\displaystyle \pi (P_{n})=2^{n-1}} 、ここではn頂点のパスグラフである。[2] P n {\displaystyle P_{n}}
  • π （ W n ） ＝ n {\displaystyle \pi (W_{n})=n} 、これはn頂点のホイール グラフです。 W n {\displaystyle W_{n}}

グラハムのペブリング予想

数学における未解決問題
グラフの直積のペブリング数は、最大でもグラフのペブリング数の積ですか?
数学におけるさらなる未解決問題

チャン（1989）は、グラフの直積のペブリング数は、最大で因子のペブリング数の積に等しいというロナルド・グラハムの予想を提唱した。 [3]これはグラハムのペブリング予想として知られるようになった。特殊なケースが知られているものの、未だに解決されていない。[4]

γ(G）—グラフの被覆ペブリング数

クルルらは被覆ペブリングの概念を導入した。グラフGの被覆ペブリング数γ( G ) は、任意の初期ペブリング配置から一連のペブリング移動を経てグラフが被覆されるために必要な最小のペブリング数である。つまり、すべての頂点に少なくとも1つのペブリングが存在する。 [5]スタッキング定理と呼ばれる結果は、任意のグラフの被覆ペブリング数を求める。[6] [7]

積み重ね定理

積み重ね定理によれば、最も多くの小石を被覆解として必要とする小石の初期配置は、すべての小石が単一の頂点に置かれたときである。この観察に基づいて、次のように定義する。

s （ v ） ＝ ∑ あなた ∈ V （ G ） 2 d （ あなた 、 v ） {\displaystyle s(v)=\sum _{u\in V(G)}2^{d(u,v)}}

Gの任意の頂点vについて、d ( u , v )はuからvまでの距離を表す。この場合、被覆ペブル数は結果として得られる最大のs ( v ) となる。

γ(Gグラフ族の）

被覆ペブリング数は、次のグラフのファミリーで知られています。

  • γ （ K n ） ＝ 2 n − 1 {\displaystyle \gamma (K_{n})=2n-1} 、ここではn頂点の完全グラフです。 K n {\displaystyle K_{n}}
  • γ （ P n ） ＝ 2 n − 1 {\displaystyle \gamma (P_{n})=2^{n}-1} 、ここではn頂点のパス グラフです。 P n {\displaystyle P_{n}}
  • γ （ W n ） ＝ 4 n − 9 {\displaystyle \gamma (W_{n})=4n-9} はn頂点のホイールグラフである。[8] W n {\displaystyle W_{n}}

参照

参考文献

  1. ^ Alwen, Joël; Serbinenko, Vladimir (2014), High Parallel Complexity Graphs and Memory-Hard Functions、2024年4月16日時点のオリジナルよりアーカイブ、2024年1月15日閲覧
  2. ^ abcd Chung, Fan RK (1989). 「超立方体におけるペブリング」. SIAM Journal on Discrete Mathematics . 2 (4): 467– 472. doi :10.1137/0402041. MR  1018531.
  3. ^ Chung（1989）の質問3、472ページを参照。
  4. ^ Pleanmani, Nopparat (2019). 「グラハムのペブリング予想は、グラフと十分に大きな完全二部グラフの積に対して成立する」.離散数学、アルゴリズム、応用. 11 (6): 1950068, 7. doi :10.1142/s179383091950068x. MR  4044549. S2CID  204207428.
  5. ^ Crull, Betsy; Cundiff, Tammy; Feltman, Paul; Hurlbert, Glenn H.; Pudwell, Lara; Szaniszlo, Zsuzsanna; Tuza, Zsolt (2005)、「グラフの被覆ペブリング数」(PDF)、離散数学、296 (1): 15– 23、arXiv : math/0406206、doi :10.1016/j.disc.2005.03.009、MR  2148478、S2CID 5109099、 2012年7月17日にオリジナルから アーカイブ(PDF) 、 2019年7月22日取得
  6. ^ Vuong, Annalies; Wyckoff, M. Ian (2004年10月18日). 「グラフの重み付き被覆ペブリングの条件」. arXiv : math/0410410 .
  7. ^ Sjöstrand, Jonas (2005). 「The cover pebbling theorem」. Electronic Journal of Combinatorics . 12 N22: Note 22. doi : 10.37236/1989 . MR  2180807. 2012年2月14日時点のオリジナルよりアーカイブ。 2019年7月22日閲覧。
  8. ^ Watson, Nathaniel G.; Yerger, Carl R. (2006). 「特定のグラフ族の被覆ペブリング数と境界値」. Bulletin of the Institute of Combinatorics and Its Applications . 48 : 53–62 . arXiv : math/0409321 . MR  2259702.

さらに読む

  • Chan, Melody ; Godbole, Anant P. (2008). 「改良されたペブリング境界」.離散数学. 308 (11): 2301– 2306. arXiv : math/0510045 . doi :10.1016/j.disc.2006.06.032. MR  2404560. S2CID  5501949.
  • Hurlbert, Glenn H. (1999). 「グラフペブリングの概観」(PDF) .第30回南東部国際組合せ論、グラフ理論、コンピューティング会議 (フロリダ州ボカラトン、1999年) の議事録. Congressus Numerantium. 第139巻. pp.  41– 64. MR  1744229. 2006年9月2日時点のオリジナルよりアーカイブ(PDF) . 2005年10月31日閲覧.
  • Pachter, Lior ; Snevily, Hunter S. ; Voxman, Bill (1995). 「ペブリンググラフについて」(PDF) .第26回南東部国際組合せ論、グラフ理論、コンピューティング会議 (フロリダ州ボカラトン、1995年) の議事録. Congressus Numerantium. 第107巻. pp.  65– 80. MR 1369255. 2015年11月25日時点のオリジナル(PDF) からのアーカイブ。
「https://en.wikipedia.org/w/index.php?title=Graph_pebbling&oldid=1329363560」より取得