Teoria dei grafi: differenze tra le versioni

Versione delle 02:40, 2 mar 2016

Versione attuale delle 17:02, 3 mag 2025

(23 versioni intermedie di 18 utenti non mostrate)

Riga 1:

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

[[File:6n-graf.svg|frame|right|300px|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 ==

[[File:Keningsbergo pontoj markitaj.png|thumb|250px|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]].

Riga 16 ⟶ 17:

* ''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".

Riga 31 ⟶ 32:

== Applicazioni ==

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

Riga 67 ⟶ 68:

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