Sprawdz czy ciąg jest graficzny

codi7123 · Post autor: **codi7123** » 16 sty 2012, o 15:19

Dla każdego z nastepujacych ciągów okresl czy jest graficzny, jezeli tak to podaj przyklad grafu prostego o takim ciagu stopni wierzcholkow:
a) (7,7,5,5,3,3,1,1)
B)(7,5,5,5,3,3,2,1,1,0)
C)(5,2,1,1)
czy ktos moglby mi wytlumaczyc dlaczego są bądź dlaczego nie są?? Z góry dziękuje za pomoc

arek1357 · Post autor: **arek1357** » 16 sty 2012, o 15:28

liczba wierzchołków o nieparzystym stopniu jest parzysta.

codi7123 · Post autor: **codi7123** » 16 sty 2012, o 15:31

tak to rozumiem, ale np w b) jeśli jest 0 to co wtedy?

arek1357 · Post autor: **arek1357** » 16 sty 2012, o 15:40

Zero to wierzchołek izolowany

codi7123 · Post autor: **codi7123** » 16 sty 2012, o 15:42

czyli a) jest graficzny, b) też. I tylko c) nie jest graficzny. Dobrze zrozumiałem?

Zordon · Post autor: **Zordon** » 16 sty 2012, o 15:43

arek1357 pisze:liczba wierzchołków o nieparzystym stopniu jest parzysta.

to oczywiście nie jest warunek wystarczający

Mozna skorzystać z tw. Erdosa-Gallai, ale to jest potężna armata. Drugi sposób to sprawdzić czy algorytm zachłanny (pewnie był podany) poprawnie znajduje graf o takich ciągu stopni.

codi7123 · Post autor: **codi7123** » 16 sty 2012, o 15:47

No właśnie nie było podane. Tylko to że suma wierzcholkow stopnia nieparzystego musi byc parzysta, dlatego w a) probowalem narysowac taki graf ale chyba sie nie da ;/

Zordon · Post autor: **Zordon** » 16 sty 2012, o 16:30

w a) się nie da,
gdyby się dało to istniałby taki graf o 8 wierzchołkach, są w nim dwa wierzchołki stopnia 7, zatem one łączą się ze wszystkimi poza sobą samym, czyli pozostałe wierzchołki muszą mieć stopień przynajmniej 2.