Illeszkedési mátrix

Az illeszkedési mátrix (ritkábban: incidenciamá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ó

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}}$

b_{i 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

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

Tételek

Illeszkedési mátrix rangja

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 v₁ egy elsőfokú pont F-ben és e₁ a hozzá illeszkedő él. Legyen v₂ egy elsőfokú pont (F - { v₁ })-ben és e₂ a hozzá tartozó él stb. Ha a blokk sorait v₁, v₂... sorrendben soroljuk fel, oszlopait pedig e₁, e₂ 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

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

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ő B₀ mátrixból képzett B₀ · B₀^T 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 (p ≤ r), 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ó: B₀-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 B₀^T megfelelő részmátrixa épp a B₀ vizsgált részmátrixának transzponáltja, tehát determinánsaik egyenlők.

Cayley-formula

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 n^n-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 B₀ mátrixot felírnunk. Az egyszerűség kedvéért tegyük fel, hogy B utolsó, vagyis n-edik sorát elhagyva kaptuk a B₀ mátrixot. A mátrixszorzás tulajdonságából és B₀ definíciójából következik, hogy B₀ B₀^T = (d_{i 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\neq 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

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

Katona Gyula Y.–Recski András–Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, 2006 ISBN 963-9664-19-7
Katona–Recski: Bevezetés a véges matematikába, ELTE jegyzet