În teoria grafurilor, contracția muchiei este o operație care elimină o muchie din graf și, înainte de aceasta, vârfurile conectate de muchie se îmbină într-un singur vârf. Contracția marginilor este o operație fundamentală în teoria grafurilor minore . Identificarea vârfurilor este o altă formă a acestei operațiuni cu restricții mai slabe.
Operația de contracție a muchiei se realizează pe o anumită muchie e . Muchia e este îndepărtată și cele două vârfuri incidente ale sale, u și v , sunt îmbinate într-un nou vârf w , unde muchiile incidente cu w corespund muchiilor incidente fie cu u , fie cu v . Mai general, o operație poate fi efectuată pe un set de muchii prin scăderea muchiilor din mulțime (în orice ordine) [1] .
După cum este definit mai jos, o operație de contracție a muchiilor poate produce un grafic cu muchii multiple chiar dacă graficul original a fost un grafic simplu [2] . Cu toate acestea, unii autori [3] nu permit crearea de muchii multiple, cu o astfel de restricție, muchiile contractante pe un graf simplu dă întotdeauna grafice simple.
Fie G =( V , E ) un grafic ( sau grafic direcționat ) care conține o muchie e =( u , v ) cu u ≠ v . Fie f o funcție care mapează orice vârf din V \{ u , v } la sine și, în caz contrar, la w . Contracția lui e conduce la un nou grafic G′ =( V′ , E′ ), unde V′ =( V \{ u , v })∪{ w }, E′ = E \{ e } și pentru orice vârf x ∈ V , un vârf x′ = f ( x )∈ V′ este incident cu o muchie e′ ∈ E′ dacă și numai dacă muchia corespunzătoare e ∈ E este incidentă cu x în G .
Potrivirea vârfurilor (uneori numită micșorare a vârfurilor ) nu folosește constrângerea conform căreia micșorarea trebuie făcută cu vârfuri incidente la aceeași muchie (astfel, micșorarea muchiei este un caz special de potrivire a vârfurilor). Această operație poate fi efectuată pe orice pereche (sau subset) de vârfuri din grafic. Muchiile dintre două vârfuri contractate sunt uneori eliminate. Dacă v și v' sunt vârfuri ale diferitelor componente ale lui G, atunci putem crea un nou graf G' identificând v și v' în G la un nou vârf v în G' [4] .
Împărțirea vârfurilor înseamnă înlocuirea unui vârf cu două, iar aceste două noi vârfuri sunt adiacente vârfurilor care erau adiacente vârfului original. Operația este inversul identificării vârfurilor.
Contracția traseului se face cu mai multe muchii din cale care se contractă pentru a forma o singură muchie între vârfurile de capăt ale căii. Muchiile incidente la vârfuri de-a lungul căii sunt fie excluse, fie aleatoriu (sau conform unui sistem) conectate la unul dintre punctele finale.
Având în vedere două grafice disjunse G 1 și G 2 , unde G 1 conține vârfurile u 1 și v 1 , iar G 2 conține vârfurile u 2 și v 2 . Să presupunem că am obținut un grafic G identificând vârfurile u 1 ale graficului G 1 și u 2 ale graficului G 2 , obținând un vârf u în G și identificând vârfurile v 1 ale graficului G 1 și v 2 ale graficului G 2 , obținând un vârf v în G. În răsucirea G’ a graficului G față de perechea de vârfuri {u, v}, identificăm în locul vârfurilor de mai sus u 1 cu v 2 și v 1 cu u 2 [5] .
Atât contracția marginilor, cât și contracția vârfurilor sunt importante pentru demonstrarea prin inducție matematică a numărului de vârfuri sau muchii ale unui grafic, unde se poate presupune că o proprietate este valabilă pentru toate graficele mai mici și aceasta poate fi folosită pentru a demonstra proprietățile graficelor mai mari.
Contracția marginilor este utilizată în formula recursivă pentru numărul de arbori contractați ai unui graf conex aleatoriu [1] și în formula recursivă pentru polinomul cromatic al unui graf simplu [6] .
Contracția este utilă și în structurile în care dorim să simplificăm graficul prin identificarea vârfurilor care reprezintă obiecte substanțial echivalente. Cel mai cunoscut exemplu este reducerea unui graf general direcționat la un graf aciclic direcționat prin contractarea tuturor vârfurilor din fiecare componentă puternic conectată . Dacă relația descrisă de grafic este tranzitivă , nu se pierde nicio informație prin etichetarea fiecărui vârf cu setul de etichete de vârf care au fost contractate la acel vârf.
Un alt exemplu este îmbinarea efectuată într- un grafic colorat sub alocare globală de registru , unde vârfurile sunt îmbinate (acolo unde este posibil) pentru a evita mutarea datelor între diferite variabile.
Contracția marginilor este utilizată în pachetele de modelare 3D (fie manual, fie cu simulatoare) pentru a reduce progresiv numărul de vârfuri pentru a crea modele poligonale cu un număr mic de laturi.