Grafico (matematica discreta)

In matematica , e più precisamente nella teoria dei grafi , un grafo è una struttura composta da oggetti in cui sono correlate determinate coppie di oggetti. Gli oggetti corrispondono ad astrazioni matematiche e sono chiamati vertici (o nodi o punti ) e le relazioni tra i vertici sono bordi (o collegamenti o linee ). Distinguiamo tra grafi non orientati , dove i bordi collegano due vertici simmetricamente, e grafi diretti , dove i bordi, chiamati poi frecce , collegano due vertici in modo asimmetrico.

Un grafo è spesso rappresentato da un diagramma sotto forma di un insieme di punti per i vertici, uniti tra loro da linee rette o curve per i bordi, eventualmente provvisto di frecce nel caso di grafi orientati. I grafici sono uno degli oggetti di studio nel campo della matematica discreta .

I grafici sono l'oggetto di base della teoria dei grafi . La parola "  grafico  " fu usata per la prima volta in questo senso da James Joseph Sylvester nel 1878.

Definizioni

Esistono diverse variazioni nella definizione dei grafici nella teoria dei grafi. Le definizioni più comuni sono le seguenti.

Grafico

In un senso ristretto ma molto diffuso del termine, un grafo è una coppia che comprende G = ( V , E )

• V un insieme di vertici (chiamati anche nodi o punti );
• E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} un insieme di bordi (chiamati anche collegamenti o linee ), che sono coppie di vertici (cioè un bordo è associato a due vertici separati).

A scanso di equivoci, questo tipo di oggetto può essere definito appunto un semplice grafo non orientato .

In bordo { x , y } , i vertici x e y sono chiamati le estremità o vertici estremi del bordo. Diciamo che il bordo unisce x ed y ed è incidente su x e y . Un vertice può esistere in un grafico senza un bordo incidente. Un loop è un bordo che unisce un vertice a se stesso. I bordi multipli sono due o più bordi che uniscono gli stessi due picchi.

In un senso più generale del termine che consente più archi, un grafo è una terzina G = ( V , E , ϕ ) che comprende

• V un insieme di vertici (chiamati anche nodi o punti );
• E un insieme di bordi (chiamati anche collegamenti o linee );
• ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} una funzione di incidenza che associa a ciascun bordo una coppia di vertici (cioè un bordo è associato a due vertici distinti).

A scanso di equivoci, questo tipo di oggetto può essere definito appunto un multigrafo non orientato .

I grafici come definiti nelle due definizioni precedenti non possono avere loop, perché un loop che unisce un vertice x è il bordo (per un grafo semplice non orientato) o è incidente su (per un multigrafo non orientato) { x , x } = { x } che è non in {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} . Quindi, per consentire i loop, le definizioni devono essere estese. Per grafici semplici non orientati, E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} deve diventare E ⊆ {{ x , y } | ( x , y ) ∈ V 2 } . Per i multigrafi non orientati, ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} deve diventare ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 } . A scanso di equivoci, questi tipi di oggetti possono essere chiamati precisamente un grafo semplice non orientato con loop e un multigrafo non orientato con loop rispettivamente.

V ed E sono generalmente considerati finiti e molti risultati cessano di essere veri (o hanno affermazioni diverse) per grafi infiniti perché alcuni argomenti di prova non si traducono nel caso infinito. Inoltre, si presume spesso che V sia non vuoto, ma E può essere l'insieme vuoto.

L' ordine di un grafico | V | è il suo numero di vertici. La dimensione di un grafico è | E |, il suo numero di spigoli. Il grado o valenza di un vertice è il numero di bordi incidenti a quel vertice, dove un ciclo conta doppio.

In un grafo semplice non orientato di ordine n , il grado massimo di un vertice è n - 1 e la dimensione massima del grafo è n ( n - 1) / 2 .

I bordi E di un grafo non orientato G inducono una relazione binaria simmetrica ~ V chiamato il rapporto di adiacenza di G . In particolare, per ogni arco { x , y } , si dice che i suoi vertici estremi x e y sono adiacenti l' uno all'altro, che è indicato con x ~ y .

Grafico orientato

Un grafico orientato è un grafico in cui i bordi hanno un orientamento.

In un senso ristretto ma molto diffuso del termine, un grafo orientato è una coppia G = ( V , A ) (a volte G = ( V , E ) ) comprendente

