Täisgraaf

Täisgraaf on graaf, kus iga kahe erineva tipu vahel on üks serv. Täisgraafil tippude arvuga $n$$n$ on $n(n-1)/2$$n(n-1)/2$ serva ning on tähistatav $K_{n}$$K_{n}$.

Täisgraafid tippude arvuga 1 kuni 8:

• 

  K₁

• 

  K₂

• 

  K₃

• 

  K₄

• 

  K₅

• 

  K₆

• 

  K₇

• 

  K₈

Täisgraaf on regulaarne valentsusega $n-1$$n-1$, tugevregulaarne, transitiivne ja täissümmeetriline. Automorfismide arv $n!$$n!$. Täigraafi täiend on tühigraaf.

Graafid $K_{1}$$K_{1}$ kuni $K_{4}$$K_{4}$ on tasandilised. Suure tippude arvuga täisgraafid ei ole tasandilised, sest need sisaldavad alamgraafi $K_{5}$$K_{5}$, mis ei rahulda Pontrjagini-Kuratovski tingimust.

Kirjandust

• Buldas, A., Laud, P., Villemson, J. (2003), Graafid, TÜ kirjastus