ciąg stopni grafu
ciąg stopni grafu
Czy ciąg stopni grafu pierwszego np (1,1,1,4) jest różny od ciągu stopni grafu drugiego np (1,1,4,1)? Czy ma znaczenie zamiana wierzchołków (np samego oznaczenia) w moim przypadku v4 na v3 , czy interesują nas tylko ogólnie jakie stopnie występują w grafie?
-
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
ciąg stopni grafu
To zależy od kontekstu i stosowanej definicji izomorfizmu (przystania) grafów.
Na ogól grafy które powstają z innych tylko poprzez zmianę oznaczeń wierzchołków są traktowane jako izomorficzne. W tym wypadku oba ciągi opisują (ściślej mogą opisywać) ten sam graf.
Uwaga
Przedstawiony ciąg nie może być ciągiem rzeczywistego grafu. Suma stopni wierzchołków grafu jest zawsze parzysta.
Grafy które nie są izomorficzne mogą być opisane tym samym ciągiem stopni wierzchołków grafu. Z tego że odpowiednie wierzchołki w dwóch grafach mają takie same stopnie nie wynika że to są te same grafy.
Na ogól grafy które powstają z innych tylko poprzez zmianę oznaczeń wierzchołków są traktowane jako izomorficzne. W tym wypadku oba ciągi opisują (ściślej mogą opisywać) ten sam graf.
Uwaga
Przedstawiony ciąg nie może być ciągiem rzeczywistego grafu. Suma stopni wierzchołków grafu jest zawsze parzysta.
Grafy które nie są izomorficzne mogą być opisane tym samym ciągiem stopni wierzchołków grafu. Z tego że odpowiednie wierzchołki w dwóch grafach mają takie same stopnie nie wynika że to są te same grafy.
ciąg stopni grafu
No tak, jasne, nie może być to ciąg rzeczywistego grafu, nie zwróciłam uwagi
więc czy mogę powiedzieć, że te grafy mają ten sam ciąg stopni ale są nieizomorficzne?
więc czy mogę powiedzieć, że te grafy mają ten sam ciąg stopni ale są nieizomorficzne?
-
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
ciąg stopni grafu
Tak. Te dwa grafy nie są izomorficzne, mimo iż oba mogą być opisane tym samy ciągiem stopni odpowiednich wierzchołków.