Grafy homomorficzne
Grafy homomorficzne
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
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Grafy homomorficzne
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.
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.
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Grafy homomorficzne
\(\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.