10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
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