Matice incidence

Matice incidence je matice, v které jsou informace o tom, které z prvků (typicky příslušné k řádkům) jsou prvky kterých podmnožin (typicky příslušných k sloupcům).

Teorie grafů

Nejběžnějším příkladem je reprezentace grafů v teorii grafů. V případě neorientovaného grafu má matice řádek pro každý vrchol a sloupec pro každou hranu. Pokud vrchol náleží hraně, je na dané pozici jednička, jinak nula. Pro reprezentaci orientovaných grafů stačí například výchozí vrchol místo čísla jedna značit číslem minus jedna.

Příklad

Neorientovaný graf na obrázku se čtyřmi vrcholy a čtyřmi hranami má následující matici incidence:

{\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{pmatrix}}

Externí odkazy

Obrázky, zvuky či videa k tématu Matice incidence na Wikimedia Commons