„Turán-gráf” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
aNincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
1. sor:
A <math>T_m(n)</math> n csúcsú, m osztályos Turán-gráf alatt a következő [[gráf]]ot értjük:
[[Fájl:Turan 13-4.svg|bélyegkép]]
Az ábrán egy-egy osztályban a csúcsok függetlenek, tehát nem fut közöttük él. Viszont, egy csúcs minden
Az ábrán szereplő gráfnak az a különleges tulajdonsága, hogy a [[Turán-féle gráftétel]] szerint ez a legtöbb élt tartalmazó olyan <math>n</math> csúcsú gráf, amely nem tartalmaz egy <math>K_{m+1}</math> [[teljes gráf]]ot. Vagyis, ha <math>G</math> <math>n</math> csúcsú és <math>K_{m+1}</math>-mentes, akkor <math>|E(G)| \leq |E(T_m(n))|</math>.
| |||