Ricerca di un bersaglio immobile o mobile su una rete

Nel paragrafo "Nascosto Immobile", si considerano diversi algoritmi che, eseguiti consecutivamente, determinano la soluzione del problema del postino cinese (chinese postman problem / CPP).

Per determinare la soluzione del problema del postino cinese, poiché applicabile in distinti contesti (Distribuzione dei giornali, dispersione del sale, approvvigionamento idrico, prova della corrente, itinerario ottimale), risulta necessario affidarsi ad un calcolatore opportunamente istruito. Tuttavia provare ogni possibilità è O (nn) o persino peggiore, quindi già 20 o 30 vertici sono sufficienti affinché nessun calcolatore possa trovare una soluzione in un tempo ragionevole.
L'implementazione trattata nel prosieguo si avvale dei seguenti algoritmi:

1) L'algoritmo di Floyd

2) Corrispondenza perfetta minima (Minimum Perfect matching)

3) L'algoritmo di Dijkstra

4) Percorsi euleriani

Tale concatenazione può risolvere problemi formati da oltre 200 vertici.
– Si trova un insieme di archi, della lunghezza totale minima, tale che quando tali archi sono duplicati (attraversati due volte nel tour) il grado di ogni nodo diventa pari. Il problema è stato risolto usando un algoritmo di corrispondenza con O n3.

Considerando che si può risolvere il CPP, senza visitare un arco più volte, solo se il grafo è Euleriano, se ne deve generare uno artificiale di tale tipo. Ma prima, è necessario un principio collegato con:

Lemma di Handshaking : Per un grafo la somma dei gradi di tutti i suoi nodi corrisponde al doppio del numero degli archi, 2E.
(E = insieme degli archi).