自転車スペース

数学の一分野であるグラフ理論において、無向グラフの（バイナリ）サイクル空間は、その偶数次サブグラフの集合です。

この部分グラフの集合は、2 要素有限体上のベクトル空間として代数的に記述できます。この空間の次元は、グラフの回路階数です。同じ空間は、代数位相幾何学の観点から、グラフの最初のホモロジー群として記述することもできます。ホモロジー理論を使用すると、バイナリサイクル空間は任意のリング上のサイクル空間に一般化できます。

グラフのサイクル空間は、数学的に高度化するにつれて、サブグラフの集合、バイナリベクトル空間、またはホモロジー群として記述できるようになります。

与えられたグラフGの全域サブグラフは、Gの辺の任意の部分集合Sから定義できます。この部分グラフは、G自体と同じ頂点集合を持ちますが(これが「全域」という言葉の意味です)、Sの要素を辺として持ちます。したがって、 m個の辺を持つグラフGには、 G自体と、Gと同じ頂点集合上の空グラフを含む2 ^{m 個}の全域サブグラフがあります。グラフGのすべての全域サブグラフの集合は、Gの辺空間を形成します。^{[1] [2]}

グラフGまたはそのサブグラフの 1 つがオイラーグラフであるとは、その各頂点が偶数個の接続辺を持つ場合である (この数は頂点の次数と呼ばれる)。この特性は、1736 年にケーニヒスベルクの七つの橋に関する論文で、連結グラフが各辺を 1 回だけ訪れる巡回グラフを持つのは、そのグラフがオイラーグラフである場合のみであることを証明したレオンハルト・オイラーにちなんで名付けられた。ただし、サイクル空間を定義する目的では、オイラーグラフのサブグラフは連結されている必要はない。たとえば、すべての頂点が互いに接続されていない空のグラフは、この意味でオイラーグラフである。グラフのサイクル空間は、そのオイラーグラフ全体にわたるサブグラフの集合である。^{[1] [2]}

与えられたグラフの2つの全域部分グラフに集合の和集合や積集合などの集合演算を適用すると、結果は再び部分グラフになります。このように、任意のグラフのエッジ空間はブール代数として解釈できます。^[3]

サイクル空間も代数的構造を持っていますが、より制限されたものです。2 つのオイラー部分グラフの和集合または積集合は、オイラーでない場合があります。しかし、2 つのオイラー部分グラフ (2 つのグラフのうちの 1 つにのみ属する辺で構成されるグラフ) の対称差は、やはりオイラーです。 ^[1]これは、要素数が偶数である 2 つの集合の対称差も偶数であるという事実から導かれます。この事実を各頂点の近傍に個別に適用すると、対称差演算子がオイラーであるという特性を保持していることがわかります。

対称差分演算に関して閉じた集合の族は、2 元有限体上のベクトル空間として代数的に記述できます。^[4]この体には 0 と 1 の 2 つの元があり、その加算と乗算の演算は、2 を法とする整数のよく知られた加算と乗算として記述できます。ベクトル空間は、よく知られた実ベクトル空間の特性を一般化する特定の特性を満たす加算とスカラー乗算の演算を伴う元の集合で構成されます。サイクル空間の場合、ベクトル空間の要素はオイラー部分グラフ、加算演算は対称差分、スカラー 1 による乗算は恒等演算、スカラー 0 による乗算はすべての要素を空グラフに渡し、サイクル空間の 加法恒等元を形成します。 ${\displaystyle \mathbb {Z} _{2}}$

辺空間も、対称差を加法とする上のベクトル空間である。ベクトル空間として、グラフのサイクル空間とカット空間（グラフのカット全体にわたる辺集合の族）は、辺空間内で互いに直交補集合である。これは、グラフ内の辺集合がカットを形成するための必要十分条件は、すべてのオイラー部分グラフが と偶数個の辺を共有することであり、オイラー部分グラフを形成するための必要十分条件は、すべてのカットが と偶数個の辺を共有することである。^[2]これら 2 つの空間は直交補集合であるが、一部のグラフには、両方に属する空でない部分グラフが存在する。そのような部分グラフ（オイラーカット）がグラフの一部として存在するのは、 が偶数個の全域林を持つ場合のみである。^[5]${\displaystyle \mathbb {Z} _{2}}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle G}$

