耳の分解

グラフ理論では、無向グラフGの耳とは、パスPの 2 つの端点が一致する可能性があるが、それ以外の場合は辺や頂点の繰り返しが許されないパスであり、Pのすべての内部頂点はGで次数2 を持ちます。無向グラフGの耳分解は、辺の集合を耳のシーケンスに分割したもので、各耳の 1 つまたは 2 つの端点はシーケンス内の前の耳に属し、各耳の内部頂点はどの前の耳にも属しません。また、ほとんどの場合、シーケンスの最初の耳は閉路でなければなりません。オープン耳分解または適切な耳分解は、最初の耳の後のそれぞれの耳の 2 つの端点が互いに異なる耳分解です。

イヤー分解は、いくつかの重要なグラフ クラスを特徴付けるために、また効率的なグラフ アルゴリズムの一部として使用できます。また、グラフからマトロイドに一般化することもできます。

いくつかの重要なグラフのクラスは、特定のタイプの耳分解を持つグラフとして特徴付けられる場合があります。

グラフは、任意の ( k − 1) 個の頂点を削除しても接続されたサブグラフが残る場合、 k頂点 接続であり、任意の ( k − 1) 個の辺を削除しても接続されたサブグラフが残る場合、 k辺接続です 。

以下の結果は、Hassler Whitney  (1932) によるものです。

グラフが2 頂点連結となるのは、オープン イヤー分解がある場合のみです。${\displaystyle G=(V,E)}$${\displaystyle |E|\geq 2}$

以下の結果はハーバート・ロビンズ (1939) によるものです。

グラフが 2 辺連結となるのは、グラフに ear 分解がある場合のみです。

どちらの場合も、耳の数は、与えられたグラフの回路ランクと必ず等しくなります。ロビンズは、2 辺連結グラフの耳分解を、ロビンズの定理を証明するツールとして導入しました。ロビンズの定理とは、これらがまさに、強く連結された方向を与えられるグラフであるというものです。耳分解に関するホイットニーとロビンズの先駆的な研究により、耳分解はホイットニー–ロビンズ合成とも呼ばれることがあります(Gross & Yellen 2006)。

非分離型耳分解は、1 つの例外を除く各頂点vについて、 v の隣接点が分解内で最初に出現する時点がvの最初に出現する時点よりも後の時点であるような、開いた耳分解です。このタイプの耳分解は、ホイットニーの結果を一般化するために使用できます。

グラフが3 頂点連結であるためには、G に非分離型耳分解が必要です。${\displaystyle G=(V,E)}$${\displaystyle |V|\geq 2}$

このような分解が存在する場合、 Gの特定の辺uvに関して、 uが最初の ear にあり、v が複数の辺を持つ最後の ear の新しい頂点であり、uv が単一辺の ear であるような方法で分解を選択できます。この結果は、Cheriyan & Maheshwari (1988) によって最初に明示的に述べられましたが、Schmidt (2013b) が説明しているように、これは Lee Mondshein の 1971 年の博士論文の結果と同等です。最大平面グラフの非分離 ear 分解に密接に関連する構造は、標準順序と呼ばれ、グラフ描画の標準的なツールでもあります。

上記の定義は有向グラフにも適用できます。耳は、すべての内部頂点の入次数と出次数が1 である有向パスになります。有向グラフは、すべての頂点から他のすべての頂点への有向パスが含まれている場合、強く接続されています。 この場合、次の定理が成り立ちます (Bang-Jensen & Gutin 2007、定理 7.2.2)。

有向グラフは、耳分解がある場合にのみ強く連結されます。

それぞれの耳が奇数の辺を使用する場合、耳分解は奇数です。因数臨界グラフは、各頂点vについて、グラフからv を削除すると、残りの頂点が完全に一致するような、奇数の頂点を持つグラフです。László Lovász  (1972) は次のことを発見しました。

グラフGが因数臨界となるのは、G が奇数耳分解を持つ場合のみです。

より一般的には、Frank (1993) の結果により、任意のグラフG内で、偶数耳が最も少ない耳分解を見つけることが可能です。

