grafo, arco di un
grafo, arco di un
grafo, arco di un elemento di un → grafo che esprime la sussistenza di una relazione tra due nodi ed è quindi formalmente definito dalla coppia di nodi (xi, xj) posti in relazione. Poiché un grafo G(X, A) è definito come una coppia di insiemi, l’insieme X dei nodi e l’insieme A degli archi, è possibile rappresentare il primo di questi come un insieme di punti e il secondo come un insieme di linee, gli archi appunto, che collegano i punti. La rappresentazione visiva che si ottiene è quella di una trama di connessioni in cui ciascun arco ha due nodi come estremi. Tra gli archi di un grafo si stabilisce una relazione di adiacenza: si dicono adiacenti due archi che hanno uno (e uno solo) dei due estremi in comune. Inoltre, è possibile stabilire un verso di percorrenza di un arco, considerando appartenente al grafo l’arco (xi, xj) e non l’arco (xj, xi); il grafo che così si ottiene è un grafo orientato. Se in una catena di un grafo orientato x1, a1, x2, a2, …, xk−1, ak−1, xk, si stabilisce il verso di percorrenza da x1 a xk gli archi (xj, xj+1) si dicono concordi con il verso di percorrenza, mentre gli archi (xj+1, xj) sono discordi con il verso di percorrenza.