Sparsity matroid

En sparsitetsmatroid är en matematisk struktur som fångar hur tätt en multigraf är befolkad med kanter. För att packa upp detta lite, är sparsity ett mått på densiteten i en graf som begränsar antalet kanter i en subgraf. Egenskapen att ha en viss matroid som dess densitetsmått är invariant under grafisomorfismer och därför är det en grafinvariant .

Graferna vi är intresserade av generaliserar enkla riktade grafer genom att tillåta flera samma orienterade kanter mellan par av hörn. Matroider är en ganska allmän matematisk abstraktion som beskriver mängden oberoende i, på olika sätt, punkter i det geometriska rummet och banor i en graf; när de tillämpas för att karakterisera gleshet, beskriver matroider vissa uppsättningar av glesa grafer. Dessa matroider är kopplade till den strukturella styvheten hos grafer och deras förmåga att sönderdelas till kant-disjunkta träd via Tutte och Nash-Williams teorem . Det finns en familj av effektiva algoritmer, kända som pebble-spel , för att avgöra om en multigraf uppfyller det givna sparsitetsvillkoret.

Definitioner

$(k,l)$ -gles multigraf. . En multigraf $G=(V,E)$ är $(k,l)$ -gles, där $k$ och $l$ är icke-negativa heltal, om för varje subgraf $G'=(V',E')$ av $G$ , har vi $|E|\leq k|V|-l$ .

$(k,l)$ -tight multigraf. En multigraf $G=(V,E)$ är $(k,l)$ -tät om den är $(k ,l)$ -glesa och $|E|=k|V|-l$ .

$[a,b]$ -gles och snäv multigraf. En multigraf $G=(V,E\cup F)$ är $[a,b]$ -gles om det finns en delmängd $F'\subset F$ så att subgrafen $G'=(V,E\cup F')$ är $(a,a)$ -gles och subgrafen $G''=(V,F\setminus F')$ är $(b) ,b)$ -gles. Multigrafen $G$ är $[a,b]$ -tät om dessutom $|E\cup F|=(a+b)|V|-(a+b)$ .

