Illeszkedési mátrix

A Wikipédiából, a szabad enciklopédiából

Az illeszkedési mátrix az egyik gráfelméleti mátrixreprezentáció, bár általánosabban is definiálható hipergráfokra és általában a véges geometria illeszkedési struktúráira is. Gyakran alkalmazzák például a villamosságtanban. Ahogy a neve is mutatja, az élek és csúcsok közötti illeszkedési kapcsolatot reprezentálja. Gyakorlati jelentősége abban rejlik, hogy egy villamos hálózatot megadhatunk egy irányított gráffal a kétféle pólus miatt.

Definíció[szerkesztés | forrásszöveg szerkesztése]

Legyen G n pontú gráf e éllel. Az n × e-es B(G) mátrix legyen a következő:

b_{ij}=
\begin{cases}
0 & \text{ha a }j\text{-edik él nem illeszkedik az }i\text{-edik ponthoz}\\
1 & \text{ha a }j\text{-edik élnek az }i\text{-edik pont a kezdőpontja}\\
-1 & \text{ha a }j\text{-edik élnek az }i\text{-edik pont a végpontja}
\end{cases}

bi j=1 abban az esetben is, ha a j-edik él az i-edik ponthoz illeszkedő hurokél. Irányítatlan esetben is ez a definíció, csak ott a j-edik él mindkét végpontjának megfelelő mátrixelem 1. Ekkor B(G) a G gráf illeszkedési mátrixa.

Példa egy gráf illeszkedési mátrixára[szerkesztés | forrásszöveg szerkesztése]

Címkézett gráf Illeszkedési mátrix
Graf2.png \begin{pmatrix}
1 & 1 & 1 & 0\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & 1\\
\end{pmatrix}

Tételek[szerkesztés | forrásszöveg szerkesztése]

Illeszkedési mátrix rangja[szerkesztés | forrásszöveg szerkesztése]

Tétel: Ha egy hurokélmentes G gráf n pontból és c darab összefüggő komponensből áll, akkor illeszkedési mátrixának rangja n - c.

Bizonyítás: Ha c>1, akkor ha komponensenként felsoroljuk a pontokat és az éleket, akkor a mátrix blokkdiagonális lesz. Így elég azt megmutatni, hogy egy p pontú komponensnek megfelelő blokk rangja p-1. Mivel a blokk sorainak száma p és az összes sor összege a nullvektor (mert minden élnek megfelelő oszlopban egy +1 és -1, valamint p-2 darab 0 található), ezért nyilvánvaló, hogy a rang legfeljebb p-1 lehet. Legyen F egy p pontú, p-1 élű feszítőfa az aktuális komponensben, valamint v1 egy elsőfokú pont F-ben és e1 a hozzá illeszkedő él. Legyen v2 egy elsőfokú pont (F - { v1 })-ben és e2 a hozzá tartozó él stb. Ha a blokk sorait v1, v2... sorrendben soroljuk fel, oszlopait pedig e1, e2 sorrendben kezdjük, akkor egy p × (p-1) méretű részmátrixot kapunk, amely diagonális elemei ±1 értékűek és az átló felett csupa 0 áll. Így találtunk p-1 darab lineárisan független oszlopot, ezért a rang pontosan p-1.

Oszlopok lineáris függetlensége[szerkesztés | forrásszöveg szerkesztése]

Tétel: Ha az összefüggő, irányított, n pontú G gráf illeszkedési mátrixából kiválasztunk n - 1 oszlopot, akkor ezek akkor és csak akkor lineárisan függetlenek, ha a megfelelő n - 1 él G-nek egy fáját alkotja.

Bizonyítás: Az előbbi bizonyítás szerint, ha az élek fát alkotnak, akkor a megfelelő oszlopvektorok lineárisan függetlenek. Most megmutatjuk ennek fordítottját, hogy ha néhány él kört alkot, a megfelelő oszlopvektorok lineárisan összefüggők. Csakugyan, ezek az oszlopok és a kört alkotó pontoknak megfelelő sorok alkalmas sor- illetve oszloppermutációk után a következő mátrixot alkotják:

 \begin{pmatrix}
a & 0 & \dots & -x \\
-a & b & \dots & 0 \\
\vdots & \vdots & \ddots & \ddots \\
0 & 0 & \dots & x \\
\end{pmatrix},

ahol az a, b, ... , x betűk mindegyike +1 vagy -1. Most képezzük az oszlopvektoroknak azt a lineáris kombinációját, amiben az első oszlop együtthatója 1, ha a = 1 és -1, ha a = -1. A második oszlopé 1, ha b = 1 és -1, ha b = -1 stb.

