Täisgraaf

Allikas: Vikipeedia

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:

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[muuda | redigeeri lähteteksti]

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