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:
|
|
h1
|
h2
|
h3
|
h4
|
h5
|
h6
|
h7
|
|
A
|
1
|
0
|
1
|
0
|
-1
|
1
|
0
|
|
B
|
-1
|
1
|
0
|
0
|
0
|
0
|
0
|
|
C
|
0
|
0
|
-1
|
-1
|
0
|
0
|
0
|
|
D
|
0
|
0
|
0
|
0
|
0
|
-1
|
1
|
|
E
|
0
|
-1
|
0
|
1
|
1
|
0
|
-1
|
|
|
|
h1
|
h2
|
h3
|
h4
|
h5
|
h6
|
h7
|
|
A
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
|
B
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
|
C
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
D
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
|
E
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
|
Matice sousednosti:
|
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
1
|
1
|
1
|
0
|
|
B
|
0
|
0
|
0
|
0
|
1
|
|
C
|
0
|
0
|
0
|
0
|
0
|
|
D
|
0
|
0
|
0
|
0
|
1
|
|
E
|
1
|
0
|
1
|
0
|
0
|
|
|
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
1
|
1
|
1
|
1
|
|
B
|
1
|
0
|
0
|
0
|
1
|
|
C
|
1
|
0
|
0
|
0
|
1
|
|
D
|
1
|
0
|
0
|
0
|
1
|
|
E
|
1
|
1
|
1
|
1
|
0
|
|
