末梢サイクル

グラフ理論において、無向グラフの周辺サイクル（または周辺回路）は、直感的には、グラフのどの部分も他のどの部分からも分離しないサイクルです。周辺サイクル（または、当初は周辺多角形と呼ばれていました。Tutteがサイクルを「多角形」と呼んだため）は、 Tutte (1963)によって初めて研究され、平面グラフの特徴付けや非平面グラフのサイクル空間の生成において重要な役割を果たします。^{[ 1 ]}

末梢サイクル${\displaystyle C}$グラフにおいて${\displaystyle G}$は、いくつかの同等な方法のいずれかで正式に定義できる。

• ${\displaystyle C}$連結グラフ内の単純サイクルで、任意の 2 つのエッジに対して、${\displaystyle e_{1}}$そして${\displaystyle e_{2}}$で${\displaystyle G\setminus C}$パスが存在する${\displaystyle G}$それは${\displaystyle e_{1}}$、で終わる${\displaystyle e_{2}}$、内部頂点は に属しません${\displaystyle C}$[ ^{2 ]​}
• もし${\displaystyle C}$は任意の部分グラフである。${\displaystyle G}$橋^{[ 3 ]}​​${\displaystyle C}$最小部分グラフ${\displaystyle B}$の${\displaystyle G}$それは辺が互いに素である${\displaystyle C}$そして、その接続点（両方のエッジに隣接する頂点）がすべて${\displaystyle B}$そして${\displaystyle G\setminus B}$) は${\displaystyle C}$[ ^{4 ]単純な}サイクル${\displaystyle C}$橋がちょうど１つある場合は周辺的である。^{[ 5 ]}
• シータグラフではない連結グラフでは、周辺サイクルはコードを持つことができません。なぜなら、コードはグラフの残りの部分から分離されたブリッジになるからです。この場合、${\displaystyle C}$サブグラフが、誘導サイクルの性質を持つ場合、それは周辺的である。${\displaystyle G\setminus C}$エッジと頂点を削除して形成${\displaystyle C}$接続されています。^{[ 6 ]}

これらの定義の等価性は容易に理解できる。${\displaystyle G\setminus C}$（それと繋がる辺と共に）${\displaystyle C}$）または誘導に失敗する原因となるサイクルの弦は、いずれの場合もブリッジでなければならず、また、2 つのエッジが内部頂点を持たないパスの端である場合に関連付けられるエッジ上の二項関係の同値類でなければならない。${\displaystyle C}$[ ^{7 ]​}

周辺サイクルは多面体グラフの理論、すなわち3頂点連結平面グラフに現れる。すべての平面グラフにおいて${\displaystyle G}$、そしてすべての平面埋め込み${\displaystyle G}$埋め込みの誘導サイクルとなる面は周辺サイクルでなければならない。多面体グラフでは、すべての面が周辺サイクルであり、すべての周辺サイクルは面である。^{[ 8 ]}この事実から、（組み合わせ的同値性、外側の面の選択、および平面の向きを除いて）すべての多面体グラフは一意の平面埋め込みを持つことがわかる。^{[ 9 ]}

平面グラフでは、サイクル空間は面によって生成されますが、非平面グラフでは周辺サイクルが同様の役割を果たします。すなわち、すべての3頂点連結有限グラフにおいて、サイクル空間は周辺サイクルによって生成されます。^{[ 10 ]}この結果は、局所的に有限だが無限なグラフにも拡張できます。^{[ 11 ]}特に、3連結グラフは必ず周辺サイクルを含むことが保証されます。周辺サイクルを含まない2連結グラフも存在します（例として完全二部グラフがあります）。${\displaystyle K_{2,4}}$（各サイクルに2つのブリッジがある）だが、2連結グラフの最小次数が3であれば、少なくとも1つの周辺サイクルが含まれる。^{[ 12 ]}

3連結グラフの周辺サイクルは線形時間で計算でき、平面性テストの設計に使用されてきました。^{[ 13 ]} また、非分離耳分解というより一般的な概念にも拡張されました。グラフの平面性をテストするアルゴリズムの中には、問題をより小さな部分問題に分割するために、周辺ではないサイクルを見つけることが有用なものがあります。回路ランクが3未満の2連結グラフ（サイクルグラフやシータグラフなど）では、すべてのサイクルが周辺ですが、回路ランクが3以上のすべての2連結グラフには、線形時間で見つけることができる非周辺サイクルがあります。^{[ 14 ]}

弦グラフを一般化すると、Seymour & Weaver (1984) は、すべての周辺サイクルが三角形であるグラフを絞め殺しグラフと定義します。彼らは、これらのグラフを弦グラフと最大平面グラフのクリーク和として特徴付けています。^{[ 15 ]}

周辺サイクルは非分離サイクルとも呼ばれるが、^{[ 2 ]}この用語は曖昧で、関連するが異なる 2 つの概念にも使用されている。1 つは、除去すると残りのグラフが切断される単純なサイクル、^{[ 16 ]}および、サイクルに沿って切断してもグラフが埋め込まれているサーフェスが切断されないような、トポロジー的に埋め込まれたグラフのサイクルである。 ^{[ 17 ]}

マトロイドにおいて、非分離回路とは、マトロイドの回路（すなわち、最小依存集合）であって、その回路を削除しても、より小さく連結なマトロイド（すなわち、マトロイドの直和として表せないマトロイド）が残るような回路のことである。 ^{[ 18 ]}これらは周辺サイクルに類似しているが、グラフマトロイド（回路がグラフの単純サイクルであるマトロイド）においても同じではない。例えば、完全二部グラフでは${\displaystyle K_{2,3}}$、各サイクルは周辺的である（ブリッジが1つ、2エッジのパスのみを持つ）が、このブリッジによって形成されるグラフィックマトロイドは接続されていないため、グラフィックマトロイドの回路は存在しない。${\displaystyle K_{2,3}}$分離しない。