grafo, nodo di un
grafo, nodo di un
grafo, nodo di un elemento di un → grafo posto in relazione con altri attraverso archi. Un grafo G(X, A) è definito come una coppia di insiemi, l’insieme X dei nodi o vertici e l’insieme A degli archi; il primo è rappresentabile come un insieme di punti, mentre il secondo come un insieme di linee, gli archi, che collegano i punti. Nella teoria dei grafi assume un ruolo importante il grado (detto anche ordine o valenza) di un nodo del grafo, che è uguale al numero di archi che incidono sul nodo stesso. Si dice grado massimo di un grafo G il grado massimo dei suoi nodi, e, analogamente, grado minimo del grafo il grado minimo dei suoi nodi. Un nodo di grado nullo è anche detto nodo isolato.
Se il grafo è orientato, gli archi che incidono in un nodo si distinguono in archi entranti in quel nodo e archi uscenti da esso. Si chiama stella uscente da un nodo l’insieme di archi che escono da quel nodo e stella entrante l’insieme di quelli che giungono a quel nodo. L’unione della stella entrante e della stella uscente dà l’insieme degli archi che incidono sul nodo. Quando si distinguono gli archi che incidono su un nodo in entranti e uscenti, anche il grado del nodo può differenziarsi in grado entrante (numero di archi entranti) e grado uscente (numero di archi uscenti). In un grafo orientato G(X, A) è possibile definire l’insieme dei successori di un nodo xi come l’insieme dei nodi a cui è connesso con un arco uscente: S(xi) = {xj ∈ X: (xi, xj) ∈ A}; analogamente, l’insieme dei predecessori di xi è l’insieme dei nodi da cui parte un arco entrante in xi: P(xi) = {xk ∈ X: (xk, xi) ∈ A}. L’unione dei nodi successori e dei nodi predecessori di xi dà l’insieme dei nodi adiacenti a xi. Il grado di ciascun nodo riveste una notevole importanza nella percorribilità di un grafo e, quindi, nella soluzione del problema che il grafo rappresenta, in particolare, nei problemi di ottimizzazione.