• V un insieme di vertici (chiamati anche nodi o punti );
• A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y } un insieme di frecce (chiamate anche bordi orientati - a volte semplicemente bordi con l'insieme corrispondente denominato E invece di A -, collegamenti orientati o linee orientate ), che sono coppie di vertici distinti ( cioè una freccia è associata a due vertici distinti).

A scanso di equivoci, questo tipo di oggetto può essere definito appunto un grafo semplice orientato .

Nella freccia ( x , y ) orientata da x a y , x è chiamata la coda della freccia e y la testa della freccia. La freccia ( y , x ) è chiamata freccia inversa di ( x , y ) .

In un senso più generale del termine che consente più frecce, un grafo orientato è una terzina G = ( V , A , ϕ ) (a volte G = ( V , E , ϕ ) ) che include

• V un insieme di vertici (chiamati anche nodi o punti );
• Ha una serie di frecce (chiamate anche bordi orientati - a volte solo bordi con il corrispondente insieme denominato E invece di A -, collegamenti orientati o linee orientate );
• ϕ : A → {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} una funzione di incidenza che associa a ciascuna freccia una coppia di vertici distinti (cioè una freccia è associata a due vertici distinti).

A scanso di equivoci, questo tipo di oggetto può essere definito appunto un multigrafo orientato .

I grafi orientati come definiti nelle due definizioni precedenti non possono avere loop, perché un loop che unisce un vertice x è la freccia (per un grafo diretto semplice) o è incidente su (per un multigrafo diretto) ( x , x ) che non è in { ( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} . Quindi, per consentire i loop, le definizioni devono essere estese. Per grafici orientati semplici, A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} deve diventare A ⊆ V 2 . Per i multigrafi orientati, ϕ : A → {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} deve diventare ϕ : A → V 2 . A scanso di equivoci, questi tipi di oggetti possono essere chiamati appunto un semplice grafo orientato con loop e un multigrafo diretto con loop (o una faretra ) rispettivamente.

Un semplice grafo orientato con cicli è una relazione omogenea (una relazione binaria tra un insieme e se stesso). Un semplice grafo orientato con passanti G = ( V , A ) è detta simmetrica se per ogni freccia A , corrispondente inversa freccia anche in A .

Grafico misto

Un grafico misto è un grafico composto da bordi non orientati e bordi diretti. È una tripletta G = ( V , E , A ) per un grafo misto semplice e G = ( V , E , A , ϕ E , ϕ A ) per un multigrafo misto con V , E , A , ϕ E e ϕ A definito come sopra. I grafici orientati e non orientati sono casi speciali.

Grafico ponderato

Un grafico ponderato o una rete è un grafico in cui ogni bordo porta un numero (il suo peso). Questi pesi possono rappresentare, ad esempio, costi, lunghezze o portate, a seconda del problema trattato. Questi grafici sono comuni in vari contesti, come il problema del percorso più breve o il problema del venditore ambulante .

Tipi di grafici

Grafico asimmetrico

Un grafico asimmetrico (in inglese "  oriented graph  " ) è un grafico orientato dove al massimo una delle coppie ( x , y ) e ( y , x ) è una freccia del grafico. Un tale grafico è senza loop. Possiamo vederlo come il risultato della scelta di un orientamento per ogni bordo di un grafo non orientato senza loop.

Grafico regolare

Un grafo regolare è un grafo (non orientato) in cui tutti i vertici hanno lo stesso grado. Se questo grado è k , parliamo anche di un grafo regolare k .

Grafico completo

Un grafo completo è un grafo semplice i cui vertici sono tutti adiacenti l'uno all'altro, vale a dire in modo tale che qualsiasi coppia di vertici distinti sia collegata da un bordo. Se il grafo è orientato , diciamo che è completo se ogni coppia di vertici è collegata esattamente da due frecce (una in ogni direzione).

Grafo finito

Un grafo finito è un grafo il cui insieme di vertici è finito (e quindi anche l'insieme di archi). Altrimenti, è un grafico infinito . Molto spesso, i grafici considerati sono tacitamente considerati finiti; se sono infinite, viene specificato esplicitamente.

Grafico correlato

Un grafo connesso è un grafo non orientato in cui qualsiasi coppia di vertici è collegata da una catena. Un grafo orientato, è connesso se è connesso il grafo non orientato ottenuto dimenticando gli orientamenti dei bordi. È fortemente connesso se una qualsiasi coppia di vertici è collegata da un percorso, quindi se per qualsiasi coppia ( x , y ) di vertici, c'è un percorso da x a y e un percorso da y a x . Un grafo connesso a k vertici è un grafo che ha almeno k +1 vertici e che rimane ancora connesso dopo aver rimosso k –1; allo stesso modo, un grafo connesso con k-edge è un grafico che rimane connesso quando rimuoviamo k - 1 archi da esso.

Grafico bipartito

Un grafo bipartito è un grafico il cui insieme di nodi può essere suddiviso in due gruppi X e Y in modo che il bordo non è tra due vertici di X o tra due vertici di Y . Equivalentemente, un grafo bipartito è un grafo il cui numero cromatico è 2.

Un grafo bipartito completo è un grafo bipartito in cui tutti i vertici di X sono collegati a tutti i vertici di Y e viceversa.

Catena

Un grafo è una catena di ordine n ≥ 2 se è composto da vertici n che possono essere numerati in modo tale che gli archi siano { v i , v i +1 } per i = 1, 2,…, n - 1. Una catena è, in modo equivalente, un grafo connesso i cui vertici sono di grado 2 tranne due che sono di grado 1. Una catena in un grafo è un sottografo parziale di questo grafo.

Grafico planare

Un grafico planare è un grafico che può essere disegnato nel piano (o su una sfera) senza che due bordi si intersechino.

Grafico del ciclo

Un ciclo di ordini o un grafo a n cicli è un grafo i cui vertici possono essere numerati in modo che i bordi siano le coppie per più il bordo . Un grafo a ciclo può essere caratterizzato come un grafo connesso tutti i cui vertici hanno grado 2. non≥3{\ displaystyle n \ geq 3}v1,...,vnon{\ displaystyle v_ {1}, \ ldots, v_ {n}}[vio,vio+1]{\ displaystyle [v_ {i}, v_ {i + 1}]}io=1,...,non-1{\ displaystyle i = 1, \ ldots, n-1}[vnon,v1]{\ displaystyle [v_ {n}, v_ {1}]}

Albero

Un albero è un grafo connesso aciclico.

Una foresta è un grafo aciclico, vale a dire un'unione disgiunta di uno o più alberi.

Altre classi

Altre classi di grafici includono:

• Il grafico di Petersen e le sue generalizzazioni;
• Grafici perfetti ;
• Cografi ;
• Grafici cordali ;
• altri grafici classificati in base al loro gruppo di automorfismi  : grafico vertice-transitivo , grafico simmetrico , e il grafico distanza-transitivo  ;
• Grafo fortemente regolare e loro generalizzazioni; grafico a distanza regolare .

Proprietà del grafico

Due bordi di un grafico sono adiacenti se hanno un vertice in comune. Due archi di un grafo orientato sono consecutivi se la fine del primo arco è l'inizio del secondo. Allo stesso modo, due vertici sono adiacenti se sono estremità dello stesso bordo (dello stesso arco). Si dice che un bordo e un vertice adiacente siano incidenti l'uno con l'altro.

Il grafo formato da un unico vertice e senza spigoli è spesso chiamato banale  ; il grafico senza vertice e bordo è talvolta chiamato anche grafo nullo .

Un grafo è etichettato ai vertici se ogni vertice ha un'etichetta. Un grafico è etichettato ai bordi se ogni bordo ha un'etichetta. Nei problemi di enumerazione o biiezione, possiamo considerare grafici etichettati o senza etichetta. Un grafico i cui vertici (o bordi) sono etichettati con colori è un grafico colorato.

Proprietà di centralità di un grafico

Nell'analisi dei grafici, la centralità misura la rilevanza e l'importanza di un vertice. Distinguiamo:

• la centralità del grado che è il numero di spigoli incidenti a un vertice;
• la centralità della prossimità che è l'inverso della somma delle distanze a tutti gli altri vertici;
• la centralità dell'intermediazione che è il numero totale di cammini minimi passanti per un vertice.

Altre misure sono l' eccentricità di un vertice che è la distanza massima da qualsiasi altro vertice, il diametro di un grafico o il raggio .

Operazioni sui grafici

Le varie operazioni che producono nuovi grafici da dati grafici possono essere raggruppate in:

• operazioni unarie , che creano un nuovo grafico da uno vecchio, come:
  • Contrazione del bordo ,
  • Grafico a linee ,
  • Doppio grafico ,
  • Grafico complementare ,
  • Riscrittura di grafici .
• operazioni binarie , che creano un nuovo grafico da due vecchi, come:
  • unione disgiunta di grafici,
  • Prodotto cartesiano ,
  • prodotto tensoriale,
  • prodotto forte,
  • prodotto lessicografico,
  • grafo serie-parallelo.

Applicazioni

• Nella teoria delle categorie , una categoria può essere rappresentata da un multigrafo orientato i cui vertici rappresentano gli oggetti e gli spigoli rappresentano i morfismi . Un funtore tra le categorie induce un morfismo di grafici .
• In informatica , i grafi diretti vengono utilizzati per rappresentare nozioni come grafi concettuali , automi finiti e molte altre strutture discrete.
• Una relazione binaria R su un insieme X definisce un grafo orientato (e viceversa). C'è una freccia da x a y nel grafico se e solo se xRy .
• Un grafico può modellare le informazioni sui social network , come la nozione di "follower" in Twitter .
• Esempi di grafi diretti regolari sono i grafi di Cayley di gruppi finitamente generati, o il grafo dei cosets Schreier  (en) .
• In chimica ed in particolare nella rappresentazione semplificata dei legami tra atomi che formano una molecola, sono largamente utilizzati grafi in genere non orientati ma con più spigoli.

Estensioni

I grafici si generalizzano in diverse direzioni:

• In un ipergrafo , un bordo può connettere più di due vertici.
• Un grafo non orientato può essere visto come un complesso simpliciale di cui i 1- Simplex sono i bordi e gli 0-Simplex i vertici. In questo aspetto, i complessi simpliciali sono generalizzazioni di grafici a dimensioni superiori.
• Qualsiasi grafico fornisce anche un matroide .
• Nella teoria dei modelli , un grafo è solo una struttura logica . In questo contesto, non c'è limite al numero di archi che può essere qualsiasi numero cardinale .
• In bioinformatica , l' analisi dei grafici di potenza  (in) ha introdotto grafici specifici (i "  grafici di potenza  " ) come alternativa per la rappresentazione di grafici non orientati.
• Nei sistemi di informazione geografica , le reti geometriche sono modelli vicini ai grafici e prendono in prestito dalla teoria dei grafi molti concetti per l'analisi spaziale su reti stradali o benchmark di utilizzo.

Note e riferimenti

1. Trudeau 1993 , p.  19: "  Un grafo è un oggetto costituito da due insiemi chiamati il ​​suo insieme dei vertici e il suo insieme degli archi  " .
2. In: JJ Sylvester, "  Chimica e algebra  ", Nature , vol.  17,7 febbraio 1878, p.  284: "Ogni invariante e covariante diventa così esprimibile da un grafo esattamente identico a un diagramma di Kekuléan o chemicografo." ( DOI  10.1038 / 017284a0 , leggi online ). e JJ Sylvester, "  Su un'applicazione della nuova teoria atomica alla rappresentazione grafica degli invarianti e delle covarianti della quantica binaria, - con tre appendici  ", American Journal of Mathematics, Pure and Applied ' , vol.  1, n o  1,1878, p.  64–90 ( DOI  10.2307 / 2369436 , leggi in linea ).
3. Gross e Yellen 2004 , p.35 .
4. (in) Edward A. Bender e S. Gill Williamson , Lists, Decisions and Graphs: With an Introduction to Probability ,2010, 251  p. ( leggi in linea ) , p.  148
5. Ad esempio ( Iyanaga e Kawada 1977 , p.  234) o ( Biggs 1993 , p.  4).
6. (a) Edward A. Bender e S. Gill Williamson , Liste, decisioni e grafici: Con un'Introduzione alla probabilità ,2010, 251  p. ( leggi in linea ) , p.  149
7. Ad esempio ( Graham et. Al., 1995 , p.  5).
8. (in) Edward A. Bender e S. Gill Williamson , Lists, Decisions and Graphs: With an Introduction to Probability ,2010, 251  p. ( leggi in linea ) , p.  161
9. Strang 2005 .
10. Fletcher, Hoyle e Patty 1991 , p.  463: Un grafico ponderato è un grafico in cui un numero w (e) , chiamato il suo peso , è assegnato a ciascun arco e .
11. Xingqin Qi , Eddie Fuller , Qin Wu e Yezhou Wu , "  Centralità laplaciana: una nuova misura di centralità per reti ponderate  ", Scienze dell'informazione , vol.  194,Luglio 2012, p.  240–253 ( ISSN  0020-0255 , DOI  10.1016 / j.ins.2011.12.027 ).
12. Martin Grandjean , "  A social network analysis of Twitter: Mapping the digital humanities community  ", Cogent Arts & Humanities , vol.  3, n o  1,2016, p.  1171458 ( DOI  10.1080 / 23311983.2016.1171458 , leggi online )
13. Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang e Reza Bosagh Zadeh WTF: The who-to-follow system su Twitter , Atti della 22a conferenza internazionale sul World Wide Web . DOI : 10.1145 / 2488388.2488433 .

Appendici

Bibliografia

Lavori generali

Tutti i libri di testo di matematica discreta contengono un trattamento di grafici:

• Peter Fletcher , Hughes Hoyle e C. Wayne Patty , Foundations of Discrete Mathematics , Boston, PWS-KENT Pub. Co.,1991, 781  p. ( ISBN  0-534-92373-9 )
• Ronald L. Graham, Martin Grötschel e Lovász Lovász (direttore), Handbook of Combinatorics , MIT Press,1995( ISBN  0-262-07169-X )
• Shôkichi Iyanaga e Yukiyosi Kawada, Dizionario enciclopedico di matematica , MIT Press,1977( ISBN  0-262-09016-3 )
• Gilbert Strang , Algebra lineare e sue applicazioni , Brooks Cole,2005, 4 °  ed. , 487  p. ( ISBN  0-03-010567-6 , leggi online ).
• (en) Daniel Zwillinger , Tabelle e formule matematiche standard CRC , Boca Raton / Londra / New York ecc., Chapman & Hall / CRC,27 novembre 2002, 31 °  ed. , 910  p. ( ISBN  1-58488-291-3 )

Lavori specifici

Molti libri si concentrano sulla teoria dei grafi:

• R. Balakrishnan e K. Ranganathan, A Textbook of Graph Theory , New York, Springer-Verlag, coll.  "Universitext",2012, xiii + 292  p. ( ISBN  978-1-4614-4528-9 , DOI  10.1007 / 978-1-4614-4529-6 , leggi online )
• Claude Berge, Teoria dei grafi e sue applicazioni , Parigi, University Mathematics Collection,1963, 2 °  ed. , viii + 267  p. ( SUDOC  007608756 )
• (en) Norman Biggs , Teoria dei grafi algebrici , Cambridge, Cambridge University Press,1993, 2 °  ed. , 205  p. ( ISBN  0-521-45897-8 )
• (en) Béla Bollobás , Modern Graph Theory , New York / Berlino / Parigi, Springer,12 agosto 2002, 1 °  ed. , 394  p. ( ISBN  0-387-98488-7 )
• Jørgen Bang-Jensen e Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications , Springer-Verlag,2000( leggi online )
• Reinhard Diestel, Teoria dei grafi , Springer, coll.  "Testi per laureati in matematica" ( n o  173)agosto 2016( Repr.2010  , 2005, 2000, 1997), 5 °  ed. , 447  p. ( ISBN  978-3-662-53621-6 e 978-3-96134-005-7 , presentazione online , leggi online )
• (en) Jonathan L. Gross e Jay Yellen, Teoria dei grafi e sue applicazioni , Boca Raton (Florida) / Londra / New York ecc., CRC Press,30 dicembre 1998, 585  p. ( ISBN  0-8493-3982-0 , leggi online )
• Jonathan L. Gross e Jay Yellen (editori), Manuale di teoria dei grafi , CRC Press ,2004, 1192  p. ( ISBN  978-1-58488-090-5 , leggi online ).
• Frank Harary , Teoria dei grafi , Addison Wesley Publishing Company,Gennaio 1995( ISBN  0-201-41033-8 )
• Richard J. Trudeau , Introduzione alla teoria dei grafi , New York, Dover Publications ,1993, 209  p. ( ISBN  978-0-486-67870-2 , presentazione online )

Articoli Correlati

• Grafico concettuale
• Doppio grafico
• Glossario di teoria dei grafi
• Grafico (tipo astratto)
• Database orientato ai grafici
• Tracciatura di grafici
• Teoria dei grafi
• Hypergraph
• Pubblicazioni importanti in teoria dei grafi
• Teoria della rete

link esterno

• (en) Eric W. Weisstein , "  Graph  " , su MathWorld
• Avviso in un dizionario o in un'enciclopedia generale  : Brockhaus Enzyklopädie