辺と頂点の空間

3 頂点グラフの場合は頂点空間、3 エッジ グラフの場合はエッジ空間。

数学の分野であるグラフ理論において、無向グラフの辺空間と頂点空間は、それぞれ辺集合と頂点集合によって定義されるベクトル空間である。これらのベクトル空間を用いることで、線型代数の手法を用いてグラフを研究すること が可能になる。

意味

を有限無向グラフとする。Gの頂点空間は、すべての関数 の2つの元 からなる有限体上のベクトル空間である。 のすべての元は、その頂点に 1 を割り当てるVの部分集合に自然に対応する。また、 Vのすべての部分集合は、その特性関数によってにおいて一意に表される。辺空間は、辺集合Eによって自由に生成される -ベクトル空間である。したがって、頂点空間の次元はグラフの頂点数であり、辺空間の次元は辺数である。 ${\displaystyle G:=(V,E)}$ ${\displaystyle {\mathcal {V}}(G)}$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace }$ ${\displaystyle V\rightarrow \mathbb {Z} /2\mathbb {Z} }$ ${\displaystyle {\mathcal {V}}(G)}$ ${\displaystyle {\mathcal {V}}(G)}$ ${\displaystyle {\mathcal {E}}(G)}$ ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

これらの定義はより明確にすることができます。例えば、エッジ空間は次のように記述できます。

• 要素は の部分集合である。つまり、集合はEの冪集合である。${\displaystyle E}$ ${\displaystyle {\mathcal {E}}(G)}$
• ベクトルの加算は対称差として定義されます。${\displaystyle P+Q:=P\triangle Q\qquad P,Q\in {\mathcal {E}}(G)}$
• スカラー乗算は次のように定義されます。
  • ${\displaystyle 0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)}$
  • ${\displaystyle 1\cdot P:=P\qquad P\in {\mathcal {E}}(G)}$

Eのシングルトン部分集合はの基底を形成します。 ${\displaystyle {\mathcal {E}}(G)}$

は、 に対して定義されているのと同様なベクトル加算とスカラー乗算を持つベクトル空間に変換されたVの冪集合と考えることもできます。 ${\displaystyle {\mathcal {V}}(G)}$ ${\displaystyle {\mathcal {E}}(G)}$

プロパティ

グラフの接続行列 は、1つの可能な線形変換を定義する。${\displaystyle H}$ ${\displaystyle G}$

${\displaystyle H:{\mathcal {E}}(G)\to {\mathcal {V}}(G)}$

の辺空間と頂点空間の間の空間。 の接続行列は線形変換として、各辺をその2つの接続頂点に写像する。 と の間の辺を とすると 、${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle vu}$ ${\displaystyle v}$ ${\displaystyle u}$

${\displaystyle H(vu)=v+u}$

サイクル空間とカット空間はエッジ空間の サブ空間です。

参考文献

• ディーステル、ラインハルト（2005年）、グラフ理論（第3版）、シュプリンガー、ISBN 3-540-26182-6（電子版第3版は著者のサイトから無料で入手可能です）。

参照

• 自転車スペース
• スペースをカット