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
#1 03. 12. 2009 20:51
Hledání grafu
Dobrý den,
zajímalo by mne, zda-li existuje nějaká věta či postup, na hledání takového grafu (či jeho doplňku) na n vrcholech, který obsahuje maximální počet hran, při kterých neobsahuje cyklus dané délky, řekněme 3 (či m, kde m<n). Věděli byste, jak na to?
Kromě hrubého vypsání jsem nenašel vhodné početní řešení, které by mne dovedlo ke zdárnému vyřešení problému.
Pokud to bude možné, spíše mi ukazujte "vodítka", či věty, pomocí kterých bych na to měl přijít.
Díky moc.
Offline
#2 03. 12. 2009 21:48
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Hledání grafu
↑ Nestor10:By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.
Snad netřeba překladu, důkaz jistě někde najdeš.
BRKOS - matematický korespondenční seminář pro střední školy
Offline