擬似森林

グラフ理論において、擬似森とは、連結されたすべての構成要素が最大で1つのサイクルを持つ無向グラフ^[1]である。つまり、それは頂点と頂点のペアを連結する辺のシステムであり、連続する辺の2つのサイクルは互いに頂点を共有せず、また、連続する辺のパスによって2つのサイクルが互いに連結されることもない。擬似木は連結された擬似森である。

これらの名前は、より一般的に研究されているツリーやフォレストとの類推によって正当化されています。(ツリーは閉路のない連結グラフであり、フォレストはツリーの非結合和です。) Gabow と Tarjan ^[2]は、擬似フォレストの研究は Dantzig の 1963 年の線形計画法に関する本に起因するとしており、その中で擬似フォレストは特定のネットワーク フロー問題の解決に使用されています。 ^[3]擬似フォレストは関数のグラフ理論モデルも形成し、いくつかのアルゴリズムの問​​題に使用されます。擬似フォレストは疎グラフであり、辺の数は頂点の数に対して線形に制限されます (実際、辺の数は頂点の数と同じになります)。また、マトロイド構造により、他のいくつかの疎グラフ ファミリをフォレストと擬似フォレストの和として分解できます。「擬似フォレスト」という名前は、Picard & Queyranne (1982) に由来しています。

無向グラフとは、各辺が 2 つの頂点 (一致する場合もある) を端点として持つ頂点と辺の集合であると定義します。つまり、複数の辺 (同じ端点のペアを持つ辺) とループ (2 つの端点が同じ頂点である辺) を許容します。 ^[1]グラフの サブグラフとは、そのグラフの頂点と辺の任意のサブセットによって形成されるグラフで、辺サブセット内の各辺は頂点サブセット内に両方の端点を持ちます。無向グラフの連結成分とは、1 つの開始頂点から次の辺で到達できる頂点と辺で構成されるサブグラフです。すべての頂点または辺が他のすべての頂点または辺から到達可能である場合、グラフは連結されています。無向グラフのサイクルとは、各頂点がちょうど 2 つの辺に接続されている、またはループである連結サブグラフです。^[4]

擬似フォレストは、各接続コンポーネントが最大で 1 つのサイクルを含む無向グラフです。^[5] 同様に、各接続コンポーネントの辺の数が頂点の数より少ない無向グラフです。^[6] サイクルを持たないコンポーネントは単なるツリーであり、サイクルを 1 つだけ持つコンポーネントは1-ツリーまたは単環グラフと呼ばれます。つまり、1-ツリーは、正確に 1 つのサイクルを含む接続グラフです。接続コンポーネントが 1 つの擬似フォレスト (通常は擬似ツリーと呼ばれますが、擬似ツリーを 1-ツリーと定義する著者もいます) は、ツリーまたは 1-ツリーのいずれかです。一般に、擬似フォレストは、接続コンポーネントがすべてツリーまたは 1-ツリーである限り、複数の接続コンポーネントを持つことができます。

1-ツリーからサイクル内の辺の 1 つを削除すると、ツリーが作成されます。このプロセスを逆にして、ツリーの任意の 2 つの頂点を新しい辺で接続してツリーを拡張すると、結果は 1-ツリーになります。追加された辺の 2 つのエンドポイントを接続するツリー内のパスと、追加された辺自体が、1-ツリーの一意のサイクルを形成します。1-ツリーの頂点の 1 つを新しく追加された頂点に接続する辺を追加して 1-ツリーを拡張すると、結果は再び 1-ツリーになり、頂点が 1 つ増えます。1-ツリーを構築する別の方法は、1 つのサイクルから始めて、この拡張操作を任意の回数繰り返すことです。任意の 1-ツリーの辺は、2 つのサブグラフに一意に分割できます。1 つはサイクルで、もう 1 つはフォレストです。フォレストの各ツリーには、サイクルの頂点が 1 つだけ含まれます。^[7]

特定のより特殊なタイプの疑似森林も研究されてきました。

1-フォレスト(最大擬似フォレストとも呼ばれる) は、グラフの一部のコンポーネントに複数のサイクルが含まれることなしにエッジを追加できない擬似フォレストです。擬似フォレストのコンポーネントの 1 つにツリーが含まれている場合、そのツリー内の 2 つの頂点を接続するエッジを追加して単一のサイクルを形成するか、そのツリーを他のコンポーネントに接続するエッジを追加できるため、1-フォレストにはなりません。したがって、1-フォレストは、すべてのコンポーネントが 1-ツリーである擬似フォレストです。

無向グラフGの全域疑似森林は、 Gのすべての頂点を持つGの疑似森林サブグラフです。このような疑似森林には、エッジは必要ありません。たとえば、 Gのすべての頂点を持ち、エッジを持たないサブグラフは疑似森林 (そのコンポーネントは単一の頂点からなる木です) です。

