Matematické Fórum

pavelk · 26. 11. 2010 19:41

Mohl by mi prosim nekdo obecne vysvetlit, jak se da najit nejvyssi pocet komponent v grafu G, ktery je k-pravidelny a ma n vrcholu ?
Co je to komponenta vim a pro konkretni graf s tim nemam problem, bohuzel obecne jsem to zatim nepochopil (ve skriptech jsem nasel pouze vyresene 2 priklady, bez postupu nebo jakehokoliv vysvetleni), kreslit takove grafy taky neni nejmoudrejsi reseni :)
Na webu jsem zjistil, ze takovy algoritmus funguje obdobne jako u prohledavani do hloubky.
Potreboval bych to ale obecne, abych mohl vyresit i jine ulohy.
Dekuji

Kondr · 26. 11. 2010 19:50

↑ pavelk: Stačí rozmyslet, proč má každá komponenta v k-pravidelném grafu alespoň k+1 vrcholů. Dál je to snadné.

pavelk · 27. 11. 2010 13:22

Kondr: Tak po chvili rozjimani jsem prisel na to, ze k+1 vrcholu tam musi byt, jinak by to neslo nakreslit.
A napadl me takovy vzorecek, $\lfloor{\frac{n}{(k+1)}}\rfloor$ , kde n je pocet vrcholu.

vaporx · 27. 11. 2010 15:28

pavelk: napsal jsem ti na tvůj email, který tu máš v profilu, tak jestli by jsi mi prosím odepsal.

Matematické Fórum

#1 26. 11. 2010 19:41

Max. pocet komponent v grafu G

#2 26. 11. 2010 19:50

Re: Max. pocet komponent v grafu G

#3 27. 11. 2010 13:22

Re: Max. pocet komponent v grafu G

#4 27. 11. 2010 15:28

Re: Max. pocet komponent v grafu G