$(k,l)$ -sparsitetsmatroid. ( $(k,l)$ -sparsity matroid är en matroid vars grundmängd är kantuppsättningen av hela multigrafen på $n$ , med loop multiplicity $kl$ och kantmångfald $2k-l$ , och vars oberoende mängder är $(k,l)$ -glesa multigrafer på $n$ hörn. Baserna för matroiden är $(k,l)$ -snäva multigrafer och kretsarna är $(k,l)$ -glesa multigrafer $G=(V,E)$ som uppfyller $|E|=k|V|-l+1$ .

De första exemplen på sparsitetsmatroider finns i. Inte alla par $(k,l)$ inducerar en matroid.

Par (k,l) som bildar en matroid

Följande resultat ger tillräckliga begränsningar för $(k,l)$ för existensen av en matroid.

Sats. De $(k,l)$ -glesa multigraferna på $n$ hörn är de oberoende uppsättningarna av en matroid om

• $n\geq 1$ och $l\in [0,k]$ ;
• $n\geq 2$ och $l\in (k,{\frac {3}{2}}k)$ ; eller
• $n=2$ eller $n\geq {\frac {l}{2k-l}}$ och ${\ displaystyle l\in [{\frac {3}{2}}k,2k)}$ .

Några konsekvenser av denna sats är att $(2,3)$ -glesa multigrafer bildar en matroid medan $(3,6)$ -glesa multigrafer inte gör det. Därför måste baserna, dvs $(2,3)$ -täta multigrafer, alla ha samma antal kanter och kan konstrueras med tekniker som diskuteras nedan. Å andra sidan, utan denna matroidstruktur, kommer maximalt $(3,6)$ -glesa multigrafer att ha olika antal kanter, och det är intressant att identifiera den med maximalt antal kanter.

Kopplingar till styvhet och nedbrytning

Strukturell stelhet handlar om att bestämma om nästan alla, dvs generiska , inbäddningar av en (enkel eller multi) graf i något $d$ -dimensionellt metriskt utrymme är stela. Mer exakt ger denna teori kombinatoriska karakteriseringar av sådana grafer. I det euklidiska rymden visade Maxwell att oberoende i en gles matroid är nödvändigt för att en graf ska vara generiskt stel i vilken dimension som helst.

Maxwell Direction. Om en graf $G$ generellt sett är minimalt stel i $d$ -dimensioner, så är den oberoende i $\left(d,{d+ 1 \choose 2}\right)$ -sparsitetsmatroid.

Motsatsen till denna sats bevisades i $2$ -dimensioner, vilket ger en komplett kombinatorisk karaktärisering av generiskt stela grafer i $\mathbb {R} ^{2}$ . Det omvända är dock inte sant för $d\geq 3$ , se kombinatoriska karakteriseringar av generiskt stela grafer .

Andra sparsitetsmatroider har använts för att ge kombinatoriska karakteriseringar av generiskt stela multigrafer för olika typer av ramverk, se stelhet för andra typer av ramverk . Följande tabell sammanfattar dessa resultat genom att ange typen av generisk stel ram i en given dimension och motsvarande sparsitetstillstånd. Låt $kG$ vara multigrafen som erhålls genom att duplicera kanterna på en multigraf $G$$k$ gånger.

Generisk minimalt stel ram	Sparsamt tillstånd
Stångledsramverk i $\mathbb {R} ^{2}$	$(2,3)$ -tight
Stavledsramverk i $\mathbb {R} ^{2}$ under allmänna polyedriska normer	$(2,2)$ -tight
Body-bar ramverk i $\mathbb {R} ^{d}$	$\left({d+1 \choose 2},{d+1 \choose 2}\right)$ -tight
$(d-2)$ -plate-bar ramverk i $\mathbb {R} ^{d}$	$\left({d+1 \choose 2}-1,{d+1 \choose 2}\right)$ -tight
Kroppsgångjärnsram i $\mathbb {R} ^{d}$	$\left({d+1 \choose 2}-1\right)G$ är ${\ displaystyle \left({d+1 \choose 2},{d+1 \choose 2}\right)}$ -tight
Body-cad-ramverk i $\mathbb {R} ^{2}$	primitiv cad-graf är $\left[1,2\right]$ -tight
Body-cad ramverk utan sammanfallande punkter i $\mathbb {R} ^{3}$	primitiv cad-graf är $\left[3,3\right]$ -tight

Tutte och Nash-Williams sats visar att $(k,k)$ -snäva grafer är ekvivalenta med grafer som kan dekomponeras i $k$ kant-disjunkande träd, kallade ${ \displaystyle k}$ -arborescenser. A $(k,a)$ -arborescens är en multigraf $G$ så att addering av $a$ kanter till $G$ ger en $k$ -arborescens. För $l\in [k,2k)$ , a $(k,l)$ -gles multigraf är en ${ \displaystyle (k,lk)}$ -arborescens; detta visades först för $(2,3)$ glesa grafer. Dessutom kan många av styvheten och gleshetsresultaten ovan skrivas i termer av träd som spänner över kanterna.

Konstruera glesa multigrafer

Det här avsnittet ger metoder för att konstruera olika glesa multigrafer med användning av operationer definierade för att konstruera generiskt stela grafer . Eftersom dessa operationer är definierade för en given dimension, låt en $(k,0)$ -extension vara en $k$ -dimensionell $0$ -extension, dvs en ${\ displaystyle 0}$ -extension där den nya vertexen är kopplad till $k$ distinkta hörn. Likaså är en $(k,1)$ -förlängning en $k$ -dimensionell $1$ -förlängning.

Allmänna (k,l)-glesa multigrafer

Den första konstruktionen är för $\left(k,k\right)$ -snäva grafer. En generaliserad $(k,1)$ -förlängning är en trippel $(k,1,j)$ , där $j$ kanter tas bort , för $1\leq j\leq k$ , och den nya vertexen $u$ är kopplad till hörnen på dessa $j$ -kanter och till ${\ displaystyle kj}$ distinkta hörn. Den vanliga $(k,1)$ -tillägget är en $(k,1,1)$ -tillägg.

Sats. En multigraf är $(k,k)$ -tight om och bara om den kan konstrueras från en enda vertex via en sekvens av ( $\displaystyle (k,0)} -$ och $(k,1,j)$ -tillägg.

Denna sats utökades sedan till allmänna $(k,l)$ -snäva grafer. Betrakta en annan generalisering av en $1$ -förlängning betecknad med $(k,1,i,j)$ , för $0\ leq j\leq i\leq k$ , där $j$ -kanterna tas bort, är den nya vertexen $u$ kopplad till hörnen på dessa $j$ -kanter, ${\ displaystyle ij}$ loopar läggs till $u$ och $u$ är kopplad till $ki$ andra distinkta hörn. Låt också $P_{l}$ beteckna en multigraf med en enda nod och $l$ loopar.

Sats. En multigraf $G$ är $(k,l)$ -tät för

• $l\in [1,k]$ om och endast om $G$ kan konstrueras från $P_{kl}$ via en sekvens av $(k,1,i,j)$ -förlängningar, så att $0\leq j\leq i\leq k-1$ och $ij\leq kl$ ;
• $l=0$ om och endast om $G$ kan konstrueras från $P_{kl}$ via en sekvens av ${\ displaystyle (k,1,i,j)}$ -tillägg, så att $0\leq j\leq i\leq k$ och $ij\leq kl$ .

Ingen av dessa konstruktioner är tillräckliga när grafen är enkel. Nästa resultat är för $(k,l)$ -glesa hypergrafer . En hypergraf är $s$ -uniform om var och en av dess kanter innehåller exakt $s$ hörn. Först fastställs villkor för förekomsten av $(k,l)$ -snäva hypergrafer.

Sats. Det finns en $n_{0}$ så att för alla $n\geq n_{0}$ finns det $s$ -enhetliga hypergrafer på $n$ hörn som är $(k,l)$ -täta.

Nästa resultat utökar Tutte och Nash-Williams sats till hypergrafer.

Sats. Om $G$ är en $(k,l)$ -tight hypergraf, för $l\geq k$ , så är ${\displaystyle G} en$$(k,lk)$ arborescens, där de $lk$ tillagda kanterna innehåller minst två hörn.

En karthypergraf är en hypergraf som tillåter en orientering så att varje vertex har en ut-grad på $1$ . En $k$ -map-hypergraph är en map-hypergraph som kan dekomponeras i $k$ kant-disjunkte karthypergrafer.

Sats. Om $G$ är en $(k,l)$ -tight hypergraf, för $k\geq l$ , då är $g$ föreningen av en $l$ -arborescens och en $(kl)$ -map-hypergraf.

(2,3)-glesa grafer

Figur 1. En $(2,3)$ -krets.

Det första resultatet visar att $(2,3)$ -snäva grafer, dvs generiskt minimalt stela grafer i $\mathbb {R} ^{2}$ har Henneberg-konstruktioner.

Sats. En graf $G$ är $(2,3)$ -tät om och bara om den kan konstrueras från hela grafen $K_{2}$ via en sekvens av $0$ - och $1$ -tillägg.

Nästa resultat visar hur man konstruerar $(2,3)$ -kretsar. I den här inställningen kombinerar en $2$ -summa två grafer genom att identifiera två $K_{2}$ subgrafer i varje och sedan ta bort den kombinerade kanten från den resulterande grafen.

Sats. En graf $G$ är en $(2,3)$ -krets om och endast om den kan konstrueras från disjunkta kopior av hela grafen $K_{4}$ via en sekvens av $1$ -tillägg inom anslutna komponenter och $2$ -summor av anslutna komponenter.

Metoden för att konstruera $3$ -anslutna $(2,3)$ -kretsar är ännu enklare.

Sats. En graf $G$ är en $3$ -ansluten $(2,3)$ -krets om och endast om den kan konstrueras från hela grafen ${\ displaystyle K_{4}}$ via en sekvens av $1$ -tillägg.

Dessa kretsar har också följande kombinatoriska egenskap.

Sats. Om en graf $G$ är en $(2,3)$ -krets som inte är hela grafen $K_{4}$ , då $G$ har minst $3$ hörn av grad $3$ så att en $1$ -reduktion på någon av dessa hörn ger en annan $(2, 3)$ -krets.

(2,2)-glesa grafer

Nästa resultat visar hur man konstruerar $(2,2)$ -kretsar med två olika konstruktionsmetoder. För den första metoden visas basgraferna i figur 2 och de tre sammanfogningsoperationerna visas i figur 2. En $1$ -join identifierar en $K_{2}$ subgraf i ${ \displaystyle G_{1}}$ med en kant av en $K_{4}$ subgraf i $G_{1}$ och tar bort de andra två hörnen av $K_{ 4}$ . En $2$ -join identifierar en kant på en $K_{4}$ subgraf i $G_{1}$ med en kant på en $K_{4}$ subgraf i $G_{2}$ och tar bort de andra hörnen på båda $K_{4}$ subgraferna. En $3$ -join tar en grad $3$ vertex $v_{1}$ i $G_{1}$ och en grad $3$ vertex $v_{2}$ i $G_{2}$ och tar bort dem, sedan lägger den till $3$ kanter mellan $G_{1}$ och ${ \displaystyle G_{2}}$ så att det finns en bijektion mellan grannarna till $v_{1}$ och $v_{2}$ .

Figur 2. Basgraferna för att konstruera $(2,2)$ -kretsar.

Figur 3. Uppifrån och ned, $1$ -, $2$ - och $3$ -join-operationerna för att konstruera $(2,2)$ -kretsar.

Den andra metoden använder $2$ -dimensionell vertexuppdelning, definierad i de generiskt stela graferna , och en vertex-to- $K_{4}$ -operation, som ersätter en vertex $v$ av en graf med en $K_{4}$ -graf och kopplar varje granne till $v$ till valfri vertex av $K_{4}$ . Sats. En graf $G$ är en $(2,2)$ -krets om och endast om

• $G$ kan konstrueras från osammanhängande kopior av basgraferna via en sekvens av $1$ -tillägg inom anslutna komponenter och $1$ -, $2$ - och $3$ - summor av anslutna komponenter;
• 

  Figur 4. En $(2,2)$ -krets.
  $G$ kan konstrueras från $K_{4}$ via en sekvens av $0$ - och $1$ -extensions, vertex-to- $K_ {4}$ och $2$ -dimensionella vertexdelningsoperationer

(2,1)-glesa grafer

Följande resultat ger en konstruktionsmetod för $(2,1)$ -snäva grafer och utökar Tutte- och Nash-Williams sats till dessa grafer. För konstruktionen är basgraferna $K_{5}$ med en kant borttagen eller $2$ -summan av två $K_{4}$ grafer (den delade kanten är inte borttagen), se mittdiagrammet i figur 2. En kantsammanfogningsoperation lägger också till en enda kant mellan två grafer.

Sats. En graf $G$ är $(2,1)$ -tight om och endast om

• $G$ kan erhållas från $K_{5}$ med en kant borttagen eller $2$ -summan av två $K_{4}$ grafer via en sekvens av $0$ - och $1$ -extensions, vertex-to- $K_{4}$ , $2$ -dimensionell vertex-delning och kantsammanfogningsoperationer;
• $G$ är en kant-disjunkt förening av ett spännträd och en spännande graf där varje ansluten komponent innehåller exakt en cykel.

Pebble spel

Det finns en familj av effektiva nätverksflödesbaserade algoritmer för att identifiera $(k,l)$ -glesa grafer, där $l\in [0,2k]$ . Den första av dessa typer av algoritmer var för $(2,3)$ -glesa grafer. Dessa algoritmer förklaras på Pebble-spelsidan.