ツリーイヤー分解は、最初のイヤーが単一のエッジであり、後続のイヤーごとに単一のイヤー、があり、 の両方の端点が上にあるような適切なイヤー分解です(Khuller 1989)。ネストされたイヤー分解は、各イヤー内で、 内にある他のイヤーの端点のペアの集合がネストされた区間の集合を形成するようなツリー イヤー分解です。シリーズ パラレル グラフは、指定された 2 つのターミナルsとt を持つグラフで、シリーズ合成 (1 つの小さいグラフの 1 つのターミナルを他の小さいグラフの 1 つのターミナルに識別し、他の 2 つのターミナルを結合されたグラフのターミナルとして保持する) とパラレル合成 (2 つの小さいグラフの両方のターミナルのペアを識別する) の 2 つの方法のいずれかで小さいシリーズ パラレル グラフを再帰的に結合することによって形成されます。 ${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle i>j}$${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle P_{j}}$${\displaystyle P_{i}}$${\displaystyle P_{j}}$

以下の結果はDavid Eppstein  (1992) によるものです。

2 頂点接続グラフは、ネストされた耳分解を持つ場合にのみ直列 - 並列になります。

さらに、2 頂点接続の直列並列グラフのオープン イヤー分解はネストされている必要があります。2 つの端子間のパスから始まるオープン イヤー分解を使用することで、2 頂点接続されていない直列並列グラフに結果を拡張できます。

耳分解の概念はグラフからマトロイドに拡張できます。マトロイドの耳分解は、マトロイドの回路のシーケンスとして定義され、次の 2 つの特性を持ちます。

• シーケンス内の各回路は、前の回路と空でない交差を持ち、
• シーケンス内の各回路は、シーケンス内の前のすべての回路が縮小された場合でも回路のままです。

グラフGのグラフィック マトロイドに適用すると、この耳分解の定義はGの適切な耳分解の定義と一致します。つまり、各回路に少なくとも 1 つのエッジが前の回路にも属している必要があるという要件によって、不適切な分解が排除されます。この定義を使用すると、シーケンス内の各回路に奇数の新しい要素が含まれる耳分解がある場合、マトロイドは因子臨界であると定義できます (Szegedy & Szegedy 2006)。

古典的なコンピュータでは、2 辺接続グラフの ear 分解と 2 頂点接続グラフの open ear 分解は、各 ear を 1 つずつ見つける貪欲アルゴリズムによって見つけることができます。Schmidt (2013a) では、ear 分解、open ear 分解、st 番号付け、および st 方向 (存在する場合) を同時に線形時間で計算する単純な貪欲アプローチが示されています。このアプローチは、1 つのパス生成ルールによってチェーン分解と呼ばれる特殊な ear 分解を計算することに基づいています。Schmidt (2013b) は、分離しない ear 分解も線形時間で構築できることを示しています。

Lovász (1985)、Maon、Schieber & Vishkin (1986)、および Miller & Ramachandran (1986) は、さまざまな種類の耳分解を構築するための効率的な並列アルゴリズムを提供しました。たとえば、2 辺接続グラフの耳分解を見つけるために、Maon、Schieber & Vishkin (1986) のアルゴリズムは次の手順に従います。

1. 指定されたグラフの全域木を見つけ、その木のルートを選択します。
2. ツリーの一部ではない各エッジuvについて、ルートとuおよびvの最小共通祖先との間の距離を決定します。
3. ツリーの一部である各エッジuvについて、対応する「マスター エッジ」、つまりツリーにwx を追加することによって形成されるサイクルがuv を通過する非ツリー エッジwx を見つけます。また、そのようなエッジの中で、wとx はルートに可能な限り近い最低の共通祖先を持ちます (同点はエッジ識別子によって分割されます)。
4. それぞれの非ツリー エッジに対して、そのエッジとそれがマスターであるツリー エッジから構成される耳を形成し、その耳をルートからのマスター エッジの距離で順序付けます (同じタイブレーク ルールを使用)。

これらのアルゴリズムは、接続性のテスト、直列-並列グラフの認識、グラフのst番号付けの構築 (平面性テストにおける重要なサブルーチン) など、他の問題のサブルーチンとして使用できます。

与えられたマトロイドの耳分解は、すべての耳にマトロイドの同じ固定要素が含まれるという追加の制約があり、マトロイドの独立性オラクルへのアクセスがあれば、多項式時間で見つけることができます(Coullard & Hellerstein 1996)。