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$: $\left\{\begin{array}{cccccc}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{array}\right\}$

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