ciąg stopni grafu

muoda92 · Post autor: **muoda92** » 12 maja 2012, o 00:08

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?

Jacek_Karwatka · Post autor: **Jacek_Karwatka** » 12 maja 2012, o 07:51

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.

muoda92 · Post autor: **muoda92** » 12 maja 2012, o 11:01

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?

Jacek_Karwatka · Post autor: **Jacek_Karwatka** » 13 maja 2012, o 07:09

Tak. Te dwa grafy nie są izomorficzne, mimo iż oba mogą być opisane tym samy ciągiem stopni odpowiednich wierzchołków.