Graf homeomorfism

Två grafer och är homeomorfa om det finns en isomorfism av någon underavdelning av grafen och någon underavdelning av grafen [1] . Om kanterna på en graf förstås som segment som förbinder hörn (som vanligtvis ritas i illustrationer), så är två grafer homeomorfa i grafteorisammanhang när de är homeomorfa i topologisk mening.

Indelning och uteslutning

I allmänhet är en underavdelning av en graf G (ibland används termen förlängning [2] eller underavdelning ) en graf som erhålls genom att dividera kanter i G . Att dividera någon kant e med slutliga hörn { u , v } ger en graf som innehåller en ny vertex w och två kanter { u , w } och { w , v } istället för kant e [1] .

Till exempel kant e med ändarna { u , v }:

kan delas upp i två kanter, e 1 och e 2 :

Den omvända operationen, som eliminerar vertex w med kanter som faller in mot den ( e 1 , e 2 ), ersätter båda kanterna intill vertexen w ( e 1 , e 2 ) med en ny kant som förbinder parets ändpunkter. Det bör betonas att denna operation endast är tillämpbar på hörn som är infallande med exakt två kanter.

Till exempel, en enkel sammankopplad graf med två kanter e 1 { u , w } och e 2 { w , v }:

har en vertex (med namnet w ) som kan uteslutas, vilket resulterar i:

Att avgöra om en graf H är homeomorf till en subgraf G är ett NP-komplett problem [3] .

Barycentriska underavdelningar

Den barycentriska underindelningen delar upp varje kant av grafen. Detta är en speciell typ av underavdelning som alltid ger en tvådelad graf . Denna procedur kan upprepas så att den n :e barycentriska underavdelningen är den barycentriska underavdelningen av n-1 underavdelningen . Den andra indelningen är alltid en enkel graf .

Inbäddning i en yta

Det är uppenbart att underindelning av grafen bevarar planheten. Pontryagin-Kuratovsky-teoremet säger det

en finit graf är plan om och endast om den inte innehåller en subgraf som är homeomorf till K 5 ( komplett graf med fem hörn ), eller K 3,3 ( komplett tvådelad graf med sex hörn, varav tre är kopplade till var och en av de återstående tre).

Faktum är att en graf som är homeomorf till K 5 eller K 3,3 kallas en Kuratowski-subgraf .

Generaliseringen som följer av Robertson-Seymour- satsen säger att det för vilket heltal g som helst existerar en ändlig obstruktiv uppsättning grafer så att grafen H är inbäddbar i en yta av släktet g om och endast om H inte innehåller en kopia homeomorf till någon graf . Till exempel består den av Kuratovsky-undergrafer.

Exempel

I följande exempel är graferna G och H homeomorfa.

G H

Om grafen G' skapas genom att dela upp de yttre kanterna på grafen G, och grafen H' skapas genom att dela upp de inre kanterna på grafen H, så har G' och H' liknande grafiska representationer:

G', H'

Det finns alltså en isomorfism mellan graferna G' och H', vilket betyder att G och H är homeomorfa.

Se även

Anteckningar

  1. ↑ 1 2 Yablonsky, 1986 , sid. 225.
  2. ↑ Trudeau, 1993 , sid. 76, definition 20.
  3. ↑ Ett mer allmänt studerat problem i litteraturen som kallas "subgraph homeomorphism problem" frågar om en underavdelning av en graf H är isomorf till en subgraf G . Om H är en cykel med n hörn, är problemet likvärdigt med att hitta en Hamiltonsk cykel , och är därför NP-komplett. Denna formulering motsvarar dock bara att fråga om en graf H är homeomorf till en subgraf G när H inte innehåller hörn av grad två, eftersom detta inte tillåter ett undantag i H. Det kan visas att det givna problemet är NP-komplett genom att något modifiera Hamiltons cykel - vi lägger till en vertex vardera i H och G intill alla andra hörn. Då innehåller grafen G ökad med en vertex en subgraf som är homeomorf till ett hjul med ( n  + 1) hörn om och endast om G är Hamiltonsk. För komplexiteten i subgrafens homeomorfismproblem, se artikeln av LaPaugh och Rivest ( LaPaugh, Rivest 1980 ).

Litteratur