Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 20. 03. 2019 09:02

check_drummer
Příspěvky: 5578
Reputace:   106 
 

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


"Máte úhel beta." "No to nemám."

Offline

 

#2 20. 03. 2019 21:55

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

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: 5578
Reputace:   106 
 

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


"Máte úhel beta." "No to nemám."

Offline

 

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

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

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: 5578
Reputace:   106 
 

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


"Máte úhel beta." "No to nemám."

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech