Matematické Fórum

těžký, takhle z hlavy · 05. 05. 2009 19:36

Ahoj, mám problém s příkladem: Je dána posloupnost čísel 6,5,5,4,3,3,3,2,1. Určete, zda existuje neorientovaný graf, jehož je tato posloupnost souborem stupňů. Pokud ano nakreslete ho.
Chápu sice že neorientovaný graf je dán množinou vrcholů a hran. Ale když tam je více stejných vrcholů, tak si nevím rady.

Kondr · 05. 05. 2009 21:39

Ahoj, nutnou podmínkou pro sestrojení grafu je, aby byl součet sudý. Algoritmus na sestavení grafu je takový, že vždy
1) odstraníme největší číslo, jeho hodnotu označme k
2) následujících k čísel zmenšíme o 1
opakujeme, dokud nám nezbudou dvě jedničky.
Příklad zde: http://forum.matweb.cz/viewtopic.php?id=8324

těžký, takhle z hlavy · 05. 05. 2009 23:06

dopracoval jsem se k řešení:
655433321 (k=6) -> 44322221 (k=4) -> 3222111 (k=3) -> 111111 (k=1) -> 11110 (k=1) -> 1100 (k=1) -> 000
znamená to tedy, že mám na začátku 3 vrcholy, které nejsou spojené, ale při postupném kreslení nevím jak se dopracuji ke konci, pokusím se to tu znázornit:

000:
o o o

1100:
o--o o o

11110:
o--o o o--o

111111:
o--o o--o o--o

3222111:
o--o o--o o--o
\ | /
\ | /
o

44322221:
o--o o--o o--o
\ | / \ | /
\ | / \ | /
o --------o

655433321:
o--o o--o o--o
\ | / \ | /
\ | / \ | /
o --------o
\ /
\ /
o tady už nevím, ke kterým dalším 4 ho mám připojit

Kondr · 05. 05. 2009 23:57

Máš špatně už předposlední krok, tvůj graf má skóre 44222222. Zkus si vrcholy očíslovat a pak dohledat, u kterých vrcholů jsi snižoval stupeň ve kterém kroku odečítání.

Matematické Fórum

#1 05. 05. 2009 19:36

Neorientovaný graf

#2 05. 05. 2009 21:39

Re: Neorientovaný graf

#3 05. 05. 2009 23:06

Re: Neorientovaný graf

#4 05. 05. 2009 23:57

Re: Neorientovaný graf

Zápatí