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 20. 03. 2019 09:02

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Maximální graf

Ahoj, ve svých poznámkách jsem našel: Nechť K je maximální graf (vzhledem k počtu hran) takový, že neobsahuje úplný podgraf na p vrcholech (p je pevné). Dokažte (nebo vyvraťte), že v K neexistují tři vrcholy z nichž nejvýše dva jsou spojeny hranou. (Můžete předpokládat, že p je dostatečně velké.)


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#2 20. 03. 2019 21:55

laszky
Příspěvky: 2129
Škola: MFF UK, FJFI CVUT
Reputace:   187 
 

Re: Maximální graf

↑ check_drummer:

Ahoj. Necht u,v,w jsou tri vrcholy grafu K takove, ze hrana je pouze mezi uv. Necht Q je mnozina libovolnych jinych p-3 vrcholu. Oznacme G podgraf grafu K indukovany mnozinou vrcholu {u,v,w} ∪ Q. Graf G je tvoren p vrcholy, ale pridanim hrany mezi uw nebo vw nevznikne uplny graf na p vrcholech (jedna hrana bude urcite chybet). Tim ziskame spor s predpokladanou maximalitou grafu. Analogicky pro pripad, kdy u,v,w tvori nezavislou mnozinu (nesou vubec spojeny).  V K tudiz neexistuji tri vrcholy z nichz nejvyse dva jsou spojeny hranou.

Offline

 

#3 20. 03. 2019 23:23

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Maximální graf

↑ laszky:
Ahoj. A co když existuje nějakých p-2 vrcholů takových, že spolu s vrcholy u,w a přidáním hrany uw již vznikne úplný podgraf velikosti p? (A totéž pro hranu vw.)


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#4 21. 03. 2019 18:01 — Editoval laszky (21. 03. 2019 22:38)

laszky
Příspěvky: 2129
Škola: MFF UK, FJFI CVUT
Reputace:   187 
 

Re: Maximální graf

↑ check_drummer:

Ahoj, mas pravdu. Treba petiuhelnik (C5) je maximalni graf neobsahujici trojuhelnik (K3), pricemz v nem existuji trojice takove, ze jen dva vrcholy jsou spojeny. Pro ostatni zatim netusim :)

Offline

 

#5 21. 03. 2019 21:40

check_drummer
Příspěvky: 3275
Reputace:   90 
 

Re: Maximální graf

Ahoj, namísto

laszky napsal(a):

... pricemz v nem existuji trojice takove, ze jen dva vrcholy jsou spojeny.

by tam spíš mělo stát:
... pricemz v nem existuji trojice takové, že alespoň dvě dvojice vrcholů jsou spojeny.

Protože jestli to chápu dobře, tak pro p=3 tvrzení neplatí.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson