Täisgraaf

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

Täisgraafid tippude arvuga 1 kuni 8:

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

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

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

Kirjandust

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