Skip to main content

Teoria dei grafi Indice Storia | Rappresentazione | Applicazioni | Note | Bibliografia | Voci correlate | Altri progetti | Collegamenti esterni | Menu di navigazionePDFWikimedia CommonsWikimedia Commonsteoria dei grafiTeoria dei grafiTeoria dei grafiAppunti sui grafi- Università di CataniaTeoria dei Grafi - AppuntiGraph Theory SoftwareMsh850564714113782-6

Multi tool use
Multi tool use

Teoria dei grafi


matematicainformaticageometria combinatoriagrafialgoritmiciEulerogeometria topologicaproblema dei ponti di KönigsbergXIX secoloproblema dei quattro coloriXX secolocammini hamiltonianiXX secoloXX secolocombinatoriateorema dei quattro coloriglossario di teoria dei grafiretiWikipediaipertestimacchine a stati finitidiagrammi di flussocatene di Markovschemi entità-relazionereti di Petrialgoritmiinformatica












Teoria dei grafi




Da Wikipedia, l'enciclopedia libera.






Jump to navigation
Jump to search



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




Indice





  • 1 Storia


  • 2 Rappresentazione


  • 3 Applicazioni


  • 4 Note


  • 5 Bibliografia


  • 6 Voci correlate


  • 7 Altri progetti


  • 8 Collegamenti esterni




Storia |




Rappresentazione del problema dei ponti di Königsberg.


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



Rappresentazione |


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



  • oggetti semplici, detti vertici o 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 spigoli, e il grafo è detto "non orientato";


    • 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;

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


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 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 l'esistenza di un collegamento da un articolo all'altro.


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 dell'informatica.



Note |



  1. ^ Per una definizione formale, si veda alla voce "grafo".



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 PDF


Voci correlate |



  • 05Cxx: sigla della sezione della MSC dedicata 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


Altri progetti |



Altri progetti


  • Wikimedia Commons


  • Collabora a Wikimedia CommonsWikimedia Commons contiene immagini o altri file su teoria dei grafi


Collegamenti esterni |





  • Teoria dei grafi, su thes.bncf.firenze.sbn.it, Biblioteca Nazionale Centrale di Firenze. Modifica su Wikidata


  • (EN) Teoria dei grafi, su Enciclopedia Britannica, Encyclopædia Britannica, Inc. Modifica su Wikidata

  • Appunti sui grafi- Università di Catania (PDF), su spazioblog.it.

  • Teoria dei Grafi - Appunti, su simonesgariglia.it.

  • Graph Theory Software, su graphtheorysoftware.com.


.mw-parser-output .navboxborder:1px solid #aaa;clear:both;margin:auto;padding:2px;width:100%.mw-parser-output .navbox thpadding-left:1em;padding-right:1em;text-align:center.mw-parser-output .navbox>tbody>tr:first-child>thbackground:#ccf;font-size:90%;width:100%.mw-parser-output .navbox_navbarfloat:left;margin:0;padding:0 10px 0 0;text-align:left;width:6em.mw-parser-output .navbox_titlefont-size:110%.mw-parser-output .navbox_abovebelowbackground:#ddf;font-size:90%;font-weight:normal.mw-parser-output .navbox_groupbackground:#ddf;font-size:90%;padding:0 10px;white-space:nowrap.mw-parser-output .navbox_listfont-size:90%;width:100%.mw-parser-output .navbox_oddbackground:#fdfdfd.mw-parser-output .navbox_evenbackground:#f7f7f7.mw-parser-output .navbox_centertext-align:center.mw-parser-output .navbox .navbox_imagepadding-left:7px;vertical-align:middle;width:0.mw-parser-output .navbox+.navboxmargin-top:-1px.mw-parser-output .navbox .mw-collapsible-togglefont-weight:normal;text-align:right;width:7em.mw-parser-output .subnavboxmargin:-3px;width:100%.mw-parser-output .subnavbox_groupbackground:#ddf;padding:0 10px














.mw-parser-output .CdAborder:1px solid #aaa;width:100%;margin:auto;font-size:90%;padding:2px.mw-parser-output .CdA thbackground-color:#ddddff;font-weight:bold;width:20%


Controllo di autorità
LCCN (EN) sh85056471 · GND (DE) 4113782-6



InformaticaPortale Informatica

MatematicaPortale Matematica



Estratto da "https://it.wikipedia.org/w/index.php?title=Teoria_dei_grafi&oldid=102894113"










Menu di navigazione



























(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.364","walltime":"0.487","ppvisitednodes":"value":2532,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":25078,"limit":2097152,"templateargumentsize":"value":214,"limit":2097152,"expansiondepth":"value":8,"limit":40,"expensivefunctioncount":"value":2,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":3433,"limit":5000000,"entityaccesscount":"value":1,"limit":400,"timingprofile":["100.00% 400.186 1 -total"," 44.70% 178.872 1 Template:Collegamenti_esterni"," 15.93% 63.744 1 Template:Combinatoria"," 15.03% 60.132 1 Template:Navbox"," 12.05% 48.231 1 Template:Portale"," 12.02% 48.110 1 Template:Interprogetto"," 9.03% 36.153 2 Template:Icona_argomento"," 8.20% 32.826 5 Template:En"," 7.60% 30.403 1 Template:Lingue"," 3.99% 15.981 1 Template:Controllo_di_autorità"],"scribunto":"limitreport-timeusage":"value":"0.254","limit":"10.000","limitreport-memusage":"value":6071051,"limit":52428800,"cachereport":"origin":"mw1311","timestamp":"20190422132429","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"Teoria dei grafi","url":"https://it.wikipedia.org/wiki/Teoria_dei_grafi","sameAs":"http://www.wikidata.org/entity/Q131476","mainEntity":"http://www.wikidata.org/entity/Q131476","author":"@type":"Organization","name":"Contributori ai progetti Wikimedia","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2004-06-22T19:22:07Z","dateModified":"2019-02-21T10:14:01Z","image":"https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg","headline":"branca della geometria combinatoria che si occupa di studiare i grafi, strutture matematiche costituite da vertici collegati fra loro da archi"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":119,"wgHostname":"mw1330"););l18LW8qB DuRldVQcr,pv
mm5mVQv

Popular posts from this blog

Creating centerline of river in QGIS? The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Finding centrelines from polygons in QGIS?Splitting line into two lines with GRASS GIS?Centroid of the equator and a pointpostgis: problems creating flow direction polyline; not all needed connections are drawnhow to make decent sense from scattered river depth measurementsQGIS Interpolation on Curved Grid (River DEMs)How to create automatic parking baysShortest path creation between two linesclipping layer using query builder in QGISFinding which side of closest polyline point lies on in QGIS?Create centerline from multi-digitized roadway lines Qgis 2.18Getting bathymetric contours confined only within river banks using QGIS?

What is the result of assigning to std::vector::begin()? The Next CEO of Stack OverflowWhat are the differences between a pointer variable and a reference variable in C++?What does the explicit keyword mean?Concatenating two std::vectorsHow to find out if an item is present in a std::vector?Why is “using namespace std” considered bad practice?What is the “-->” operator in C++?What is the easiest way to initialize a std::vector with hardcoded elements?What is The Rule of Three?What are the basic rules and idioms for operator overloading?Why are std::begin and std::end “not memory safe”?