Teoria dei grafi
In matematica, i grafi sono oggetti che permettono una rappresentazione intuitiva di una relazione binaria transitiva tra gli elementi di un insieme.In termini informali, un grafo è un insieme di oggetti, detti vertici o nodi connessi da collegamenti detti archi o spigoli. Solitamente, un grafo è rappresentato da una serie di punti o cerci, che rappresentano i nodi, collegati da linee, che rappresentano gli archi. Per un'approfondimento sulla terminologia specifica della teoria dei grafi, si può consultare il Glossario di Teoria dei grafi.
Definizione: un grafo G è una coppia (V, E) dove V è un insieme e E ⊆ V×V è un sottoinsieme del prodotto cartesiano di V. Gli elementi di V sono detti nodi e quelli di E sono detti archi.
Si distinguono due tipi di grafi:
- i grafi non orientati, dove la relazione E è simmetrica, quindi (a, b) ∈ V → (b, a) ∈ V. In questo tipo di grafo, gli archi sono sovente denominati spigoli e i nodi vertici.
- i grafi orientati o diretti, dove la relazione E non è simmetrica ed esiste una relazione d'ordine tra i nodi.
Le strutture che possono essere rappresentate da grafi sono onnipresenti e molti problemi di interesse pratico possono essere formulati come questioni relative a grafi. In particolare, le reti possono essere descritte in forma di grafi. Ad esempio, la struttura dei link della Wikipedia può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentato l'esistenza di un link tra un articolo e l'altro. I grafi orientati sono anche utilizzati per rappresentare le macchine a stati finiti.
Lo sviluppo di algoritmi per maneggiare i grafi è una delle aree di maggior interesse dell'informatica.
Storia
Il primo testo che prende in considerazione i grafi come entità matematiche è la pubblicazione di Eulero sui "Sette ponti di Königsberg". Questo testo rappresenta anche la prima volta in cui viene affrontato un problema di geometria topologica, che non dipende da alcuna misurazione.
