Teoria dei grafi: differenze tra le versioni

Versione delle 22:50, 10 feb 2016

Versione attuale delle 17:02, 3 mag 2025

(24 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{NN|matematica|ottobre 2023|argomento2=informatica}}

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

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

== Storia ==

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

[[File:Keningsbergo pontoj markitaj.png|thumb|Rappresentazione del [[problema dei ponti di Königsberg]].]]

Il primo testo che prende in considerazione i grafi come entità matematiche è la pubblicazione di [[Leonhard Euler|Eulero]] sui "Sette ponti di Königsberg". Questo testo rappresenta anche la prima volta in cui viene affrontato un problema di [[Topologia|geometria topologica]], che non dipende da alcuna misurazione: il [[problema dei ponti di Königsberg]].

Nel [[XIX secolo]] è stato posto e discusso il [[teorema dei quattro colori|problema dei quattro colori]], rivelatosi molto impegnativo e risolto solo nella seconda metà del [[XX secolo]]. È stato anche introdotto il problema dei [[Cammino hamiltoniano|cammini hamiltoniani]].

==Rappresentazione==

Fino a metà del [[XX secolo]] poco altro è stato scoperto.

Nella seconda metà del [[XX secolo]] gli studi e i risultati si sono sviluppati ampiamente, in sintonia con i forti sviluppi della [[combinatoria]] e del calcolo automatico. L'introduzione del computer ha consentito da un lato lo sviluppo di indagini sperimentali sui grafi (come, in particolare, nella dimostrazione del [[teorema dei quattro colori]]) e dall'altro ha richiesto alla teoria dei grafi di indagare su algoritmi e modelli di forte impatto applicativo. Nel giro di cinquant'anni la teoria dei grafi è diventata un capitolo della matematica molto sviluppato, ricco di risultati profondi e con forti influenze applicative.

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]] o [[Nodo (grafi)|nodi]],

== Rappresentazione ==

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]] o [[Nodo (grafi)|nodi]], ;

* ''collegamenti'' tra i vertici; tali collegamenti possono essere:

** ''non orientati'' (cioè dotati di una direzione, ma non dotati di un verso): in questo caso sono detti [[Arco (teoria dei grafi)Spigolo|archispigoli]] o cammini, e il grafo è detto "non orientato";

** ''non orientati'' (cioè dotati di una direzione e di un verso): in questo caso sono detti [[SpigoloArco (teoria dei grafi)|spigoliarchi]] o cammini, e il grafo è detto "non orientato" o [[Digrafo (matematica)|digrafo]];

** eventuali ''dati associati a nodi e/o collegamenti''; un [[grafo pesato]] è un esempio di grafo in cui a ogni collegamento è associato un valore numerico, detto "peso".

Un grafo viene generalmente raffigurato sul piano da punti o cerchietti, che rappresentano i nodi; archii ocollegamenti spigolitra i vertici sono rappresentati da segmenti o curve che collegano due nodi.; Ilnel posizionamentocaso deidi nodiun egrafo laorientato, formail verso degli archi o spigoli è irrilevante,indicato 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 modificarneda leuna proprietàfreccia.

<gallery>

== Applicazioni ==

File:Dominator control flow graph.svg|Esempio di grafo orientato

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.

File:Graph weights.svg|Esempio di grafo pesato

</gallery>

Il 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à.

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.

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

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

== StoriaApplicazioni ==

Le strutture che possono essere rappresentate da grafi sono onnipresentipresenti in molte discipline 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 delladi [[Wikipedia]], come tutti gli [[ipertesto|ipertesti]], può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentatorappresentano l'esistenza di un linkcollegamento trada un articolo e lall'altro.

Il primo testo che prende in considerazione i grafi come entità matematiche è la pubblicazione di [[Leonhard Euler|Eulero]] sui "Sette ponti di Königsberg". Questo testo rappresenta anche la prima volta in cui viene affrontato un problema di [[Topologia|geometria topologica]], che non dipende da alcuna misurazione: il [[problema dei ponti di Königsberg]].

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]], e [[rete di Petri|reti di Petri]] e molti altri.

Nel [[XIX secolo]] è stato posto e discusso il [[teorema dei quattro colori|problema dei quattro colori]], rivelatosi molto impegnativo e risolto solo nella seconda metà del [[XX secolo]]. È stato anche introdotto il problema dei [[Cammino hamiltoniano|cammini hamiltoniani]].

Fino a metà del [[XX secolo]] poco altro è stato scoperto.

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

Nella seconda metà del [[XX secolo]] gli studi e i risultati si sono sviluppati ampiamente, in sintonia con i forti sviluppi della [[combinatoria]] e del calcolo automatico. L'introduzione del computer ha consentito da un lato lo sviluppo di indagini sperimentali sui grafi (come, in particolare, nella dimostrazione del [[teorema dei quattro colori]]) e dall'altro ha richiesto alla teoria dei grafi di indagare su algoritmi e modelli di forte impatto applicativo. Nel giro di cinquant'anni la teoria dei grafi è diventata un capitolo della matematica molto sviluppato, ricco di risultati profondi e con forti influenze applicative.

== Note ==

Riga 34 ⟶ 42:

== Bibliografia ==

* {{en}} K. Thulasiraman, M. N. S. Swamy (1992): ''Graphs: Theory and Algorithms'', [[J.Wiley]]

* {{en}} [[Béla Bollobás]] (1998): ''Modern Graph Theory'', Springer, ISBN 0-387-98488-7

* {{en}} [[Lowell W. Beineke]], [[Robin J. Wilson]], [[Peter J. Cameron]], eds (2004): ''Topics in Algebraic Graph Theory'', Cambridge University Press

* {{en}} D. Cvetković, P. Rowlison, S. Simić (1997): ''Eigenspaces of Graphs'', Cambridge University Press *

* {{en}} Reinhard Diestel (2005): ''Graph Theory'', 3rd edition, Springer, ISBN 3-540-26182-6. Anche disponibile liberamente in [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ PDF]

== Voci correlate ==

* [[05Cxx]]: {{MSCid|teoria dei grafi}}

* [[Albero (grafo)]]

* [[Calcolo combinatorio]]

* [[Complessità computazionale]]

* [[Ottimizzazione combinatoria]]

* [[Automa a stati finiti]]

* [[Grammatica formale]]

* [[Linguaggi di Lindenmayer]]

* [[Teoria dei giochi]]

* [[Teoria del mondo piccolo]]

* [[Diagramma di flusso]]

* [[Organigramma]]

* [[Rete (matematica)]]

* [[Albero genealogico]]

* [[Schema di classificazione]]

* [[Problema dei ponti di Königsberg]]

* [[Problema del postino cinese]]

* [[Sei gradi di separazione]]

* [[Teoria chimica dei grafi]]

* [[Matrice delle adiacenze|Matrice di adiacenza]]

== Altri progetti ==

{{interprogetto|commonspreposizione=Category:Graph theorysulla}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{cita web|http://www.spazioblog.it/uploads/g/giorgioragusa/212322.pdf|Appunti sui grafi- Università di Catania}}

* {{cita web|http://teoriadeigrafi.altervista.org|Teoria dei Grafi 1.0 - Desmatron}}

* {{cita web|http://simonesgariglia.it/grafi/|Teoria dei Grafi - Appunti}}

* {{cita web|http://graphtheorysoftware.com/|Graph Theory Software}}

{{Combinatoria}}

{{Controllo di autorità}}

{{Portale|informatica|matematica}}

[[Categoria:Teoria dei grafi| ]]