W teorii wykres An skurcz krawędzi jest działanie na wykresie. Polega ona, obrazowo, na zawężeniu krawędzi wykresu, co sprowadza się do scalenia jego dwóch końców.
Ta operacja ma fundamentalne znaczenie dla teorii górników grafów i jest używana w niektórych algorytmach i niektórych dowodach.
Niech będzie grafem G = (V, E) , zawierającym krawędź (u, v) , przy czym u różni się od v . Skurcz (u, v), to operacja polegająca na transformacji G na wykresie G '= (V, E „) , gdzie v” jest równa V, z tym, że U i V są zastąpione przez unikalny wierzchołka wagowo , a E ' jest równe E z tą różnicą, że wystąpienia u i v są zastąpione przez w .
W zależności od obszaru zastosowania, pętle i wielokrotne wypukłości powstałe w wyniku skurczu są usuwane lub nie.
Karger 's algorytm dla min cięcia i Borůvka jest algorytm w minimalny ciężar drzewa rozpinającego użytkowania krawędzi skurczu.