Cesko.wiki Matice sousednosti
Technology
12 hours ago
8
4
2
Author
Albert FloresMatice 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
| Graf | Matice sousednosti |
|---|---|
| 200px | \begin{pmatrix} 2 & 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} |
| +moresvg'>250px | 250px Bílá políčka jsou nuly, barevná jedničky |
| 250px Orientovaný Cayleyho graf S4 | 250px Protože je graf orientovaný, matice nemusí být symetrická |
.svg){kind=link}
.svg){kind=link}