Grafy homomorficzne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
K4M1L
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 10 cze 2019, o 17:31
Płeć: Mężczyzna
Podziękował: 5 razy

Grafy homomorficzne

Post autor: K4M1L » 30 lis 2019, o 22:45

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}\)

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 178
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 25 razy
Pomógł: 25 razy

Re: Grafy homomorficzne

Post autor: Gosda » 1 gru 2019, o 21:57

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.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3759
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 87 razy
Pomógł: 367 razy

Re: Grafy homomorficzne

Post autor: arek1357 » 2 gru 2019, o 10:52

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

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 178
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 25 razy
Pomógł: 25 razy

Re: Grafy homomorficzne

Post autor: Gosda » 2 gru 2019, o 17:19

\(\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.

ODPOWIEDZ