Incidensmatris - Incidence matrix

I matematik är en incidensmatris en logisk matris som visar förhållandet mellan två objektklasser, vanligtvis kallad incidensrelation . Om den första klassen är X och den andra är Y , har matrisen en rad för varje element i X och en kolumn för varje element i Y . Inmatningen i rad x och kolumn y är 1 om x och y är relaterade (kallas incident i detta sammanhang) och 0 om de inte är det. Det finns variationer; se nedan.

Grafteori

Incidensmatris är en vanlig grafrepresentation i grafteorin . Det skiljer sig från Adjacency-matris som kodar förhållandet mellan vertex-vertex-par.

Oriktade och riktade grafer

En opriktad graf.

I grafteorin har en oriktad graf två typer av incidensmatriser: oorienterad och orienterad.

Den oorienterade incidensmatrisen (eller helt enkelt incidensmatrisen ) för en oriktad graf är en matris B , där n och m är antalet vertikaler respektive kanter , så att om topp och kant är infallande och 0 annars. ${\ displaystyle n \ times m}$ ${\ displaystyle B_ {ij} = 1}$ ${\ displaystyle v_ {i}}$ ${\ displaystyle e_ {j}}$

Till exempel är incidensmatrisen för det oriktade diagrammet som visas till höger en matris som består av 4 rader (motsvarande de fyra hörn, 1–4) och 4 kolumner (motsvarande de fyra kanterna, ): ${\ displaystyle e_ {1}, e_ {2}, e_ {3}, e_ {4}}$

	e ₁	e ₂	e ₃	e ₄
1	1	1	1	0
2	1	0	0	0
3	0	1	0	1
4	0	0	1	1

=

