Matematické Fórum

Mauz · 09. 12. 2015 21:19

Zadání:
Je graf s 2n vrcholy a deg(v) = n souvislý?
(Redukované zadání z 2n kruhových objezdů, kde z každého vychází n ulic, a úkolem zjistit, je-li možné dostat se z libovolného objezdu na jiný libovolný objezd.)

Nevím proč, ale vyplývá z toho, že počet hran je $n^{2}$ s čímž už se nějak pracovat dá, protože $m\ge n-1$ (kde m je počet hran a n je počet vrcholů), můžu substituovat na $n^{2}\ge n-1$ . Což je vždy pravda a dalo by se to dokázat velmi jednoduše např. indukcí.

Jak se dostanu k počtu hran?

Díky

petrkovar · 10. 12. 2015 01:29

Uvedená argumentace není šikovná. proč $n^{2}$ ? Nemělo by být alespoň $n^{2}$ ?
Šikovnější je využít sporu (případně nepřímého důkazu).

Kdyby byl graf nesouvislý, kolik vrcholů by měla MENŠÍ komponenta?

Matematické Fórum

#1 09. 12. 2015 21:19

Souvislost grafu

#2 10. 12. 2015 01:29

Re: Souvislost grafu