Matice sousednosti

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Matice sousednosti je v matematice a informatice používaný způsob reprezentace grafu. Pro konečnou množinu vrcholů grafu G, kterých je n, má podobu čtvercové matice n×n, jejíž hodnota na místě aij je celé číslo odpovídající počtu hran vedoucích z vrcholu i do vrcholu j. Prvky na diagonále tak obvykle odpovídají počtu hran vedoucích z vrcholu i do vrcholu i (takové je běžná konvence u orientovaných grafů), ovšem někdy se na diagonálu ukládá dvojnásobek této hodnoty (taková bývá konvence u neorientovaných grafů). Pro každou třídu izomorfismu grafů existuje až na prohazování řádků a sloupců právě jedna matice sousednosti a ta neodpovídá žádné jiné třídě.

Příklady[editovat | editovat zdroj]

Graf Matice sousednosti
6n-graph2.svg \begin{pmatrix}
1 & 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{pmatrix}
Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg

Bílá políčka jsou nuly, barevná jedničky

Symmetric group 4; Cayley graph 4,9; numbers.svg


Orientovaný Cayleyho graf S4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg

Protože je graf orientovaný, matice nemusí být symetrická

Logo Wikimedia Commons
Wikimedia Commons nabízí obrázky, zvuky či videa k tématu