Körmátrix

A matematika területén a gráfelméleten belül az egyik mátrixreprezentáció a körmátrix. Az illeszkedési mátrixhoz hasonlóan a körmátrixnak is hasznos alkalmazásai vannak a villamosságtanban. A valóságban a körmátrix nem alkalmas egy gráf reprezentálására, mert nem izomorf gráfoknak lehet azonos körmátrixa és tárolása is helyigényesebb, mint például egy szomszédossági listának.

Definíció

A körmátrixot úgy definiáljuk, hogy minden egyes kört körüljárunk, ekkor a C(G) mátrix c_{i j} eleme legyen a következő:

$c_{ij}={\begin{cases}0&{\text{ha a }}j{\text{-edik él nem eleme az }}i{\text{-edik körnek}}\\1&{\text{ha a }}j{\text{-edik él benne van az }}i{\text{-edik körben és irányítása megegyezik a kör körüljárásával}}\\-1&{\text{ha a }}j{\text{-edik él benne van az }}i{\text{-edik körben és irányítása ellentétes a kör körüljárásával}}\end{cases}}$

Példa egy gráf körmátrixára

Irányított gráf	Körmátrix
	${\begin{pmatrix}0&0&-1&1&0&0&0&0\\0&0&0&0&1&1&0&0\\0&0&1&0&-1&0&1&0\\0&0&1&0&0&1&1&0\\0&0&0&1&-1&0&1&0\\0&0&0&1&0&1&1&0\\0&0&0&0&0&0&0&1\\\end{pmatrix}}$

Tételek

A körmátrix esetében az illeszkedési mátrixhoz hasonló tételek érvényesek, melyeket összefüggő gráfokra mondunk ki:

Körmátrix rangja

Tétel: Az n csúcsú, e élű (összefüggő) irányított G gráf körmátrixának rangja: e - n + 1.

Oszlopok lineáris függetlensége

Tétel: Ha kiválasztunk az n csúcsú, e élű G gráf körmátrixából e - n + 1 oszlopot, ezek akkor és csak akkor lineárisan függetlenek, ha a megfelelő e - n + 1 él G egy fájának komplementerét alkotja.

Alkalmazás villamos hálózatokban

A Kirchhoff-féle feszültségegyenleteket a körmátrixszal C·u=0 alakba írhatjuk, ahol C a körmátrix és u az alkatrészek feszültségei. Az illeszkedési mátrixoknál a Kirchoff-féle egyenletek felírása egyszerűbb, mint a körmátrix esetében. Egy n pontú gráfban akár n! darab kör is megtalálható, és a rangról szóló fenti tétel megmutatja, hogy ha mindegyikre felírnánk egy feszültségegyenletet, akkor nagyon sok egyenlet adódna, amik a többi következményei. Ha a hálózat gráfja K₆ lenne, akkor a 165 feszültségegyenletből 150 felesleges lenne.

Alapkörrendszer

Ha egy összefüggő G gráf valamely F fájához minden lehetséges módon hozzáveszünk még egy további e ∉ F élt, akkor ( F ∪ {e} ) egyetlen C_e kört tartalmaz. Ezen körök együttesét az F fához tartozó alapkörrendszernek vagy fundamentális körrendszernek nevezzük. Mélységi bejárással - mélységi kereséssel ez egyszerűen megoldható (Depth-first search, DFS). A villamosmérnöki gyakorlatban valamely alapkörrendszer elemeihez érdemes felírni a Kirchhoff-féle feszültségtörvényeket.

Az F fához tartozó alapkörrendszer köreinek megfelelő sorvektorok és az F-hez nem tartozó éleknek megfelelő oszlopok C(G)-ben egy olyan (e - n + 1)×(e - n + 1) méretű négyzetes részmátrixot határoznak meg, mely a sorok és az oszlopok esetleges permutációi után az előjelektől eltekintve egységmátrix. Ebből adódik, hogy r(C) ≥ e - n + 1.

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

Kapcsolódó szócikkek

• Gráfelmélet
• Illeszkedési mátrix
• Vágásmátrix
• Szomszédsági mátrix