Az első tételből az is következik, hogy a fáknak megfelelő p-1 oszlop és B bármely p-1 sora által alkotott mátrix determinánsa ± 1.

Feszítőfák száma[szerkesztés | forrásszöveg szerkesztése]

Tétel: Hagyjunk el az n pontú, összefüggő, irányított G gráf illeszkedési mátrixából egy tetszőleges sort. A keletkező B0 mátrixból képzett B0 · B0T mátrix determinánsa épp a G gráf feszítőfáinak száma.

Bizonyítás: Ebben a bizonyításban felhasználjuk Binet és Cauchy következő tételét:

Ha M egy p × r-es, N egy r × p-es mátrix (pr), akkor M · N determinánsa \textstyle \sum det(M_i) det(N_i), ahol M i az M alkalmas p darab oszlopából, N i pedig az ugyanilyen sorszámú soraiból áll, és az összegzés mind az \textstyle \binom{r}{p} -féle ilyen kiválasztásra történik. Például:

\left| \begin{pmatrix} a & b & c \\ d & e & f \\ \end{pmatrix}
\begin{pmatrix} g & h \\ i & j \\ k & l \end{pmatrix} \right| = \begin{vmatrix} a & b \\ d & e \end{vmatrix}\begin{vmatrix} g & h \\ i & j \end{vmatrix}+\begin{vmatrix} a & c \\ d & f \end{vmatrix}\begin{vmatrix} g & h \\ k & l \end{vmatrix}+\begin{vmatrix} b & c \\ e & f \end{vmatrix}\begin{vmatrix} i & j \\ k & l \end{vmatrix} .

Ezek után a tétel állítása nyilvánvaló: B0-ból mindenféleképp kiválasztva n - 1 oszlopot, éppen a fának megfelelő részmátrixok determinánsa lesz 0-tól különböző. Az előző tétel végén említettek szerint ekkor ez a determináns ± 1. Felhasználtuk, hogy B0T megfelelő részmátrixa épp a B0 vizsgált részmátrixának transzponáltja, tehát determinánsaik egyenlők.

Cayley-formula[szerkesztés | forrásszöveg szerkesztése]

Az illeszkedési mátrix segítségével új bizonyítás adható Cayley tételére:

Tétel: Az n címkézett csúcson megadható fák száma nn-2.

Bizonyítás: Az előző, feszítőfák számára vonatkozó tétel felhasználásához nem szükséges a B0 mátrixot felírnunk. Az egyszerűség kedvéért tegyük fel, hogy B utolsó, vagyis n-edik sorát elhagyva kaptuk a B0 mátrixot. A mátrixszorzás tulajdonságából és B0 definíciójából következik, hogy B0 B0T = (di j) elemeit az alábbi képlet is előállítja:

d_{ij}=
\begin{cases}
\text{az }i\text{-edik pont foka,} & \text{ha } i=j\\
\text{az }i\text{-edik és }j\text{-edik pont között oda- és visszavezető élek számának (-1)-szerese,} & \text{ha } i \ne j.
\end{cases}

Így például az n pontú teljes gráfra

B_0 B_0^T =
\begin{pmatrix}
n-1 & -1 & \dots & -1 \\
-1 & n-1 & \dots & -1 \\
\vdots & \vdots & \ddots & \vdots \\
-1 & -1 & \dots & n-1
\end{pmatrix}.

Ennek determinánsa:


\begin{vmatrix}
1 & 1 & \dots & 1 \\
-1 & n-1 & \dots & -1 \\
\vdots & \vdots & \ddots & \vdots \\
-1 & -1 & \dots & n-1
\end{vmatrix} =
\begin{vmatrix}
1 & 1 & \dots & 1 \\
0 & n & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \dots & n
\end{vmatrix} = n^{n-2}.

Alkalmazás villamos hálózatokban[szerkesztés | forrásszöveg szerkesztése]

A Kirchhoff-féle áramegyenletek B·i = 0 alakba írhatók, melyben az i vektor elemei az alkatrészek áramai. Ha egy kétpólusú alkatrészekből álló villamos hálózatokra fel szeretnénk írni a Kirchhoff-féle áramegyenleteket, akkor n egyenletet kapnánk (minden pontra egyet). Az illeszkedési mátrix rangjára vonatkozó tétel miatt azonban ezek közül csak n-c darab lenne lineárisan független. A gyakorlatban emiatt a hálózat gráfjának minden összefüggő komponensében egy-egy pontot figyelmen kívül hagyunk az áramegyenletek felírásakor.

Irodalom[szerkesztés | forrásszöveg szerkesztése]

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]