Contracția muchiei
În teoria graficelor , o contracție a graficului este o operație care îndepărtează o margine dintr-un grafic în timp ce fuzionează simultan cele două vârfuri pe care le-a conectat anterior. Contracția marginilor este o operație fundamentală în teoria minorilor de grafice . Identificarea vertexului este o formă mai puțin restrictivă a acestei operațiuni.
Definiție
Operația de contracție a muchiei are loc în raport cu o anumită margine, e . Marginea e este eliminată și cele două vârfuri incidente ale sale, u și v , sunt îmbinate într-un nou vârf w , unde marginile incidente de pe w corespund fiecare cu o margine incidentă de pe u sau v .
Mai general, operația poate fi efectuată pe un set de muchii prin contractarea fiecărei muchii (în orice ordine). Contracțiile pot duce la un grafic cu mai multe bucle sau margini . Acestea sunt uneori șterse pentru a le menține în clasa simplă a graficelor .
Definiție formală
Fie G = ( V , E ) un grafic ( sau grafic direct ) care conține o margine și = ( u , v ) cu u ≠ v . Fie f o funcție care mapează fiecare nod din V \ {u, v} pentru sine sau mapează la un nou nod w. Contracția lui e are ca rezultat un nou grafic G ′ = ( V ′ , E ′ ), unde V ′ = ( V \ { u , v }) ∪ { w }, E ′ = E \ { e } și pentru fiecare x ∈ V , x ′ = f ( x ) ∈ V ′ este incident pe o margine și ′ ∈ E ′ dacă și numai dacă, muchia corespunzătoare și ∈ E , este incidentă pe x în G.
Identificarea vertexului
Identificarea vertexului (numită uneori contracție a vârfului ) elimină restricția conform căreia contracția trebuie să aibă loc pe vârfurile care au o margine incidentă. (Prin urmare, contracția muchiilor este un caz special de identificare a vârfurilor.) Operația poate avea loc pe orice pereche (sau subset) de vârfuri din grafic. Vârfurile dintre două vârfuri care se micșorează sunt uneori eliminate. Dacă v și v ' sunt vârfurile componentelor distincte ale lui G, atunci putem crea un nou grafic G' identificând v și v ' în G ca un nou vârf v în G'. [1]
Separarea vertexului
Separarea vârfurilor , care este aceeași cu împărțirea vârfurilor, înseamnă că un vârf separat în două, unde aceste două vârfuri noi sunt adiacente vârfurilor la care vârful inițial era la rândul său adiacent. Aceasta este operația inversă a identificării vârfurilor.
Contracția căii
Contracția căilor are loc pe setul de margini într-o cale care se contractă pentru a forma o singură margine între capetele căii. Marginile incidente pe vârfurile de-a lungul căii sunt fie eliminate, fie conectate arbitrar (sau sistematic) la una dintre extreme.
Răsucire
Având două grafuri disjuncte G1 și G2, unde G1 conține vârfurile u1 și v1 și G2 conține vârfurile u2 și v2 . Să presupunem că putem obține graficul G identificând vârfurile lui u1 u2 G1 și G2 ca vârful u al lui G și identificând vârfurile v1 și v2 de la G1 la G2 ca vârful v al lui G. Într-o torsiune (răsucire) G 'a G față de setul de vârfuri {u, v}, identificăm, în schimb, u1 cu v2 și v1 cu u2 . [2]
Aplicații
Atât tehnicile de contracție a muchiilor cât și a vârfurilor sunt valoroase în dovada inducției asupra numărului de vârfuri sau muchii dintr-un grafic, unde se poate presupune că o proprietate este valabilă pentru toate graficele mai mici și aceasta poate fi utilizată pentru a demonstra proprietatea pentru cel mai mare grafic.
Contracțiile sunt utile și în structuri în care dorim să simplificăm un grafic prin identificarea vârfurilor care reprezintă în esență entități echivalente. Unul dintre cele mai frecvente exemple este reducerea unui grafic direct general la un grafic aciclic direct prin contractarea tuturor vârfurilor din fiecare componentă puternic conectată . Dacă relația descrisă de grafic este tranzitivă , nu se pierd informații până când nu etichetăm fiecare vârf cu setul de etichete de vârf care au fost contractate pentru a-l forma.
Un alt exemplu este întâlnirea efectuată în alocarea registrelor de colorare globală a graficelor , în care vârfurile sunt contractate (acolo unde este sigur) pentru a elimina operațiile de deplasare între variabile distincte.
Contracția marginilor este utilizată în pachetele de modelare tridimensională (fie manual, fie prin intermediul unei caracteristici ale software-ului de modelare) pentru a reduce în mod constant numărul de vârfuri, ajutând la crearea modelelor cu poligon redus.
Notă
Elemente conexe
linkuri externe
- (EN) Eric W. Weisstein, Edge Contraction în MathWorld Wolfram Research.
