Graafi seosmaatriks

Graafi seosmaatriks on graafi esitav ja selle tippude arvule vastav ruutmaatriks $E$, 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 $E$: ${\begin{Bmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{Bmatrix}}$

Seosmaatriks on mõeldud küll graafi $G$ 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 $G$ seosmaatriksi $E$ astendamine, mis tähendab selle maatriksi korrutamist iseendaga. On selgunud, et seosmaatriksite teatud astme $n$ korral identifitseerib saadud $E^{n}$ graafi elementaarsed sümmeetriaomadused vastavate tipupaari ja tipuorbiitide (-sümmeetriaklasside, positsioonide) näol .

Vaata ka

• Graafide identifitseerimine
• Graafi orbiit
• Graafi invariant
• Graafi struktuur