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 X1 és X2 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 ∈ X1 és v ∈ X2. 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:
Példa egy gráf vágásmátrixára
Irányított gráfVágásmátrix400px
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
és
Irodalom
Katona Gyula Y.-Recski András-Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, 2006 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
Kategória:Gráfelmélet