Vágásmátrix

A matematikában a vágásmátrix egy gráfelméleti mátrixreprezentáció. A körmátrixhoz hasonlóan definiálhatjuk a vágásmátrixot is, csak itt nem a kör, hanem a vágás irányítását definiáljuk. A valóságban a vágásmátrix nem alkalmas egy gráf reprezentálására, mert nem izomorf gráfoknak lehet azonos vágásmátrixa és tárolása is helyigényesebb, mint például egy szomszédossági listának.

Definíció

Egy vágást alkotó élek a gráf ugyanazon komponensében vannak és ezen komponens pontjait választják szét X₁ és X₂ részhalmazra. A vágás egy (u,v) élének irányítása akkor egyezik meg a vágás irányításával, ha u ∈ X₁ és v ∈ X₂. Fordított esetben ellentétes az irányításuk. Így a Q(G) vágásmátrix (q _{i j}) elemének a körmátrixhoz hasonló definíciója:

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

Példa egy gráf vágásmátrixára

Irányított gráf	Vágásmátrix
	${\begin{pmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&1&0&0&-1&0\\0&0&0&0&-1&1&-1&0\\0&0&1&1&1&-1&0&0\\\end{pmatrix}}$

Kapcsolat egyes mátrixreprezentációk között

Tétel: Ha B, C, Q rendre egy hurokélmentes irányított gráf illeszkedési, kör- és vágásmátrixa és oszlopaik ugyanabban a sorrendben vannak, akkor

$\textstyle B\cdot C^{T}=\mathbf {0}$ és $\textstyle Q\cdot C^{T}=\mathbf {0} .$

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
• Körmátrix
• Szomszédsági mátrix