Matice incidence
Jiným prostředkem, jak graf popsat maticí, je tak zvaná matice incidence uzlů a hran. Užívá se u grafů bez smyček. Konstrukce této matice vyžaduje stanovit jisté pořadí uzlů a hran. Má-li graf vrcholů a hran, je to obdélníková matice typu Řádky odpovídají vrcholům, sloupce hranám grafu.
U orientovaných grafů je v i-tém sloupci a j-tém řádku číslo pokud je i-tý vrchol počátečním vrcholem j-té hrany, a číslo pokud je jejím koncovým vrcholem. Ostatní prvky matice jsou nuly. Incidenční matice orientovaného grafu bez smyček má v každém sloupci vždy jednu hodnotu a jednu hodnotu Ostatní jsou nuly. U neorientovaných grafů je na místě i,j jednička, pokud je i-tý vrchol incidentní s j-tou hranou, a nula jindy. U neorientovaných grafů jsou v každém sloupci právě dvě jedničky.
Příklad: Pro následující orientovaný a neorientovaný graf sestrojte matice incidence a matice sousednosti.
Řešení: Incidenční matice uzlů a hran:
|
|
Matice sousednosti:
|
|