${\ displaystyle {\ begin {bmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\\ end {bmatrix}}.}$

Om vi tittar på incidensmatrisen ser vi att summan av varje kolumn är lika med 2. Detta beror på att varje kant har en topp som är ansluten till varje ände.

Den infalls matris av en riktad graf är en matris B där n och m är antalet hörn och kanter respektive, så att om kant blad vertex , en om det kommer in vertex och 0 annars (många författare använder det motsatta tecknet konvention). ${\ displaystyle n \ times m}$ ${\ displaystyle B_ {ij} = - 1}$ ${\ displaystyle e_ {j}}$ ${\ displaystyle v_ {i}}$ ${\ displaystyle v_ {i}}$

Den orienterade incidensmatrisen för en icke-riktad graf är incidensmatrisen, i betydelsen riktade grafer, för vilken orientering som helst i diagrammet. Det vill säga i kolumnen av kant e finns det en 1 i raden som motsvarar ett toppunkt för e och en −1 i raden som motsvarar det andra toppunktet av e , och alla andra rader har 0. Den orienterade incidensmatrisen är unik upp till negering av någon av kolumnerna, eftersom negering av inmatningarna i en kolumn motsvarar att vända på en kant.

Den oorienterade incidensmatrisen för en graf G är relaterad till angränsningsmatrisen för dess linjediagram L ( G ) genom följande sats:

{\ displaystyle A (L (G)) = B (G) ^ {\ textsf {T}} B (G) -2I_ {m}.}

där A ( L ( G )) är angränsningsmatrisen för linjediagrammet för G , B ( G ) är incidensmatrisen och I _m är identitetsmatrisen för dimension m .

Den diskreta Laplacian (eller Kirchhoff-matrisen) erhålls från den orienterade incidensmatrisen B ( G ) med formeln

{\ displaystyle B (G) B (G) ^ {\ textsf {T}}.}

Det integrerade cykelutrymmet i en graf är lika med nollutrymmet i dess orienterade incidensmatris, betraktad som en matris över heltal eller reella eller komplexa tal . Den binära cykeln utrymmet är nollutrymme av dess orienterade eller oorienterade incidens matris, ses som en matris över det två element fält .

Signerade och dubbelriktade grafer

Incidensmatrisen för en signerad graf är en generalisering av den orienterade incidensmatrisen. Det är incidensmatrisen för varje dubbelriktad graf som orienterar den givna signerade grafen. Kolumnen med en positiv kant har en 1 i raden som motsvarar en slutpunkt och en -1 i raden som motsvarar den andra slutpunkten, precis som en kant i en vanlig (osignerad) graf. Kolumnen i en negativ kant har antingen en 1 eller en -1 i båda raderna. Linjediagrammet och Kirchhoff-matrisegenskaperna generaliseras till signerade grafer.

Multigrafer

Definitionerna av incidensmatris gäller för grafer med slingor och flera kanter . Kolumnen i en orienterad incidensmatris som motsvarar en slinga är helt noll, såvida inte grafen är signerad och slingan är negativ; då är kolumnen helt noll utom ± 2 i raden av dess infallande toppunkt.

Viktade diagram

En vägd, ej riktad graf

Ett viktat diagram kan representeras genom att använda vikten av kanten i stället för en 1. Till exempel är infallsmatrisen för diagrammet till höger:

	e ₁	e ₂	e ₃	e ₄
1	2	1	5	0
2	2	0	0	0
3	0	1	0	6
4	0	0	5	6

=

${\ displaystyle {\ start {bmatrix} 2 & 1 & 5 & 0 \\ 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 6 \\ 0 & 0 & 5 & 6 \\\ end {bmatrix}}.}$

Hypergrafer

Eftersom kanterna på vanliga grafer bara kan ha två hörn (en i vardera änden) kan kolumnen i en incidensmatris för grafer bara ha två poster som inte är noll. Däremot kan en hypergraf ha flera hörn tilldelade en kant; således beskriver en allmän matris av icke-negativa heltal en hypergraf.

Incidensstrukturer

Den incidens matris av en infalls struktur C är en p × q matris B (eller dess transponering), där p och q är antalet punkter och linjer respektive, så att B _{i , j} = 1 om punkten p _i och linje L _j är incident och 0 annars. I detta fall är incidensmatrisen också en biadjacency-matris i Levi-grafen för strukturen. Eftersom det finns en hypergraf för varje Levi-graf, och tvärtom , beskriver incidensmatrisen för en incidensstruktur en hypergraf.

Slutliga geometrier

Ett viktigt exempel är en ändlig geometri . I ett ändligt plan är X till exempel uppsättningen punkter och Y är uppsättningen linjer. I en ändlig geometri med högre dimension kan X vara uppsättningen punkter och Y kan vara uppsättningen av delområden av dimensionen en mindre än dimensionen för hela rymden (hyperplan); eller, mer allmänt, kan X vara uppsättningen för alla delutrymmen för en dimension d och Y uppsättningen för alla delutrymmen för en annan dimension e , med incidens definierad som inneslutning.

Polytoper

På ett liknande sätt kan förhållandet mellan celler vars dimensioner skiljer sig åt i en polytop representeras av en incidensmatris.

Blockera design

Ett annat exempel är en blockdesign . Här är X en begränsad uppsättning "punkter" och Y är en klass av underuppsättningar av X , kallade "block", underkastade regler som beror på typen av design. Incidensmatrisen är ett viktigt verktyg i teorin om blockdesign. Det kan till exempel användas för att bevisa Fishers ojämlikhet , en grundläggande teorem för balanserade ofullständiga 2-mönster (BIBD), att antalet block är åtminstone antalet punkter. Med tanke på blocken som ett system av uppsättningar är det permanenta i incidensmatrisen antalet system med distinkta representanter (SDR).

Referenser

Vidare läsning

Diestel, Reinhard (2005), Graph Theory , Graduate Texts in Mathematics , 173 (3rd ed.), Springer-Verlag, ISBN 3-540-26183-4
Jonathan L Gross, Jay Yellen, Graph Theory and its applications , andra upplagan, 2006 (s 97, Incidensmatriser för oriktade grafer; s 98, incidensmatriser för digrafer)

externa länkar

Weisstein, Eric W. "Incidensmatris" . MathWorld .

Languages

In other projects