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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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 18. 01. 2016 23:43

cetis
Příspěvky: 53
Škola: MFF UK
Pozice: student
Reputace:   
 

Teorie grafů - důkaz

Zdravím,

nevím si rady s tím to důkazem, budu rád za jakoukoliv radu.

Ukažte, že každý graf, jehož všechny vrcholy mají stupeň alespoň d, obsahuje cestu na d + 1 vrcholech jako podgraf.

Offline

  • (téma jako vyřešené označil(a) jelena)

#2 19. 01. 2016 10:52

Wotton
Logik
Místo: Plzeň
Příspěvky: 805
Reputace:   24 
 

Re: Teorie grafů - důkaz

Zdravím,

není to tak náročné jak to vypadá:

Nechť máme graf G (dle daných podmínek) a v něm cestu P tak, že její délka je maximálně d (taková musí existovat minimálně pro délku 1). Nyní si označme v poslední vrchol cesty. Tento vrchol má minimálně d sousedních vrcholů (spojených hranou), ale nejvýše d-1 je jich v cestě P. To znemená, že existuje vrchol (označme si jej v'), který je možné přidat k P, tak že nám vznikne cesta P' která je o jeden vrchol delší než P.

No a nyní jsou dvě možnosti: buď má P' délku d+1 a jsme hotovi, nebo má délku maximálně d a můžeme postup opakovat.


Dva jsou tisíckrát jeden.

Offline

 

#3 22. 01. 2016 07:57

cetis
Příspěvky: 53
Škola: MFF UK
Pozice: student
Reputace:   
 

Re: Teorie grafů - důkaz

Děkuji

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson