10: Allocazione dinamica della memoria Vers. 9.3 – Dicembre 2025
DEF. In un grafo G si definisce CAMMINO una successione di nodi adiacenti che non contiene due volte lo stesso arco.
N. B. Un cammino può invece contenere due volte lo stesso nodo
Ad esempio nel nostro grafo G: la successione di nodi B, C, E, H, I, E, D la successione di nodi B, C, E, G, I, E, D è un cammino tra i nodi B e D è un altro cammino tra i nodi B e D MA FATE MOLTA ATTENZIONE … è facile farsi ingannare ….. la successione di nodi B, C, E, G, E, D
NON è un cammino tra i nodi B ed D
DEF. In un grafo G si definisce CAMMINO SEMPLICE un cammino costituito da tutti nodi distinti ad eccezione eventualmente del primo e dell’ ultimo( che possono eventualmente coincidere). Nel caso di cammino semplice con nodo iniziale uguale al nodo finale si parla di CAMMINO SEMPLICE CICLICO o più semplicemente CICLO.
Ad esempio nel nostro grafo G: |
la successione di nodi B, C, G, E, D |
è un cammino semplice tra i nodi B e D |
la successione di nodi B, C, F, G, E, D, B |
è un cammino semplice ciclico ossia un ciclo di B |
N. B. In generale possono esistere diversi cammini semplici che uniscono due stessi nodi |
la successione di nodi B, E, D |
è un cammino semplice che unisce i nodi B ed D |
la successione di nodi B, E, H, D |
è un cammino semplice che unisce i nodi B ed D |
la successione di nodi B, C, E, H, D |
è un cammino semplice che unisce i nodi B ed D |
la successione di nodi B, C, E, I, H, D |
è un cammino semplice che unisce i nodi B ed D |
DEF. Un grafo G si definisce connesso se per ogni coppia di nodi considerata esiste sempre almeno un cammino che li congiunge. In modo equivalente un grafo G si definisce connesso se, considerati due suoi nodi arbitrari, esiste sempre almeno un cammino che li congiunge
DEF. Un grafo G si definisce orientato se ogni arco è dotato di orientamento ossia di un verso di percorrenza
Tale orientamento indica la relazione logica che esiste tra i dati contenuti nei due nodi congiunti dall’ arco.
N. B. In tal caso al posto dei segmenti semplici per rappresentare gli archi vengono utilizzate le frecce con uno o due punte considerando in questo tipo di grafo un eventuale segmento semplice del tutto equivalente alla freccia con le due punte.
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 43