Homeomorfism (grafteori) - Homeomorphism (graph theory)

I grafteori , två grafer och är homeomorfa om det finns en graf isomorfism från någon underavdelning av till någon underindelning av . Om kanterna på ett diagram betraktas som linjer som dras från ett toppunkt till ett annat (som de vanligtvis avbildas i illustrationer), är två grafer homeomorfa till varandra i grafteoretisk mening exakt om de är homeomorfa i den mening som termen används i topologi . ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle G}$ ${\ displaystyle G '}$

Underindelning och utjämning

I allmänhet, en underavdelning av en graf G (ibland känd som en expansions är) ett diagram som resulterar från uppdelning av kanter i G . Underindelningen av någon kant e med slutpunkter { u , v } ger ett diagram som innehåller ett nytt toppunkt w och med en kantuppsättning som ersätter e med två nya kanter, { u , w } och { w , v }.

Till exempel kanten e , med slutpunkter { u , v }:

kan delas in i två kanter, e ₁ och e ₂ , som ansluter till ett nytt toppunkt w :

Den omvända operationen, utjämning eller utjämning av ett toppunkt w med avseende på paret av kanter ( e ₁ , e ₂ ) infallande på w , tar bort båda kanterna som innehåller w och ersätter ( e ₁ , e ₂ ) med en ny kant som förbinder andra slutpunkter i paret. Här betonas att endast grad-två (dvs. 2-valenta) toppar kan utjämnas.

Till exempel det enkla anslutna diagrammet med två kanter, e ₁ { u , w } och e ₂ { w , v }:

har ett toppunkt (nämligen w ) som kan utjämnas, vilket resulterar i:

Att bestämma huruvida för graferna G och H är H homeomorf till en delgraf av G , är ett NP-komplett problem.

Barycentric underindelningar

Den barycentriska indelningen delar upp varje kant i diagrammet. Detta är en särskild indelning, eftersom det alltid resulterar i en bipartitgraf . Denna procedur kan upprepas, så att n ^{: te} barycentriska indelning är den barycentriska uppdelning av n -1 ^e barycentriska uppdelning av grafen. Den andra sådan underindelningen är alltid ett enkelt diagram .

Bädda in på en yta

Det är uppenbart att uppdelning av ett diagram bevarar planariteten. Kuratowskis sats säger att

en ändlig graf är plan om och endast om den inte innehåller något subgrafiskt homomorf till K ₅ ( komplett diagram på fem hörn ) eller K _3,3 ( komplett bipartit-diagram på sex hörn, varav tre ansluter till var och en av de andra tre).

I själva verket kallas en graf som är hemomorf till K ₅ eller K _3,3 en Kuratowski-subgraf .

En generalisering, som följer av Robertson – Seymour-satsen , hävdar att det för varje heltal g finns en ändlig hinderuppsättning av grafer så att en graf H är inbäddad på en yta av släktet g om och endast om H inte innehåller någon homeomorf kopia av någon av . Består till exempel av Kuratowski-underbilderna. ${\ displaystyle L (g) = \ left \ {G_ {i} ^ {(g)} \ right \}}$ ${\ displaystyle G_ {i} ^ {(g)}}$ ${\ displaystyle L (0) = \ left \ {K_ {5}, K_ {3,3} \ right \}}$

Exempel

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

Diagram G

Diagram H

Om G ' är diagrammet som skapats genom indelning av ytterkanterna på G och H' är grafen som skapas genom indelning av den inre kanten av H , då har G ' och H' en liknande grafritning:

Diagram G ' , H'

Därför finns det en isomorfism mellan G ' och H' , vilket betyder att G och H är homeomorfa.

Se även

Referenser

^ Archdeacon, Dan (1996), "Topological graph theory: a survey", Surveys in graph theory (San Francisco, CA, 1995) , Congressus Numerantium, 115 , s. 5–54, MR 1411236 , Namnet uppstår på grund av och är homeomorf som diagram om och bara om de är homeomorfa som topologiska utrymmen ${\ displaystyle G}$ ${\ displaystyle H}$
^ Trudeau, Richard J. (1993). Introduktion till grafteori (Korrigerad, utvidgad republikering. Red.). New York: Dover Pub. sid. 76. ISBN 978-0-486-67870-2. Hämtad 8 augusti 2012 . Definition 20. Om några nya hörn av grad 2 sättes till en del av kanterna på en graf G , den resulterande grafen H kallas en utvidgning av G .
^ Den mer allmänt studerade problem i litteraturen, under namnet av subgraf homeomorfi problemet, är om en underindelning av H är isomorf med en subgraf av G . Fallet när H är en n- vertikal cykel motsvarar Hamilton-cykelproblemet och är därför NP-komplett. Emellertid är denna formulering endast ekvivalent med frågan om huruvida H är homeomorfa till en subgraf av G när H har inga grad-två hörn, eftersom det inte tillåter utjämning i H . Det angivna problemet kan visas vara NP-komplett genom en liten modifiering av Hamilton-cykelreduktionen: lägg till ett toppunkt till var och en av H och G , intill alla andra hörn. Såledesinnehållerförstoringsförstärkningen av en graf G en subgraf hemomorf till en ( n + 1) -vertex hjulgraf , om och bara om G är Hamilton. För hårdheten i subgrafhomomorfismproblemet, se t.ex. LaPaugh, Andrea S .; Rivest, Ronald L. (1980), "The subgraph homeomorphism problem", Journal of Computer and System Sciences , 20 (2): 133–149, doi : 10.1016 / 0022-0000 (80) 90057-4 , MR 0574589.

Vidare läsning

Yellen, Jay; Gross, Jonathan L. (2005), Grafteori och dess tillämpningar , diskret matematik och dess tillämpningar (2: a upplagan), Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-505-4

[1] Archdeacon, Dan (1996), "Topological graph theory: a survey", Surveys in graph theory (San Francisco, CA, 1995) , Congressus Numerantium, 115 , s. 5–54, MR 1411236 , Namnet uppstår på grund av och är homeomorf som diagram om och bara om de är homeomorfa som topologiska utrymmen ${\ displaystyle G}$ ${\ displaystyle H}$

[2] Trudeau, Richard J. (1993). Introduktion till grafteori (Korrigerad, utvidgad republikering. Red.). New York: Dover Pub. sid. 76. ISBN 978-0-486-67870-2. Hämtad 8 augusti 2012 . Definition 20. Om några nya hörn av grad 2 sättes till en del av kanterna på en graf G , den resulterande grafen H kallas en utvidgning av G .

[3] Den mer allmänt studerade problem i litteraturen, under namnet av subgraf homeomorfi problemet, är om en underindelning av H är isomorf med en subgraf av G . Fallet när H är en n- vertikal cykel motsvarar Hamilton-cykelproblemet och är därför NP-komplett. Emellertid är denna formulering endast ekvivalent med frågan om huruvida H är homeomorfa till en subgraf av G när H har inga grad-två hörn, eftersom det inte tillåter utjämning i H . Det angivna problemet kan visas vara NP-komplett genom en liten modifiering av Hamilton-cykelreduktionen: lägg till ett toppunkt till var och en av H och G , intill alla andra hörn. Såledesinnehållerförstoringsförstärkningen av en graf G en subgraf hemomorf till en ( n + 1) -vertex hjulgraf , om och bara om G är Hamilton. För hårdheten i subgrafhomomorfismproblemet, se t.ex. LaPaugh, Andrea S .; Rivest, Ronald L. (1980), "The subgraph homeomorphism problem", Journal of Computer and System Sciences , 20 (2): 133–149, doi : 10.1016 / 0022-0000 (80) 90057-4 , MR 0574589.

Languages

In other projects