Kantutrymme - Edge space

I matematisk disciplinen av grafteori , den kantutrymmet och vertex utrymme av en oriktad graf är vektorrum definieras i termer av de kant och vertex uppsättningar, respektive. Dessa vektorutrymmen gör det möjligt att använda tekniker för linjär algebra för att studera grafen.

Definition

Låt vara en ändlig okontrollerad graf. Den vertex utrymme av G är vektorn utrymme över den ändliga fältet av två element av alla funktioner . Varje element av naturligtvis motsvarar delmängden av V som tilldelar en 1 till dess hörn. Också varje delmängd av V representeras unikt genom sin karakteristiska funktion. Den kant utrymmet är -vector utrymmet fritt genereras av kanten som E . Dimensionen på toppmellanrummet är således antalet vertikaler i diagrammet, medan dimensionen av kantutrymmet är antalet kanter. ${\ 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}}$

Dessa definitioner kan göras mer tydliga. Vi kan till exempel beskriva kantutrymmet på följande sätt:

• element i vektorutrymmet är delmängder av , det vill säga eftersom en uppsättning är effektuppsättningen för E${\ displaystyle E}$${\ displaystyle {\ mathcal {E}} (G)}$
• vektortillsats definieras som den symmetriska skillnaden :${\ displaystyle P + Q: = P \ triangel Q \ qquad P, Q \ i {\ mathcal {E}} (G)}$
• skalförstärkning definieras av:
  • ${\ displaystyle 0 \ cdot P: = \ emptyset \ qquad P \ in {\ mathcal {E}} (G)}$
  • ${\ displaystyle 1 \ cdot P: = P \ qquad P \ in {\ mathcal {E}} (G)}$

De singleton delmängder av E ligga till grund för . ${\ displaystyle {\ mathcal {E}} (G)}$

Man kan också tänka sig som kraftsättningen av V som görs till ett vektorutrymme med liknande vektortillsats och skalförstärkning som definierats för . ${\ displaystyle {\ mathcal {V}} (G)}$${\ displaystyle {\ mathcal {E}} (G)}$

Egenskaper

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

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

mellan kantutrymmet och topprymmet på . Förekomstmatrisen för , som en linjär transformation, kartlägger varje kant till dess två infallande vertikaler. Låt vara kanten mellan och sedan ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle vu}$${\ displaystyle v}$${\ displaystyle u}$

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

Den cykel utrymme och skurna utrymmet är linjära underrum av kantutrymme.

referenser

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

Se även

• cykelutrymme
• skär utrymme