Homeomorfizm grafów.html



Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Homeomorfizm grafów – relacja równoważności w zbiorze grafów, wiążąca grafy jednokształtne.

Intuicyjnie graf homeomorficzny do grafu G otrzymuje się przez "rozerwanie" krawędzi i "wstawienie pomiędzy nie" nowego wierzchołka. Proces ten może zostać powtórzony dowolną ilość razy, tzw. początkowa krawędź może być zastępowana coraz dłuższą ścieżką utworzoną z nowych wierzchołków i "kawałków" starej krawędzi.

Dwa grafy G₁ i G₂ są homeomorficzne, jeśli można je oba otrzymać z pewnego grafu G przez zastępowanie krawędzi grafu łańcuchami prostymi.

Inaczej: grafy G₁ i G₂ są homeomorficzne, jeśli można otrzymać z grafu G₁ graf G₂ zastępując wybrane krawędzie łańcuchami prostymi lub łańcuchy proste pojedynczymi krawędziami.

Zobacz też: teoria grafów