Kant- och vertexutrymmen

I den matematiska disciplinen grafteori är kantutrymmet och vertexutrymmet för en oriktad graf vektorrum definierade i termer av kant- respektive vertexuppsättningar . Dessa vektorrum gör det möjligt att använda tekniker för linjär algebra för att studera grafen.

Definition

Låt $G:=(V,E)$ vara en finit oriktad graf. Vertexutrymmet ${\mathcal {V}}(G)$ i G är vektorutrymmet över det ändliga fältet för två element $\displaystyle \mathbb { Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace }$ { av alla funktioner $V\rightarrow \mathbb {Z} /2\mathbb {Z}$ . Varje element av ${\mathcal {V}}(G)$ motsvarar naturligtvis delmängden av V som tilldelar en 1 till dess hörn. Varje delmängd av V representeras också unikt i ${\mathcal {V}}(G)$ av sin karakteristiska funktion. Kantutrymmet ${\mathcal {E}}(G)$ är $\displaystyle \mathbb {Z} /2\mathbb {Z} }$ { -vektorutrymmet fritt genererat av kantuppsättning E . Dimensionen på vertexutrymmet är alltså antalet hörn i grafen, medan dimensionen på kantutrymmet är antalet kanter.

Dessa definitioner kan göras mer explicit. Till exempel kan vi beskriva kantutrymmet på följande sätt:

element är delmängder av $E$ , det vill säga som en mängd är ${\mathcal {E}}(G)$ potensmängden av E
vektoraddition definieras som den symmetriska skillnaden : $P+Q:=P\triangel Q\qquad P,Q\in {\mathcal {E} }(G)$
skalär multiplikation definieras av:
- $0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)$
- $1\cdot P:=P\qquad P\in {\mathcal {E}}(G)$

Singleton - delmängderna av E bildar en bas för ${\mathcal {E}}(G)$ .

Man kan också tänka på ${\mathcal {V}}(G)$ som potensmängden av V som gjorts till ett vektorrum med liknande vektoraddition och skalär multiplikation som definieras för ${\ displaystyle {\mathcal {E}}(G)}$ .

Egenskaper

Incidensmatrisen $H$ för en graf $\displaystyle G}$ { definierar en möjlig linjär transformation

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

mellan kantutrymmet och vertexutrymmet för $G$ . Incidensmatrisen för $G$ , som en linjär transformation, mappar varje kant till dess två infallande hörn. Låt $vu$ vara kanten mellan $v$ och $u$ då

H(vu)=v+u

Cykelutrymmet och skärutrymmet är linjära delrum till kantutrymmet .

Diestel, Reinhard (2005), Graph Theory (3:e upplagan), Springer , ISBN 3-540-26182-6 (den elektroniska tredje upplagan är fritt tillgänglig på författarens webbplats).

Se även