Gの最大擬似フォレストは、 Gのどのより大きな擬似フォレストにも含まれないGの擬似フォレスト サブグラフです。 Gの最大擬似フォレストは常に全域擬似フォレストですが、その逆は成り立ちません。Gにツリーである接続コンポーネントがない場合、その最大擬似フォレストは 1-フォレストですが、Gにツリー コンポーネントがある場合、その最大擬似フォレストは 1-フォレストではありません。正確に言えば、任意のグラフGにおいて、その最大擬似フォレストは、Gのすべてのツリー コンポーネントと、 Gの残りの頂点をカバーする 1 つ以上の互いに素な 1-ツリーで構成されます。

これらの定義のバージョンは、有向グラフにも使用されます。無向グラフと同様に、有向グラフは頂点と辺で構成されますが、各辺は一方の端点からもう一方の端点に向かって有向になっています。有向擬似フォレストは、各頂点が最大で 1 つの出力辺を持つ有向グラフです。つまり、出力次数は最大で 1 です。有向 1 フォレスト(最も一般的には関数グラフ(下記参照)と呼ばれ、最大有向擬似フォレストと呼ばれることもあります) は、各頂点の出力次数がちょうど 1 である有向グラフです。^[8] Dが有向擬似フォレストの場合、 Dの各辺から方向を削除して形成される無向グラフは、無向擬似フォレストです。

n頂点の集合上のすべての擬似森は最大でn辺を持ち、 n頂点の集合上のすべての極大擬似森はちょうどn辺を持つ。逆に、グラフG が、その頂点のすべての部分集合Sについて、 Sの誘導部分グラフの辺の数が最大でSの頂点数になるという性質を持つ場合、G は擬似森である。1 木は、頂点と辺の数が等しい連結グラフとして定義できる。^[2]

個々のグラフからグラフ族に移ると、グラフ族が、族内のグラフのすべてのサブグラフも族内にあり、族内の各グラフの辺の数が頂点の数以下であるという特性を持つ場合、族には擬似森林のみが含まれます。たとえば、トラクル(すべての辺のペアが 1 つの交差点を持つように描かれたグラフ) のすべてのサブグラフはトラクルでもあるため、すべてのトラクルの辺の数が頂点の数以下であるというコンウェイの予想は、すべてのトラクルが擬似森林であると言い換えることができます。より正確な特徴付けは、予想が正しい場合、トラクルは 4 頂点サイクルがなく、奇数サイクルが最大 1 つである擬似森林とまったく同じであるということです。^[9]

Streinu と Theran ^{[10]は擬似森林を定義する}スパース条件を一般化している。彼らは、グラフが ( k , l ) -スパースであるとは、n 頂点を持つすべての空でない部分グラフが最大で kn − l 個の辺を持つ場合であり、( k , l ) -スパースで あり 、ちょうどkn − l個の辺を持つ場合であると定義している。したがって、擬似森林は (1,0)-スパースグラフであり、最大擬似森林は (1,0)-タイトグラフである。他のいくつかの重要なグラフ族は、 k と l の他の値から定義される可能性があり 、  l ≤ kの場合、(  k  , l ) -スパースグラフは、 l 個の森林とk  −  l 個の擬似森林の辺が互いに素な和として形成されるグラフとして特徴付けられる可能性がある。^[11]

十分に疎なランダムグラフのほとんど全ては擬似フォレストである。^[12]つまり、c が0 < c < 1/2の定数で、P _c ( n ) がcn個の辺を持つn頂点のグラフから一様にランダムに選択して擬似フォレストを生成する確率である場合、P _c ( n ) はnが大きい場合の極限で 1 に近づく。しかし、c > 1/2 の場合、 cn個の辺を持つほぼすべてのランダムグラフには、一巡しない大きな要素がある。

グラフが単純であるとは、自己ループがなく、同じ端点を持つ複数の辺がないことである。n個のラベル付き頂点を持つ単純な1木の数は^{[13]である。}

${\displaystyle n\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}\sum _{n_{1}+\cdots +n_{k}=n}{\frac {n!}{n_{1}!\cdots n_{k}!}}{\binom {{\binom {n_{1}}{2}}+\cdots +{\binom {n_{k}}{2}}}{n}}.}$

nが300 までの値は、On-Line Encyclopedia of Integer SequencesのシーケンスOEIS :A057500で見つけることができます。

