Täisgraaf

Allikas: Vikipeedia
Jump to navigation Jump to search

Täisgraaf on graaf, kus iga kahe erineva tipu vahel on üks serv. Täisgraafil tippude arvuga on serva ning on tähistatav .

Täisgraafid tippude arvuga 1 kuni 8:

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

Graafid kuni on tasandilised. Suure tippude arvuga täisgraafid ei ole tasandilised, sest need sisaldavad alamgraafi , mis ei rahulda Pontrjagini-Kuratovski tingimust.

Kirjandust[muuda | muuda lähteteksti]

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