Matematické Fórum

Ahoj, sice máme něco podobného teprve před sebou, ale chtěla bych se zeptat zda toho chápu dobře a když tak mi to někdo trošičku více přiblížil už nyní. Předem děkuji za každou odpověď :-)


Pokud máme 2m+1 , kde m=2 (nebo jiném počtu hran), potom může být graf jedině souvislý, protože pokud máme 5 vrcholů a každý tento vrchol 2 hrany neuděláme graf nesouvislý.
I kdyby byl jiný počet hran, nikdy nedostaneme graf nesouvislý . . jedině kdyby m=0, potom počet vrcholů bude 1, graf je tedy jaký?

př:souvislého grafu, m=2 - 5 vrcholů
       o--o
     /       \
    o        o
     \       /
       \   /
         o


============================================
Pokud máme 2m+2, kde m=2(nebo jiný pořet hran), potom může být graf souvislý i nesouvislý?
A jak je to pokud je opět m=0.

př.nesouvislého grafu se dvěmi komponentami souvislosti tzn. to co tu měl Lishaak
     o
o--/-\--o
\/     \/
/\     /\   
o--\-/--o
     o
př: souvislého grafu
    o--o--o
    |        |
    o--o--o


No a kdybych se měla vrátit k příkladu, jak matematicky dokázat, že graf 2m+1 je jistě souvislý? a že to pro 2m+2 neplatí, protože lze vytvořit i grad nesouvislý.

↑ kristýna:Pochopila jsi to dobře. Důkaz souvislosti grafu pro 2m+1 napsal Lishaak.
Pro 2m+2 stačí říct, že pokud budou počítače uspořádány do dvou úplných grafů na m+1 vrcholech, graf souvislý nebude.

Tvrzení platí i pro m=0. V prvním případě máme graf o 1 vrcholu, ten je souvislý (má 1 komponentu).
Ve druhém případě mohou nastat opět dvě možnosti -- souvislý graf:

o--o

i nesouvislý:

o  o

↑ kristýna:
Tomuto uplne nerozumim. Tebou nakreslena sit neodpovida zadani, protoze pises m=3, ale kazdy vrchol je spojen jenom se dvema dalsimi, podle zadani ma byt spojen s alespon 'm' dalsimi (v tomto pripade tedy s alespon tremi dalsimi). Jelikoz ta sit neni podle zadani prikladu, neni me jasne, na co se vlastne ptas nebo co chces demonstrovat.