„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
PityuBot (vitalap | szerkesztései)
a fájl;bélyegkép
aNincs szerkesztési összefoglaló
3. sor:
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 éllel össze van kötve az osztályán kivül (ezt jelzik a dupla párhuzamos vonalak). A pontok, annyira amennyire lehetséges, egyenletesen vannak szétosztva az osztályok között (emiatt vannak az alsó és felső egészértékek).
 
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 tartalmazotartalmazó 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>.
 
[[Kategória:Gráfelmélet]]