自己ループを許すn頂点上の最大有向擬似森林の数はn ⁿである。これは、各頂点に対して出力エッジの可能な端点がn個あるためである。アンドレ・ジョヤルはこの事実を利用して、最大有向擬似森林と2つの区別されたノードを持つ無向木との間の一対一関係を見つけることで、 nノード上の無向木の数はn ^{n  − 2であるという}ケイリーの公式の全単射証明を与えた。^{[14]自己ループが許されない場合、最大有向擬似森林の数は(} n  −1) ⁿとなる。

有向擬似フォレストと自己関数は、ある意味では数学的に同等です。集合Xからそれ自身への任意の関数 ƒ (つまり、Xの自己準同型) は、 ƒ( x ) = yであるときはいつでもxからyへのエッジを持つ有向擬似フォレストを定義するものとして解釈できます。結果として得られる有向擬似フォレストは最大であり、何らかの値xが ƒ( x ) = xであるときはいつでも自己ループを含めることができます。あるいは、自己ループを省略すると、非最大擬似フォレストが生成されます。逆方向では、任意の最大有向擬似フォレストは、 ƒ( x ) がxから出るエッジのターゲットとなるような関数 ƒ を決定し、任意の非最大有向擬似フォレストは、自己ループを追加することで最大にすることができ、同じ方法で関数に変換できます。このため、最大有向擬似フォレストは関数グラフと呼ばれることもあります。^[2]関数を関数グラフとして見ると、関数理論の観点からは簡単に説明できない特性を記述するための便利な言語が提供されます。この手法は、関数グラフ内のパスに対応する反復関数を含む問題に特に適用されます。

サイクル検出は、関数グラフ内のパスをたどってその中のサイクルを見つける問題であり、暗号学や計算数論において、整数因数分解のためのポラードのローアルゴリズムの一部として、また暗号ハッシュ関数における衝突を見つける方法として応用されている。これらの応用では、ƒ はランダムに動作することが期待される。FlajoletとOdlyzko ^{[15] は、}ランダムに選択されたマッピングから生じる関数グラフのグラフ理論的特性を研究している。特に、誕生日のパラドックスの形式は、 n個の頂点を持つランダムな関数グラフにおいて、ランダムに選択された頂点から始まるパスは通常、ループして O( √ n ) ステップ以内にサイクルを形成することを意味している。Konyaginらは、グラフ統計に関する分析的および計算的進歩を遂げてきた。^[16]

Martin、Odlyzko、Wolfram ^[17]は、セルオートマトンの動きをモデル化する擬似フォレストを調査している。彼らが状態遷移図と呼ぶこれらの機能グラフには、オートマトンセルの集合がとり得る各構成に対応する頂点と、各構成をオートマトンルールに従ってそれに続く構成に接続する辺がある。これらの図の構造から、コンポーネントの数、限界サイクルの長さ、非限界状態をこれらのサイクルに接続するツリーの深さ、図の対称性など、オートマトンの特性を推測することができる。たとえば、入ってくる辺のない頂点はエデンの園のパターンに対応し、自己ループのある頂点は静物画のパターンに対応する。

関数グラフのもう一つの初期の応用は、シュタイナー三重体系の研究に使用された列車である。^[18]三重体系の列車は、記号の可能な各三重を頂点とする関数グラフである。各三重pqr はƒ によってstuにマッピングされる。ここで、pqs、prt、およびqruは三重体系に属する三重であり、それぞれpq、pr、およびqr のペアを含む。列車は、計算が多少面倒ではあるが、三重体系の強力な不変量であることがわかっている。

マトロイドは、特定の要素の集合が独立であると定義され、独立集合がベクトル空間における線型独立の特性をモデルにした特性を満たす数学的構造です。マトロイドの標準的な例の 1 つは、独立集合がグラフのフォレスト内のエッジの集合であるグラフィック マトロイドです。フォレストのマトロイド構造は、グラフの最小全域木を計算するアルゴリズムで重要です。同様に、疑似フォレストからマトロイドを定義することもできます。

任意のグラフG = ( V , E ) について、 Gの辺上にマトロイドを定義できます。このマトロイドでは、辺の集合が独立であるためには、疑似森を形成する必要があります。このマトロイドは、Gの双円マトロイド(または自転車マトロイド)として知られています。^{[19] [20]}このマトロイドの最小の従属集合は、複数のサイクルを持つGの最小連結サブグラフであり、これらのサブグラフは自転車と呼ばれることもあります。自転車には 3 つの種類があります。シータ グラフには 2 つの頂点があり、それらは 3 つの内部的に互いに素なパスで連結されています。8 の字グラフは 1 つの頂点を共有する 2 つのサイクルで構成され、手錠グラフは 1 つのパスで連結された 2 つの互いに素なサイクルで構成されています。^[21] グラフが疑似森であるためには、自転車がサブグラフとして含まれている必要があります。 ^[10]

