grafo, percorribilita di un

grafo, percorribilita di un

grafo, percorribilità di un caratteristica di un → grafo consistente nell’esistenza di un percorso semplice, cioè di una successione di nodi e archi adiacenti, che passi una e una sola volta per ognuno degli archi del grafo. È stato dimostrato da Eulero che un grafo è percorribile con un percorso semplice chiuso (il cui punto d’arrivo coincida cioè con il punto di partenza) se e solo se tutti i nodi del grafo hanno grado pari (ciclo o grafo euleriano). Se solo due nodi sono di ordine dispari il grafo è percorribile con un percorso semplice aperto a patto che questi due nodi costituiscano i punti di partenza e di arrivo del percorso stesso.