Pagina iniziale | Navigazione |
Google

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 EV×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.

Un caso estremo di grafo è un grafo costituito da un solo nodo, detto grafo nullo.

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.


GNU Fdl - it.Wikipedia.org




Google | 

Enciclopedia |  La Divina Commedia di Dante |  Mappa | : A |  B |  C |  D |  E |  F |  G |  H |  I |  J |  K |  L |  M |  N |  O |  P |  Q |  R |  S |  T |  U |  V |  W |  X |  Y |  Z |