無向グラフは、頂点が0次元単体、辺が1次元単体である単体複体とみなすことができます。 ^[6]この位相空間の鎖複体は、辺空間と頂点空間（頂点の集合のブール代数）で構成され、任意のスパニングサブグラフ（辺空間の要素）を奇数次頂点の集合（頂点空間の要素）にマッピングする境界演算子によって接続されています。ホモロジー群

${\displaystyle H_{1}(G,\mathbb {Z} _{2})}$

頂点空間のゼロ要素にマップされるエッジ空間の要素で構成されます。これらはまさにオイラー部分グラフです。そのグループ演算はオイラー部分グラフ上の対称差演算です。

この構成を任意の環に置き換えると、サイクル空間の定義を、与えられた環に係数を持つサイクル空間に拡張することができ、その係数は環上の加群を形成する。^[7] 特に、積分サイクル空間は空間である。 ${\displaystyle \mathbb {Z} _{2}}$

${\displaystyle H_{1}(G,\mathbb {Z} ).}$

グラフ理論の用語で定義するには、グラフの任意の方向を選択し、グラフの積分サイクルを、各頂点で、入ってくるエッジに割り当てられた数値の合計が、出ていくエッジに割り当てられた数値の合計に等しいという性質を持つ、エッジ（エッジ上の自由アーベル群の要素）への整数の割り当てとして定義します。^[8]${\displaystyle G}$${\displaystyle G}$

または（サイクル空間を法として）の要素で、辺に割り当てられた数値がすべてゼロでないという追加の特性を持つものは、それぞれnowhere-zeroフローまたはnowhere-zero -フローと呼ばれます。^[9]${\displaystyle H_{1}(G,\mathbb {Z} )}$${\displaystyle H_{1}(G,\mathbb {Z} _{k})}$${\displaystyle k}$${\displaystyle k}$

ベクトル空間として、頂点、辺、連結成分を持つグラフのサイクル空間の次元はである。^{[1] [2] [10]}この数は、グラフの最初のベッティ数として位相的に解釈することができる。 ^{[6]グラフ理論では、これは}回路ランク、サイクロマティック数、またはグラフのヌル性 として知られている。${\displaystyle n}$${\displaystyle m}$${\displaystyle c}$ ${\displaystyle m-n+c}$

この階数の公式と、サイクル空間が 2 元体上のベクトル空間であるという事実を組み合わせると、サイクル空間内の要素の総数はちょうど であることが示されます。 ${\displaystyle 2^{m-n+c}}$

ベクトル空間の基底は、他のすべての要素が基底要素の線形結合として記述できるという特性を持つ要素の最小サブセットです。有限次元空間のすべての基底には、空間の次元と同じ数の要素があります。サイクル空間の場合、基底は正確にオイラー部分グラフの族であり、すべてのオイラー部分グラフは基底要素の族の対称差として記述できるという特性があります。 ${\displaystyle m-n+c}$

ヴェブレンの定理^[11]によれば、与えられたグラフのあらゆるオイラー部分グラフは単純閉路に分解できる。単純閉路とは、すべての頂点が次数0または2を持ち、次数2の頂点が連結集合を形成する部分グラフである。したがって、基底要素がすべて単純閉路である基底を見つけることは常に可能である。このような基底は、与えられたグラフの閉路基底と呼ばれる。より強く言えば、基底要素が誘導閉路、または（3頂点連結グラフでは）分離しない誘導閉路である基底を見つけることは常に可能である。^[12]

