Homeomorfism (teoria graficelor)
Se spune că două grafice G și H sunt homeomorfe dacă și numai dacă există un izomorfism între cele două subdiviziuni ale muchiilor lor G 'și H'.
În mod echivalent, două grafice G și H pot fi definite ca homeomorfe dacă și numai dacă pot fi obținute din același grafic K prin intermediul a două secvențe (finite) de subdiviziuni elementare ale muchiilor.
Premisă
Pentru subdiviziunea elementară a muchiilor unui grafic se referă la o operație care modifică o margine {u, v} în două margini {u, w} și {w, v} accidente într-un nou vârf w. Această operațiune poate fi descrisă și ca inserarea unui nou nod într-o margine.
Prin subdiviziune a muchiilor unui grafic înțelegem atât operația constând din una sau mai multe subdiviziuni elementare, cât și graficul obținut cu această manevră.
Exemplu
Să examinăm următoarele două grafice pentru a vedea că sunt homeomorfe.
G. 
H. 
Numim G 'graficul obținut din G prin împărțirea fiecărei margini având un vârf de grad 2 (muchii „exterioare”) și H' graficul obținut de H prin împărțirea muchiei sale având cele două extreme de grad 3 („internă”) margine). Aceste două grafice au aceeași reprezentare:
G ', H' 
Prin urmare, evident, există un izomorfism între G 'și H' (de fapt există două) și, în consecință, pentru a doua dintre definițiile date, G și H sunt homeomorfe.
Să luăm în considerare a doua definiție echivalentă. Eliminând din G singurul vârf de gradul 2 și din H patru dintre vârfurile sale de grad 2 alese astfel încât să mențină caracterul unui grafic simplu , identificăm un grafic K cu două vârfuri de grad 3 și două de grad 2, din pe care le putem obține prin subdiviziune graficele G și H. Tot astfel putem afirma deci homeomorfismul dintre G și H.
Considerare complexitate
Având în vedere două grafice G și H, apare problema determinării dacă H este homeomorf pentru un subgraf al lui G. O astfel de problemă se dovedește a fi NP-completă .
Bibliografie
- Jay Yellen, Jonatan L. Gross: Teoria graficelor și aplicațiile sale, Chapman & Hall / CRC, (2005) ediția a II-a, ISBN 978-1-58488-505-4
