A gráfelméletben az élösszehúzódás egy olyan művelet , amely eltávolít egy élt a gráfból, és ezt megelőzően az él által összekapcsolt csúcsok egy csúcsba egyesülnek. Az élösszehúzódás a gráf-moll elmélet alapvető művelete . A csúcs azonosítása ennek a műveletnek egy másik formája gyengébb korlátozásokkal.
Az élösszehúzó műveletet egy adott élen hajtjuk végre e . Az e élt eltávolítjuk, és két beeső csúcsát, az u -t és a v -t egy új w csúcsba egyesítjük , ahol a w -vel beeső élek megfelelnek az u -val vagy v -vel beeső éleknek . Általánosabban fogalmazva, egy művelet végrehajtható egy élhalmazon úgy, hogy az éleket kivonjuk a halmazból (bármilyen sorrendben) [1] .
Az alábbiakban definiált módon egy élösszehúzó művelet több élű gráfot hozhat létre, még akkor is, ha az eredeti gráf egyszerű gráf volt [2] . Egyes szerzők [3] azonban nem teszik lehetővé több él létrehozását, ilyen megszorítás mellett az összehúzódó élek egy egyszerű gráfon mindig egyszerű gráfokat adnak.
Legyen G =( V , E ) egy gráf ( vagy irányított gráf ) , amely egy e = ( u , v ) élt tartalmaz u ≠ v . Legyen f olyan függvény, amely a V \{ u , v } bármely csúcsát önmagára képezi le, egyébként pedig w -re . Az e összehúzódása egy új G′ =( V′ , E′ ) gráfhoz vezet , ahol V′ =( V \{ u , v })∪{ w }, E′ = E \{ e }, és bármely x ∈ V csúcs , egy x′ = f ( x )∈ V′ csúcs akkor és csak akkor esik egy e′ ∈ E′ élre, ha a megfelelő e ∈ E él esik a G - beli x -re .
A csúcsillesztés (ezt néha csúcszsugorodásnak is nevezik ) nem alkalmazza azt a megkötést, hogy a zsugorítást ugyanazon élre eső csúcsokkal kell végrehajtani (tehát az élzsugorítás a csúcsillesztés speciális esete) . Ez a művelet elvégezhető a gráf bármely csúcspárján (vagy részhalmazán). A két összehúzott csúcs közötti éleket néha eltávolítják. Ha v és v' G különböző komponenseinek csúcsai, akkor létrehozhatunk egy új G' gráfot úgy, hogy g-ben v és v'-t azonosítunk egy új v csúcshoz G' -ben [4] .
A csúcsok felosztása azt jelenti, hogy egy csúcsot kettőre cserélünk, és ez a két új csúcs szomszédos azokkal a csúcsokkal, amelyek szomszédosak voltak az eredeti csúcsponttal. A művelet a csúcsok azonosításának fordítottja.
A pályaösszehúzódás több éllel történik az útvonalon , amelyek összehúzódnak , és egyetlen élt alkotnak az út végcsúcsai között. Az útvonal mentén a csúcsokra beeső élek vagy kizártak, vagy véletlenszerűen (vagy valamilyen rendszer szerint) kapcsolódnak valamelyik végponthoz.
Adott két G 1 és G 2 diszjunkt gráf , ahol G 1 az u 1 és v 1 csúcsokat , G 2 pedig az u 2 és v 2 csúcsokat tartalmazza . Tegyük fel, hogy G gráfot kaptunk úgy, hogy azonosítjuk a G 2 gráf G 1 és u 2 csúcsait , megkapjuk a G-beli u csúcsot, és azonosítjuk a G 1 gráf v 1 és v 2 csúcsait a G 2 gráfban . , kapunk egy v csúcsot G-ben. A G gráf G' elcsavarásakor az {u, v} csúcspárhoz képest a fenti u 1 csúcsok helyett v 2 -vel , v 1 pedig u 2 -vel azonosítjuk [5] .
Mind az élösszehúzódás, mind a csúcsösszehúzódás fontos a gráf csúcsainak vagy éleinek matematikai indukciós bizonyításához, ahol feltételezhető, hogy egy tulajdonság minden kisebb gráfra teljesül, és ez felhasználható nagyobb gráfok tulajdonságainak bizonyítására.
Az élösszehúzódást egy véletlenszerűen összefüggő gráf összehúzódó fáinak számának rekurzív képletében [1] és egy egyszerű gráf kromatikus polinomjának rekurzív képletében [6] használjuk .
Az összehúzódás olyan struktúrákban is hasznos, ahol a gráfot egyszerűsíteni akarjuk olyan csúcsok azonosításával, amelyek lényegében egyenértékű objektumokat képviselnek. A legismertebb példa egy általános irányított gráf redukálása irányított aciklikus gráfra úgy, hogy minden egyes erősen kapcsolódó komponensben összehúzzuk az összes csúcsot . Ha a gráf által leírt reláció tranzitív , akkor semmilyen információ nem vész el, ha minden csúcsot az adott csúcshoz összehúzott csúcscímkék halmazával címkézünk fel.
Egy másik példa a gráf színezésében végrehajtott egyesítés globális regiszter allokáció alatt , ahol a csúcsokat egyesítik (ahol lehetséges), hogy elkerüljék az adatok mozgatását a különböző változók között.
Az élösszehúzódást a 3D modellezési csomagokban használják (akár manuálisan, akár szimulátorokkal), hogy fokozatosan csökkentsék a csúcsok számát, hogy sokszögű modelleket hozzanak létre kevés oldallal.