Teoria dei grafi: differenze tra le versioni

Versione delle 18:22, 10 gen 2016

Versione delle 22:48, 10 feb 2016

Riga 1:

[[File:6n-graf.svg|frame|right|350px|Un diagramma di un grafo con 6 vertici e 7 spigoli.]]

In [[matematica]], [[informatica]] e, più in particolare, [[geometria combinatoria]], la '''teoria dei grafi''' si occupa di studiare i [[Grafo|grafi]], che sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne l'delle analisi in termini quantitativi e [[algoritmo|algoritmici]].

Per un approfondimento sulla terminologia specifica della teoria dei grafi, si può consultare il [[glossario di teoria dei grafi]].

==Descrizione==

==Rappresentazione==

In termini informali, per grafo si intende una struttura costituita da:

* ''oggetti semplici'', detti [[vertice (grafi)|vertici]] (''vertices'') o [[Nodo (grafi)|nodi]] (''nodes''),

* ''collegamenti'' tra i vertici. I collegamenti possono essere:

** ''orientati'', e in questo caso sono detti [[Arco (teoria dei grafi)|archi]] (''arcs'') o cammini (''paths''), e il grafo è detto ''orientato''

** ''non orientati'', e in questo caso sono detti [[Spigolo|spigoli]] (''edges''), e il grafo è detto ''non orientato''

** eventualmente ''dati associati a nodi e/o collegamenti''.

In termini informali, per grafo si intende una struttura costituita da:<ref>Per una definizione formale, si veda alla voce «[[grafo]]».</ref>

* ''oggetti semplici'', detti [[vertice (grafi)|vertici]] (''vertices'') o [[Nodo (grafi)|nodi]] (''nodes''),

* ''collegamenti'' tra i vertici.; Itali collegamenti possono essere:

** ''orientati'', e: in questo caso sono detti [[Arco (teoria dei grafi)|archi]] (''arcs'') o cammini (''paths''), e il grafo è detto ''"orientato''"

** ''non orientati'', e: in questo caso sono detti [[Spigolo|spigoli]] (''edges''), e il grafo è detto ''"non orientato''"

** eventualmenteeventuali ''dati associati a nodi e/o collegamenti''.

Un grafo viene generalmente raffigurato sul piano da punti o cerchietti, che rappresentano i nodi; archi o spigoli sono rappresentati da segmenti o curve che collegano due nodi. In questo caso, ilIl posizionamento dei nodi e la forma degli archi o spigoli è irrilevante, dal momento che a contare sono solo i nodi e le relazioni tra essi. In altri termini, lo stesso grafo può essere disegnato in molti modi diversi senza modificarne le proprietà.

== Applicazioni ==

Per un approfondimento sulla terminologia specifica della teoria dei grafi, si può consultare il [[glossario di teoria dei grafi]].

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 [[Rete (matematica)|reti]] possono essere descritte in forma di grafi. Ad esempio, la struttura dei link della [[Wikipedia]], come tutti gli [[ipertesto|ipertesti]], 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.

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 [[Rete (matematica)|reti]] possono essere descritte in forma di grafi. Ad esempio, la struttura dei link della [[Wikipedia]], come tutti gli [[ipertesto|ipertesti]], 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 [[Macchina a stati finiti|macchine a stati finiti]] e molti altri formalismi, come ad esempio [[diagramma di flusso|diagrammi di flusso]], [[Processo markoviano|catene di Markov]], [[Modello E-R|schemi entità-relazione]], [[rete di Petri|reti di Petri]] e molti altri.

Lo sviluppo di [[Algoritmo|algoritmi]] per manipolare i grafi è una delle aree di maggior interesse dell'[[informatica]].