サイクル基底を構築する方法の 1 つは、グラフの最大の森を形成し、次に森に属さない各辺に対して、の端点を結ぶ森のパスとともに から なるサイクルを形成することです。このようにして形成されたサイクルは線形独立であり (それぞれに他のサイクルのいずれにも属さない辺が含まれます)、基底となるのに適切なサイズを持っているため、必然的に基底になります。このようにして形成された基底は、基本サイクル基底と呼ばれます(選択された森に関して)。^[1]${\displaystyle e}$${\displaystyle C_{e}}$${\displaystyle e}$${\displaystyle e}$${\displaystyle C_{e}}$${\displaystyle e}$${\displaystyle m-n+c}$

サイクル基底におけるサイクルの線形順序が存在し、各サイクルに前のサイクルの一部ではない辺が少なくとも1つ含まれる場合、そのサイクル基底は弱基本的と呼ばれます。すべての基本サイクル基底は弱基本的です（すべての線形順序に対して）が、その逆は必ずしも当てはまりません。弱基本的ではないグラフと、それらのグラフのサイクル基底が存在します。^[13]

グラフの辺に実数の重みが与えられている場合、サブグラフの重みはその辺の重みの合計として計算される。サイクル空間の最小重み基底は必然的にサイクル基底であり、多項式時間で構築できる。^[8]最小重み基底は常に弱基本基底であるとは限らず、そうでない場合は、最小の重みを持つ弱基本基底を見つけることはNP困難である。 ^[13]

平面グラフが平面に埋め込まれている場合、その辺と頂点の連鎖複合体は、グラフの面の集合も含む高次元の連鎖複合体に埋め込まれることがあります。この連鎖複合体の境界マップは、任意の 2 連鎖 (面の集合) を、2 連鎖内の奇数の面に属する辺の集合に変換します。2 連鎖の境界は必然的にオイラー部分グラフであり、すべてのオイラー部分グラフは、この方法で正確に 2 つの異なる 2 連鎖 (それぞれが他方の補集合) から生成できます。 ^[14]このことから、埋め込みの境界付き面の集合は、平面グラフのサイクル基底を形成することがわかります。つまり、このサイクルの集合から境界なし面を削除すると、各オイラー部分グラフを生成できる方法の数が 2 から 1 に減ります。

サンダース・マックレーンにちなんで名付けられたマックレーンの平面性基準は、平面グラフをサイクル空間とサイクル基底の観点から特徴付ける。有限無向グラフが平面的であるためには、グラフの各辺が最大で 2 つの基底サイクルに参加するサイクル基底を持つ必要があるとしている。平面グラフでは、埋め込みの境界面の集合によって形成されるサイクル基底は、必然的に次の特性を持つ。各辺は、それが分離する 2 つの面の基底サイクルにのみ参加する。逆に、サイクル基底が辺ごとに最大で 2 つのサイクルを持つ場合、そのサイクルはそのグラフの平面埋め込みの境界面の集合として使用できる。^{[14] [15]}

平面グラフのサイクル空間は、その双対グラフのカット空間であり、その逆も同様である。平面グラフの最小重みサイクル基底は、その境界面によって形成される基底と必ずしも同じではない。面ではないサイクルを含むことがあり、また、一部の面は最小重みサイクル基底にサイクルとして含まれないことがある。2 つのサイクルが互いに交差しない最小重みサイクル基底が存在する。基底内の 2 つのサイクルごとに、サイクルが境界面の互いに素な部分集合を囲むか、2 つのサイクルのうちの 1 つがもう 1 つを囲む。サイクル空間とカット空間の双対性に従い、平面グラフのこの基底は、双対グラフのGomory–Hu 木、つまりそのカット空間の最小重み基底に対応する。^[16]

平面グラフでは、異なる色による着色は、を法とする整数の環上のどこにもゼロのないフローと双対である。この双対性では、2つの隣接する領域の色の違いは、領域を分離するエッジを横切るフロー値によって表される。特に、どこにもゼロのない4フローの存在は、4色定理と同等である。スナーク定理は、この結果を非平面グラフに一般化している。^[17]${\displaystyle k}$${\displaystyle \mathbb {Z} _{k}}$${\displaystyle k}$