Matematické Fórum

Filas · 04. 12. 2014 18:23

Dobrý den,
čelím následujícímu zadání a zajímalo by mě, jestli je má úvaha správná:

"Kolik nejvýše může mít nesouvislý bipartitní graf G na n vrcholech hran?"

moje úvaha:

Mám graf $K_{l,m}$ kde ${l+m}= n$ , pak počet hran $|E| = m*l$ . Musím tedy zvolit mn. Abych dostal největší počet hran, určím $l$ jako $\left \lceil{n/2}\right \rceil$ a $m$ jako $\left \lfloor{n/2}\right \rfloor$ . Pro nesouvislý graf musím jeden vrchol odpojit a sice tak, aby odpojený vrchol byl nejmenšího řádu $d(K_{l,m}) = \left \lfloor{n/2}\right \rfloor$ .

Konečná rovnice je tedy $\left \lceil{n/2}\right \rceil*\left \lfloor{n/2}\right \rfloor - \left \lfloor{n/2}\right \rfloor$

Případně, mohl by mě někdo trošku nasměrovat na správné řešení?

Děkuji

petrkovar · 06. 12. 2014 12:00

↑ Filas:Několik postřehu:
Co to znamená zvolit "mn". Není to překlep?
Máte zdůvodnit, proč by hledaný graf měl být zrovna $K_{l,m}$ a potom, proč by partity měly mít zovna $\left \lceil{n/2}\right \rceil$ a $\left \lfloor{n/2}\right \rfloor$ vrcholů. Jedná se o hledání extrémní hodnoty. Jistě nějaké postupy znáte...

Filas · 06. 12. 2014 13:41

Děkuji za odpoveď.

Ano, jde o překlep. Má tam být lm.

Chápu to tedy správně, že má myšlenka je správná, jen je třeba jí lépe zdůvodnit??

petrkovar · 07. 12. 2014 09:20

↑ Filas:Já myslím, že zdůvodněním se ukáže že nápad je správný.

Filas · 07. 12. 2014 11:49

Děkuji mockrát. Myslím, že jsem přišel na správné řešení.

Matematické Fórum

#1 04. 12. 2014 18:23

Kolik nejvýše vrcholů (Projekt 2, úloha 4)

#2 06. 12. 2014 12:00

Re: Kolik nejvýše vrcholů (Projekt 2, úloha 4)

#3 06. 12. 2014 13:41

Re: Kolik nejvýše vrcholů (Projekt 2, úloha 4)

#4 07. 12. 2014 09:20

Re: Kolik nejvýše vrcholů (Projekt 2, úloha 4)

#5 07. 12. 2014 11:49

Re: Kolik nejvýše vrcholů (Projekt 2, úloha 4)

Zápatí