Топ-100
Indietro

ⓘ Teoria dei grafi. In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei g ..




Teoria dei grafi
                                     

ⓘ Teoria dei grafi

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

                                     

1. 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: il problema dei ponti di Königsberg.

Nel XIX secolo è stato posto e discusso il problema dei quattro colori, rivelatosi molto impegnativo e risolto solo nella seconda metà del XX secolo. È stato anche introdotto il problema dei cammini hamiltoniani. 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. Lintroduzione del computer ha consentito da un lato lo sviluppo di indagini sperimentali sui grafi e dallaltro ha richiesto alla teoria dei grafi di indagare su algoritmi e modelli di forte impatto applicativo. Nel giro di cinquantanni la teoria dei grafi è diventata un capitolo della matematica molto sviluppato, ricco di risultati profondi e con forti influenze applicative.

                                     

2. Rappresentazione

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

  • non orientati cioè dotati di una direzione, ma non dotati di un verso: in questo caso sono detti spigoli, e il grafo è detto "non orientato";
  • 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".
  • collegamenti tra i vertici; tali collegamenti possono essere
  • oggetti semplici, detti vertici o nodi;
  • orientati cioè dotati di una direzione e di un verso: in questo caso sono detti archi o cammini, e il grafo è detto "orientato" o digrafo;

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.

Il posizionamento dei nodi e la forma degli archi o spigoli è irrilevante, dal momento che a contare sono solo i nodi 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.

                                     

3. 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 reti possono essere descritte in forma di grafi. Ad esempio, la struttura dei link di Wikipedia, come tutti gli ipertesti, può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentano lesistenza di un collegamento da un articolo allaltro.

I grafi orientati sono anche utilizzati per rappresentare le macchine a stati finiti e molti altri formalismi, come ad esempio diagrammi di flusso, catene di Markov, schemi entità-relazione e reti di Petri.

Lo sviluppo di algoritmi per manipolare i grafi è una delle aree di maggiore interesse dellinformatica.

                                     
  • Nella teoria dei grafi un vertice o nodo è l unità fondamentale di cui i grafi sono costituiti: un grafo consiste in un insieme di vertici e di archi
  • l insieme dei nodi connessi. Un albero è una foresta connessa. Può essere definito anche come un grafo connesso ed aciclico. Oppure: nella teoria dei grafi un
  • della teoria algebrica dei grafi che implicano l uso dell algebra lineare, l uso della teoria dei gruppi e lo studio delle invarianti dei grafi La prima
  • studio, la teoria dei grafi costituisce un importante parte della combinatoria i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi
  • Gross: Graph Theory and Its Applications, Chapman Hall CRC, 2005 2nd edition, ISBN 978 - 1 - 58488 - 505 - 4 Teoria dei grafi Minore teoria dei grafi
  • Nella disciplina matematica della teoria dei grafi un accoppiamento o abbinamento in inglese matching o insieme degli spigoli indipendenti in un grafo
  • La teoria chimica dei grafi è una branca della chimica matematica che applica la teoria dei grafi ai modelli matematici utilizzati per descrivere i fenomeni
  • Nella teoria dei grafi un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè
  • In teoria dei grafi una cricca o clique è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un
  • Nella teoria dei grafi una componente connessa o semplicemente una componente di un grafo indiretto è un sottografo in cui: qualsiasi coppia di vertici