Graficul homeomorfismului

Două grafice și sunt homeomorfe dacă există un izomorfism al unei subdiviziuni a graficului și al unei subdiviziuni a graficului [1] . Dacă muchiile unui graf sunt înțelese ca segmente care leagă vârfuri (așa cum este de obicei desenat în ilustrații), atunci două grafuri sunt homeomorfe în contextul teoriei grafurilor atunci când sunt homeomorfe în sens topologic .

Subdiviziunea și excluderea

În general, o subdiviziune a unui graf G (uneori se folosește termenul extensie [2] sau subdiviziune ) este un graf obținut prin împărțirea muchiilor în G . Împărțirea unei muchii e cu vârfuri finale { u , v } dă un grafic care conține un nou vârf w și două muchii { u , w } și { w , v } în loc de muchia e [1] .

De exemplu, muchia e cu capete { u , v }:

poate fi împărțit în două muchii, e 1 și e 2 :

Operația inversă, eliminând vârful w cu muchii incidente cu acesta ( e 1 , e 2 ), înlocuiește ambele muchii adiacente vârfului w ( e 1 , e 2 ) cu o nouă muchie care conectează punctele terminale ale perechii. Trebuie subliniat că această operație este aplicabilă numai vârfurilor care sunt incidente cu exact două muchii.

De exemplu, un grafic conex simplu cu două muchii e 1 { u , w } și e 2 { w , v }:

are un vârf (numit w ) care poate fi exclus, rezultând:

Determinarea dacă un graf H este homeomorf unui subgraf G este o problemă NP-completă [3] .

Subdiviziuni baricentrice

Subdiviziunea baricentrică împarte fiecare margine a graficului. Acesta este un tip special de subdiviziune care oferă întotdeauna un graf bipartit . Această procedură poate fi repetată astfel încât a n- a subdiviziune baricentrică să fie subdiviziunea baricentrică a subdiviziunii n-1 . A doua astfel de diviziune este întotdeauna un grafic simplu .

Încorporarea într-o suprafață

Este evident că subdiviziunea graficului păstrează planaritatea. Teorema Pontriagin-Kuratovsky afirmă că

un graf finit este plan dacă și numai dacă nu conține un subgraf homeomorf la K 5 ( graf complet cu cinci vârfuri ) sau K 3,3 ( graf complet bipartit cu șase vârfuri, dintre care trei sunt conectate la fiecare dintre celelalte vârfuri). Trei).

De fapt, un grafic homeomorf la K 5 sau K 3,3 se numește subgraf Kuratowski .

Generalizarea care urmează din teorema Robertson-Seymour afirmă că pentru orice număr întreg g există un set finit obstructiv de grafice , astfel încât graficul H este înglobat într-o suprafață de genul g dacă și numai dacă H nu conține o copie homeomorfă a unui grafic. . De exemplu, este format din subgrafe Kuratovsky.

Exemplu

În exemplul următor, graficele G și H sunt homeomorfe.

G H

Dacă graficul G' este creat prin subdivizarea muchiilor exterioare ale graficului G, iar graficul H' este creat prin subdivizarea muchiilor interioare ale graficului H, atunci G' și H' au reprezentări grafice similare:

G', H'

Astfel, există un izomorfism între graficele G’ și H’, ceea ce înseamnă că G și H sunt homeomorfe.

Vezi și

Note

  1. ↑ 1 2 Yablonsky, 1986 , p. 225.
  2. ↑ Trudeau, 1993 , p. 76, Definiția 20.
  3. ↑ O problemă mai studiată în literatură numită „problema homeomorfismului subgrafului” se întreabă dacă o subdiviziune a unui graf H este izomorfă cu un subgraf G . Dacă H este un ciclu cu n vârfuri, problema este echivalentă cu găsirea unui ciclu hamiltonian și, prin urmare, este NP-complet. Cu toate acestea, această formulare este echivalentă doar cu întrebarea dacă un grafic H este homeomorf cu un subgraf G atunci când H nu conține vârfuri de gradul doi, deoarece acest lucru nu permite o excepție în H. Se poate demonstra că problema dată este NP-completă modificând ușor ciclul hamiltonian - adăugăm câte un vârf în H și G adiacent tuturor celorlalte vârfuri. Atunci graficul G mărit cu un vârf conține un subgraf homeomorf la o roată cu ( n  + 1) vârfuri dacă și numai dacă G este hamiltonian. Pentru complexitatea problemei homeomorfismului subgrafului, a se vedea lucrarea lui LaPaugh și Rivest ( LaPaugh, Rivest 1980 ).

Literatură