Matice incidence

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

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ů[editovat | editovat zdroj]

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 mínus jedna.

Příklad[editovat | editovat zdroj]

Příklad neorientovaného grafu

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

Externí odkazy[editovat | editovat zdroj]