A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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ő:
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
Címkézett gráf | Illeszkedési mátrix |
---|---|
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 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
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:
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ő 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 (p ≤ r), akkor M · N determinánsa , 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 -féle ilyen kiválasztásra történik. Például:
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
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:
Így például az n pontú teljes gráfra
Ennek determinánsa:
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
Külső hivatkozások
Lásd még
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.