Gli archi possono essere non orientati oppure orientati, e in quest’ultimo caso sono frecce con direzione e verso, ovvero ci dicono da quale nodo partire e a quale nodo arrivare.
Inoltre i grafi possono essere non pesati o pesati e in quest’ultimo caso sopra ogni arco viene riportato un numero (che è appunto il peso).
I grafi si usano in informatica per rappresentare situazioni e risolvere problemi di vario tipo: ad es. per schematizzare un programma, un circuito, una rete di computer, la mappa di un sito. Ma possono anche essere usati per fare l'astrazione di
una carta geografica.
Un grafo in informatica è detto anche albero.
Un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino (grafo non orientato, connesso e privo di cicli).
Ad esempio si può usare per schematizzare un albero genealogico oppure dei corsi d’acqua, con sorgente e affluenti.
Come possiamo rappresentare testualmente un grafo?
Ad esempio potremmo descrivere ogni suo arco nel seguente modo:
arco(<nodo1>,<nodo2>,<lunghezza>)
Questa espressione ci dice di un arco quali nodi unisce e quale è il suo peso, o lunghezza.
Esempio:
arco(n1,n2,3)
arco(n1,n3,4)
arco(n3,n4,2)
arco(n1,n5,8)
arco(n4,n5,1)
Quale è il percorso più breve per andare da n2 a n5?
E' il percorso 2, nonostante attraversi un numero maggiore di nodi, infatti:
percorso1=3+8=11
Il mondo dei grafi è sicuramente affascinante e infatti, non a caso, è proprio a loro che ho dedicato questo mio blog!
Date un'occhiata al mio video su youtube:
Date un'occhiata al mio video su youtube:
Nessun commento:
Posta un commento
Nota. Solo i membri di questo blog possono postare un commento.