Grafy homomorficzne

[K4M1L]

Podać przykład nieizomorficznych grafów G i H, dla których istnieją homomorfizmy \(\displaystyle{ f: G \rightarrow H}\) oraz \(\displaystyle{ k: H \rightarrow G}\)

[Gosda]

Niech \(\displaystyle{ V = X \cup Y}\) będzie sumą dwóch nieskończonych zbiorów \(\displaystyle{ X, Y}\). W grafie \(\displaystyle{ G}\) każde dwa wierzchołki są połączone, chyba że oba końce należą do zbioru \(\displaystyle{ Y}\). W grafie \(\displaystyle{ H}\) mamy te same krawędzie i jeszcze jedną między dwoma wybranymi wierzchołkami ze zbioru \(\displaystyle{ Y}\).

Grafy nie są izomorficzne, w pierwszym z nich jeśli dwa wierzchołki sąsiadują ze sobą, to przynajmniej jeden z nich sąsiaduje ze wszystkimi innymi. Drugi graf nie ma tej własności. Wskazanie homomorfizmów pozostawiam Tobie.

[arek1357]

A co to jest V? i jak się on ma do G i H brak wyjaśnienia...

[Gosda]

\(\displaystyle{ V}\) to standardowe oznaczenie na zbiór wierzchołków grafu, w tym rozwiązaniu zarówno dla \(\displaystyle{ G}\) jak i \(\displaystyle{ H}\). Z angielskiego vertices.