Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#2 18. 11. 2012 02:46
- JohnPeca18
- Příspěvky: 651
- Škola: MFF UK
- Pozice: Absolvent 2014
- Reputace: 81
Re: Grafy
napady
203.
a) Zober si tie 4 vrcholy na niektorej uhlopriecke, urcite musia byt v HK, tak teda predpokladaj ze zacinas budovat HK od tejto uhlopriecky, ake mas moznosti ako pokracovat? Nevyhnutne ukoncis kruznicu skor ako obides vsetky vrcholy.
b) podobne, vezmes si 3 vrcholy na niektorej uhlopriecke a skusis budovat HK. Uz tym ze odizolujes tou uhloprieckou cast grafu ti zabrani najst HK.
210.
Ak ma HK, tak preskakujes v HK po hranach z jednej partity do druhej, takze musia mat rovnaku velkost.
Offline
#3 18. 11. 2012 03:06
- JohnPeca18
- Příspěvky: 651
- Škola: MFF UK
- Pozice: Absolvent 2014
- Reputace: 81
Re: Grafy
212.
Skus si predstavit, ze jednotlive vrcholy su cisla v 
, teda cisla {0,1,2 ...p-1}.
jednotlive HK zacnes budovat v bode 0 a to tak, ze i-ta HK bude generovana pripocitavanim 0+i.
Napriklad pre p=5, budes mat v 
HK i=1, 0,1,2,3,4,0
HK i=2 0,2,4,1,3,0
HK i=3 0,3,1,4,2,0
HK i=4 0,4,3,2,1,0
Vidis, ze HK pre i=k je ta ista ako HK pre i=p-k. takze ich je dokopy (p-1)/2.
To ze tam mas prvocislo ti garantuje, ze takto to mozes generovat, ze sa nedostanes spat do 0 skor ako prejdes vsetky prvky. A to ze pripocitavas stale ine cislo ti garantuje hranovu disjunktnost.
Offline