疑似フォレストの辺の一部を縮小し、他の辺を削除してマイナーを形成すると、別の疑似フォレストが生成されます。したがって、疑似フォレストの族はマイナーに関して閉じており、ロバートソン-シーモア定理は、疑似フォレストが禁止マイナーの有限集合によって特徴付けられることを示唆しています。これは、平面グラフを、完全グラフK ₅も完全二部グラフK _3,3もマイナーとして持たないグラフとして特徴付けるワーグナーの定理と類似しています。上で説明したように、疑似フォレスト以外のグラフには、手錠、8の字、またはシータグラフがサブグラフとして含まれています。任意の手錠グラフまたは8の字グラフは縮約してバタフライグラフ（5頂点の8の字）を形成でき、任意のシータグラフは縮約してダイヤモンドグラフ（4頂点のシータグラフ）を形成できます。^[22]したがって、任意の非疑似フォレストには、バタフライまたはダイヤモンドのいずれかがマイナーとして含まれており、これらはマイナー極小の非疑似フォレストグラフのみです。したがって、グラフが疑似フォレストである場合、それは、バタフライまたはダイヤモンドをマイナーとして含まない場合に限ります。ダイヤモンドのみを禁止し、バタフライを禁止しない場合、結果として得られるより大きなグラフファミリは、サボテングラフと、複数のサボテングラフの非結合和で構成されます。^[23]

もっと簡単に言えば、自己ループを持つマルチグラフを考慮すると、禁止されたマイナーは 1 つだけ、つまり 2 つのループを持つ頂点だけになります。

擬似森林の初期のアルゴリズム的使用には、ネットワーク シンプレックスアルゴリズムと、異なるタイプの商品間の変換をモデル化する一般化フロー問題へのその応用が含まれます。 ^{[3] [24]}これらの問題では、頂点が各商品をモデル化し、エッジが商品間の許容される変換をモデル化するフロー ネットワークが入力として与えられます。各エッジには、容量(単位時間あたりに変換できる商品の量)、フロー乗数(商品間の変換率)、およびコスト(変換単位あたりに発生する損失または利益 (マイナスの場合)) が付けられます。タスクは、フロー ネットワークの各エッジを介して各商品をどれだけ変換するかを決定し、容量制約に従い、どのタイプの商品も未使用のまま蓄積されないようにしながら、コストを最小化し利益を最大化することです。この種の問題は、線形計画法として定式化でき、シンプレックス アルゴリズムを使用して解くことができます。このアルゴリズムから生じる中間解と最終的な最適解は、特別な構造を持っています。入力ネットワークの各エッジは未使用か、最大容量まで使用されていますが、エッジのサブセットは入力ネットワークのスパニング疑似フォレストを形成し、そのフロー量はゼロから最大容量の間になります。このアプリケーションでは、単環グラフは拡張ツリーと呼ばれることもあり、最大疑似フォレストは拡張フォレストと呼ばれることもあります。^[24]

最小全域擬似森林問題は、より大きな辺重み付きグラフG内で最小の重みを持つ全域擬似森林を見つけることです。擬似森林のマトロイド構造により、最小全域木問題と同様の貪欲アルゴリズムによって最小重み最大擬似森林を見つけることができます。しかし、Gabow と Tarjan は、この場合、より効率的な線形時間アプローチを発見しました。^[2]

グラフGの擬似樹木性は、樹木性と同様に、その辺を分割できる擬似森林の最小数として定義されます。つまり、Gが ( k ,0)-スパースとなる最小のk 、またはGの辺を最大kの出次数を持つ有向グラフを形成するように方向付けることができる最小のkです。擬似森林のマトロイド構造により、擬似樹木性は多項式時間で計算できます。^[25]

二分 グラフの各辺にn個の頂点があり、n ^{2 個}の頂点のペアのそれぞれからcn個の辺がランダムに選択されるランダム二分グラフは、 cが 1 より小さい定数である場合に高い確率で擬似フォレストになります。この事実は、カッコウハッシュの分析で重要な役割を果たします。カッコウハッシュは、キーから決定される場所にある 2 つのハッシュテーブルのいずれかを調べることでキーと値のペアを検索するデータ構造です。頂点がハッシュテーブルの場所に対応し、辺がキーの 1 つが見つかる可能性のある 2 つの場所をリンクするグラフ、つまり「カッコウグラフ」を形成できます。カッコウハッシュアルゴリズムは、カッコウグラフが擬似フォレストである場合にのみ、そのすべてのキーの場所を見つけることに成功します。^[26]

擬似森林はグラフの色付けや関連する問題に対する並列アルゴリズムにおいても重要な役割を果たしている。 ^[27]

• ワイスタイン、エリック W.、「単環グラフ」、MathWorld