Matice sousednosti

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ě a_ij 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
	${\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}}$
	Bílá políčka jsou nuly, barevná jedničky
Orientovaný Cayleyho graf S4	Protože je graf orientovaný, matice nemusí být symetrická

Externí odkazy

• Obrázky, zvuky či videa k tématu matice sousednosti na Wikimedia Commons

Autoritní data	GND: 4844440-6