Täisgraaf

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

Täisgraafid tippude arvuga 1 kuni 8:

• 
  K₁
• 
  K₂
• 
  K₃
• 
  K₄
• 
  K₅
• 
  K₆
• 
  K₇
• 
  K₈

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

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

Kirjandust

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