I grafteori er kantkontraktion en operation , der fjerner en kant fra grafen, og før det smelter de hjørner, der er forbundet med kanten, sammen i et toppunkt. Kantsammentrækning er en grundlæggende operation i grafisk mindre teori . Vertex-identifikation er en anden form for denne operation med svagere restriktioner.
Kantkontraktionsoperationen udføres på en specifik kant f.eks . Kanten e fjernes, og dens to indfaldende toppunkter, u og v , slås sammen til et nyt toppunkt w , hvor kanter, der falder ind med w, svarer til kanter, der falder ind med enten u eller v . Mere generelt kan en operation udføres på et sæt kanter ved at trække kanter fra sættet (i vilkårlig rækkefølge) [1] .
Som defineret nedenfor kan en kantkontraktionsoperation producere en graf med flere kanter , selvom den oprindelige graf var en simpel graf [2] . Nogle forfattere [3] tillader dog ikke oprettelsen af flere kanter, med en sådan begrænsning giver kontraherende kanter på en simpel graf altid simple grafer.
Lad G =( V , E ) være en graf ( eller rettet graf ) indeholdende en kant e =( u , v ) med u ≠ v . Lad f være en funktion, der afbilder et hvilket som helst toppunkt i V \{ u , v } til sig selv og ellers til w . Sammentrækningen af e fører til en ny graf G′ =( V′ , E′ ), hvor V′ =( V \{ u , v })∪{ w }, E′ = E \{ e }, og for evt. toppunkt x ∈ V , et toppunkt x′ = f ( x )∈ V′ falder ind på en kant e′ ∈ E′ hvis og kun hvis den tilsvarende kant e ∈ E falder ind med x i G .
Vertex-tilpasning (nogle gange kaldet vertex-krympning ) bruger ikke den begrænsning, at krympning skal udføres med toppunkter, der falder ind på den samme kant (således er kantkrympning et særligt tilfælde af toppunkt-tilpasning). Denne operation kan udføres på ethvert par (eller undersæt) af hjørner i grafen. Kanter mellem to sammentrukne hjørner fjernes nogle gange. Hvis v og v' er hjørner af forskellige komponenter af G, så kan vi skabe en ny graf G' ved at identificere v og v' i G til et nyt toppunkt v i G' [4] .
At opdele toppunkter betyder at erstatte et toppunkt med to, og disse to nye toppunkter støder op til de toppunkter, der stødte op til det oprindelige toppunkt. Operationen er det modsatte af at identificere knudepunkter.
Banesammentrækning udføres med flere kanter i stien , der trækker sig sammen for at danne en enkelt kant mellem stiens endespidser. Kanter, der falder ind på hjørner langs stien, er enten udelukket eller tilfældigt (eller i henhold til et system) forbundet til et af endepunkterne.
Givet to usammenhængende grafer G 1 og G 2 , hvor G 1 indeholder toppunkterne u 1 og v 1 , og G 2 indeholder toppunkterne u 2 og v 2 . Lad os antage, at vi har opnået en graf G ved at identificere toppunkter u 1 på graf G 1 og u 2 på graf G 2 , opnå et toppunkt u i G og identificere toppunkter v 1 på graf G 1 og v 2 på graf G 2 , opnåelse af et toppunkt v i G. Ved at vride G' af grafen G i forhold til parret af toppunkter {u, v} identificerer vi i stedet for ovenstående toppunkter u 1 med v 2 og v 1 med u 2 [5] .
Både kantkontraktion og toppunktkontraktion er vigtige for at bevise ved matematisk induktion på antallet af toppunkter eller kanter på en graf, hvor en egenskab kan antages at holde for alle mindre grafer, og denne kan bruges til at bevise egenskaber for større grafer.
Kantkontraktion bruges i den rekursive formel for antallet af kontraherende træer i en tilfældigt forbundet graf [1] og i den rekursive formel for det kromatiske polynomium i en simpel graf [6] .
Kontraktion er også nyttig i strukturer, hvor vi ønsker at forenkle grafen ved at identificere hjørner, der repræsenterer i det væsentlige ækvivalente objekter. Det bedst kendte eksempel er reduktionen af en generel rettet graf til en rettet acyklisk graf ved at kontrahere alle hjørner i hver stærkt forbundne komponent . Hvis relationen beskrevet af grafen er transitiv , går der ingen information tabt ved at mærke hvert toppunkt med det sæt af toppunktsetiketter, der er blevet kontraheret til det toppunkt.
Et andet eksempel er sammenfletningen udført i en graffarvning under global registerallokering , hvor toppunkter flettes (hvor det er muligt) for at undgå at flytte data mellem forskellige variable.
Kantkontraktion bruges i 3D-modelleringspakker (enten manuelt eller med simulatorer) for gradvist at reducere antallet af hjørner for at skabe polygonale modeller med et lille antal sider.