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{array}{cc}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{array}$

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

Irányított gráf	Vágásmátrix
	$\left(\begin{array}{cccccccc}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{array}\right)$

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

$B\cdot C^T=\mathrm{𝟎}$ és $Q\cdot C^T=\mathrm{𝟎}.$

Irodalom

• Katona Gyula Y.-Recski András-Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, 2006 Sablon:ISBN
• 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