Turán-gráf
A n csúcsú, m osztályos Turán-gráf alatt a következő gráfot értjük:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/220px-Turan_13-4.svg.png)
Az ilyen egy-egy osztályban a csúcsok függetlenek, tehát nem fut közöttük él. Viszont egy csúcs minden egyéb csúccsal össze van kötve a saját osztályán kívül (ezt jelzik a dupla párhuzamos vonalak). A pontok, annyira amennyire lehetséges, egyenletesen vannak szétosztva az osztályok között, vagyis bármely két osztály elemszámának eltérése legfeljebb 1.
A Turán-gráfoknak az a különleges tulajdonsága, hogy a Turán-tétel szerint ezek a legtöbb élt tartalmazó olyan csúcsú gráfok, amelyek nem tartalmaznak m+1 csúcsú klikket. Vagyis, ha G egy n csúcsú, m+1 csúcsú klikket nem tartalmazó gráf, akkor .
A Turán-gráfok teljes többrészes gráfok.
Tulajdonságai
A Turán-gráf minden csúcsa vagy élű, éleinek teljes száma
Reguláris gráf, ha m|n (m osztja n-et).
Minden Turán-gráf kográf, azaz megalkotható különálló csúcsokból komplementer és diszjunkt unió műveletek elvégzésével. Ez a következő módon történhet: minden osztályt előállítunk különálló pontok halmazaként, majd ennek vesszük a komplementerét. Ezután ezen gráfok uniójának komplementere épp a Turán-gráfot adja.
Chao és Novacky 1982-ben bizonyították, hogy a Turán-gráfok kromatikusan egyediek, azaz nincs más olyan gráf, melyek kromatikus polinomja megegyezik valamely Turán-gráféval.
Fordítás
- Ez a szócikk részben vagy egészben a Turán graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.