Teoria dei grafi: differenze tra le versioni

Versione delle 12:42, 17 ago 2012

Versione attuale delle 17:02, 3 mag 2025

(44 versioni intermedie di 27 utenti non mostrate)

Riga 1:

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

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

[[File:6n-graf.svg|frame|right|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''' si occupa di studiare i [[Grafo|grafi]], oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne l'analisi in termini quantitativi e [[algoritmo|algoritmici]].

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

==Descrizione Storia ==

[[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]].

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

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

* ''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''), 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''

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.

Per una definizione formale, si veda alla voce «[[grafo]]».

== Rappresentazione ==

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

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 [[Spigolo|spigoli]], e il grafo è detto "non orientato";

** ''orientati'' (cioè dotati di una direzione e di un verso): in questo caso sono detti [[Arco (teoria dei grafi)|archi]] o cammini, e il grafo è detto "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; i collegamenti tra i vertici sono rappresentati da segmenti o curve che collegano due nodi; nel caso di un grafo orientato, il verso degli archi è indicato da una freccia.

<gallery>

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

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

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

== Applicazioni ==

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.

Le strutture che possono essere rappresentate da grafi sono presenti 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 di [[Wikipedia]], come tutti gli [[ipertesto|ipertesti]], può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentano l'esistenza di un collegamento da un articolo all'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]] e [[rete di Petri|reti di Petri]].

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

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

== Storia ==

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]].

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

== Note ==

Nella seconda metà del [[XX secolo]] gli studi e i risultati si sono sviluppati ampiamente, in sintonia con i forti sviluppi della [[combinatorica]] 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.

<references/>

== 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 ==

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

* [[CalcoloAlbero combinatorio(grafo)]]

* [[Calcolo combinatorio]]

*[[Complessità computazionale]]

* [[Complessità computazionale]]

*[[Ottimizzazione combinatoria]]

* [[Ottimizzazione combinatoria]]

*[[Automa a stati finiti]]

* [[GrammaticaAutoma a stati formalefiniti]]

* [[Grammatica formale]]

*[[Linguaggi di Lindenmayer]]

* [[TeoriaLinguaggi deidi giochiLindenmayer]]

* [[Teoria del mondodei piccologiochi]]

* [[DiagrammaTeoria del dimondo flussopiccolo]]

* [[Diagramma di flusso]]

*[[Organigramma]]

* [[Organigramma]]

*[[Rete (matematica)|Rete]]

* [[AlberoRete genealogico(matematica)]]

* [[Albero genealogico]]

*[[Schema di classificazione]]

* [[Problema dei pontiSchema di Königsbergclassificazione]]

* [[Problema deldei ponti postinodi cineseKönigsberg]]

* [[Problema del postino cinese]]

*[[Sei gradi di separazione]]

* [[TeoriaSei chimicagradi deidi grafiseparazione]]

* [[Teoria chimica dei grafi]]

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

== Altri progetti ==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* [http://www.spazioblog.it/uploads/g/giorgioragusa/212322.pdf Appunti sui grafi- Università di Catania]

* [http://teoriadeigrafi.altervista.org Teoria dei Grafi 1.0 - Desmatron]

* [http://simonesgariglia.it/grafi/ Teoria dei Grafi - Appunti]

[[Categoria:Teoria dei grafi]]

{{Link AdQ|nl}}

{{Combinatoria}}

{{Controllo di autorità}}

{{Portale|matematica}}

{{Portale|informatica|matematica}}

[[Categoria:Teoria dei grafi| ]]

[[am:ሥነ ግራፍ]]

[[an:Teoría de grafos]]

[[ar:نظرية المخططات]]

[[bg:Теория на графите]]

[[bn:গ্রাফ তত্ত্ব]]

[[bs:Teorija grafikona]]

[[ca:Teoria de grafs]]

[[cs:Teorie grafů]]

[[cy:Damcaniaeth graffiau]]

[[da:Grafteori]]

[[de:Graphentheorie]]

[[el:Θεωρία γράφων]]

[[en:Graph theory]]

[[eo:Grafeteorio]]

[[es:Teoría de grafos]]

[[et:Graafiteooria]]

[[eu:Grafo teoria]]

[[fa:نظریه گراف]]

[[fi:Graafiteoria]]

[[fr:Théorie des graphes]]

[[he:תורת הגרפים]]

[[hi:ग्राफ़ सिद्धान्त]]

[[hu:Gráfelmélet]]

[[hy:Գրաֆների տեսություն]]

[[id:Teori graf]]

[[is:Netafræði]]

[[ja:グラフ理論]]

[[kk:Граф]]

[[ko:그래프 이론]]

[[lt:Grafų teorija]]

[[mn:Графын онол]]

[[ms:Teori graf]]

[[mt:Teorija tal-grafi]]

[[nl:Grafentheorie]]

[[nn:Grafteori]]

[[no:Grafteori]]

[[pl:Teoria grafów]]

[[pt:Teoria dos grafos]]

[[ro:Teoria grafurilor]]

[[ru:Теория графов]]

[[scn:Tiuria dî grafi]]

[[simple:Graph theory]]

[[sk:Teória grafov]]

[[sl:Teorija grafov]]

[[sr:Теорија графова]]

[[sv:Grafteori]]

[[tg:Назарияи графҳо]]

[[th:ทฤษฎีกราฟ]]

[[tl:Teoriya ng grapo]]

[[tr:Çizge Kuramı]]

[[uk:Теорія графів]]

[[ur:نظریۂ مخطط]]

[[vi:Lý thuyết đồ thị]]

[[zh:图论]]