Matrici di incidenza

Matrici d'incidenza e grafici

L'algebra delle matrici si rivela un metodo comodo e potente per descrivere il modo in cui i punti in un

grafico sono connessi l'uno all'altro. Per grafico intendiamo una serie di punti (i vertici), alcuni dei

quali sono connessi ad altri punti del grafico da segmenti. La matrice che descrive le connessioni è

chiamata matrice d'incidenza.

Supponiamo di aver evidenziato una serie di luoghi su una mappa. Potrebbero essere città o angoli di

strade, qualsiasi cosa. Possiamo descrivere questi luoghi come punti su un grafico, come abbiamo fatto

qui sotto con un piccolo insieme di luoghi generati a caso. Chiamiamoli città.

1

0.5

0 0 0.5 1

i x , y . Associata ad ogni coppia di

è quella rappresentata dalle coordinate

Affermiamo che la città i i

S

i j i j

città e c'è un elemento pari ad 1 se possiamo spostarci dalla città alla città e altrimenti pari a

i , j S 1

0 a seconda, per esempio, che queste città siano servite da una linea aerea oppure no . Quindi sta

i , j

i j

alla città .

ad indicare che c'è un volo diretto dalla città

Una tale matrice si chiama .

Matrice d'incidenza

Abbiamo generato a caso una matrice d'incidenza per i nostri dati. Notiamo alcune cose a proposito di

questa matrice: 0

0

0

1

1

0 0

1

1

1

0

1 1

0

1

0

1

1

S = 1

1

0

1

1

0 1

0

1

0

1

0 0

1

1

1

0

0