Graafi seosmaatriks

Allikas: Vikipeedia
Jump to navigation Jump to search

Graafi seosmaatriks on graafi esitav ja selle tippude arvule vastav ruutmaatriks , mille elemendid „1“ esitavad serva olemasolu tipupaari vahel ning elemendid „0“ selle puudumist. Seda maatriksit on nimetatud ka naabruste maatriksiks.

Graaf

Esitatud graafile vastav seosmaatriks :

Seosmaatriks on mõeldud küll graafi esitamiseks, kuid mitte ainult.

Levinud on graafi spektri arvutamine kui seosmaatriksi omaväärtuste hulk, mis on graafi üks mittetäielikest invariantidest. Eksisteerib koguni spektraalne graafiteooria.

Uudne on aga graafi seosmaatriksi astendamine, mis tähendab selle maatriksi korrutamist iseendaga. On selgunud, et seosmaatriksite teatud astme korral identifitseerib saadud graafi elementaarsed sümmeetriaomadused vastavate tipupaari ja tipuorbiitide (-sümmeetriaklasside, positsioonide) näol [1].

Viide[muuda | muuda lähteteksti]

  1. J.-T. Tevet. Graafide identifitseerimine. S.E.R.R., Tallinn, 2017 ISBN 9789949816514

Vaata ka[muuda | muuda lähteteksti]