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

check_drummer
Příspěvky: 2685
Reputace:   73 
 

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é.)


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

#2 20. 03. 2019 21:55

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

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: 2685
Reputace:   73 
 

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.)


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

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

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

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: 2685
Reputace:   73 
 

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í.


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson