辺と頂点の空間

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

を有限無向グラフとします。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版は著者のサイトから無料で入手できます）。

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