Grafo (matematica discreta)

Le definizioni nella teoria dei grafi variano. I seguenti sono alcuni dei modi più basilari di definire i grafi e le strutture matematiche correlate.

GraphEdit

Un grafo (talvolta chiamato grafo indiretto per distinguerlo da un grafo diretto, o grafo semplice per distinguerlo da un multigrafo) è una coppia G = (V, E), dove V è un insieme i cui elementi sono chiamati vertici (singolare: vertex), ed E è un insieme di vertici accoppiati, i cui elementi sono chiamati bordi (talvolta link o linee).

I vertici x e y di un bordo {x, y} sono chiamati punti finali del bordo. Si dice che il bordo unisce x e y e che è incidente su x e y. Un vertice può non appartenere a nessun bordo, nel qual caso non è unito a nessun altro vertice.

Un multigrafo è una generalizzazione che permette a più bordi di avere la stessa coppia di punti finali. In alcuni testi, i multigrafi sono semplicemente chiamati grafi.

A volte, i grafi possono contenere dei loop, che sono bordi che uniscono un vertice a se stesso. Per permettere i loop, la definizione di cui sopra deve essere cambiata definendo i bordi come multi-insiemi di due vertici invece di due insiemi. Tali grafi generalizzati sono chiamati grafi con loop o semplicemente grafi quando è chiaro dal contesto che i loop sono permessi.

Generalmente, si suppone che l’insieme dei vertici V sia finito; questo implica che anche l’insieme dei bordi sia finito. I grafi infiniti sono a volte considerati, ma sono più spesso visti come un tipo speciale di relazione binaria, poiché la maggior parte dei risultati sui grafi finiti non si estendono al caso infinito, o hanno bisogno di una prova piuttosto diversa.

Un grafico vuoto è un grafico che ha un insieme vuoto di vertici (e quindi un insieme vuoto di bordi). L’ordine di un grafo è il suo numero di vertici |V|. La dimensione di un grafo è il suo numero di spigoli E. Tuttavia, in alcuni contesti, come per esprimere la complessità computazionale degli algoritmi, la dimensione è |V| + |E| (altrimenti, un grafico non vuoto potrebbe avere una dimensione 0). Il grado o la valenza di un vertice è il numero di bordi che gli sono incidenti; per i grafi con loop, un loop viene contato due volte.

In un grafo di ordine n, il grado massimo di ogni vertice è n – 1 (o n se sono ammessi i loop), e il numero massimo di bordi è n(n – 1)/2 (o n(n + 1)/2 se sono ammessi i loop).

I bordi di un grafico definiscono una relazione simmetrica sui vertici, chiamata relazione di adiacenza. In particolare, due vertici x e y sono adiacenti se {x, y} è un bordo. Un grafo può essere completamente specificato dalla sua matrice di adiacenza A, che è un n × n {displaystyle n\times n}

matrice quadrata, con Aij che specifica il numero di connessioni dal vertice i al vertice j. Per un grafo semplice, A i j ∈ { 0 , 1 } {displaystyle A_{ij} in \0,1\}}

, che indica rispettivamente disconnessione o connessione, mentre A i i = 0 {\displaystyle A_{ii}=0}

(cioè, un bordo non può iniziare e finire allo stesso vertice). I grafi con autocicli saranno caratterizzati da alcuni o tutti A i i {\displaystyle A_{ii}}

è uguale a un intero positivo, e i multigrafi (con più bordi tra i vertici) saranno caratterizzati da alcuni o tutti A i j {displaystyle A_{ij}

è uguale a un numero intero positivo. I grafi indiretti avranno una matrice di adiacenza simmetrica ( A i j = A j i {displaystyle A_{ij}=A_{ji}}

).

Directed graphEdit

Un grafo diretto o digrafo è un grafo in cui i bordi hanno orientamenti.

In un senso ristretto ma molto comune del termine, un grafo diretto è una coppia G = ( V , E ) {\displaystyle G=(V,E)}

comprendente:

• V {\displaystyle V}
  

  , un insieme di vertici (chiamati anche nodi o punti);

• E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } {\displaystyle E\subseteq \(x,y)\mid (x,y)\in V^{2}};{\textrm {e}}};x\neq y}}}
  

  , un insieme di bordi (chiamati anche bordi diretti, collegamenti diretti, linee dirette, frecce o archi) che sono coppie ordinate di vertici (cioè, un bordo è associato a due vertici distinti).

Per evitare ambiguità, questo tipo di oggetto può essere chiamato proprio un grafo semplice diretto.

Nel bordo ( x , y ) {\displaystyle (x,y)}

diretto da x {\displaystyle x}

a y {displaystyle y}

, i vertici x {\displaystyle x}

e y {displaystyle y}

sono chiamati i punti finali del bordo, x {\displaystyle x}

la coda del bordo e y {\displaystyle y}

la testa del bordo. Si dice che il bordo unisce x {displaystyle x}

e y {displaystyle y}

e di essere incidente su x {\displaystyle x}

e su y {\displaystyle y}

. Un vertice può esistere in un grafico e non appartenere a un bordo. Il bordo ( y , x ) {\displaystyle (y,x)}

è chiamato bordo inverso di ( x , y ) {\displaystyle (x,y)}

. I bordi multipli, non ammessi dalla definizione precedente, sono due o più bordi con la stessa coda e la stessa testa.

In un senso più generale del termine che permette bordi multipli, un grafo diretto è una tripla ordinata G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}

comprendente:

• V {\displaystyle V}
  

  , un insieme di vertici (chiamati anche nodi o punti);

• E {\displaystyle E}
  

  , un insieme di bordi (chiamati anche bordi diretti, collegamenti diretti, linee dirette, frecce o archi);

• ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } {\displaystyle \phi :E\to \(x,y)\mid (x,y)\in V^{2}};{\textrm {e}}};x\neq y}}}
  

  , una funzione di incidenza che mappa ogni bordo a una coppia ordinata di vertici (cioè, un bordo è associato a due vertici distinti).

Per evitare ambiguità, questo tipo di oggetto può essere chiamato appunto multigrafo diretto.

Un loop è un bordo che unisce un vertice a se stesso. I grafi diretti come definiti nelle due definizioni precedenti non possono avere loop, perché un loop che unisce un vertice x {displaystyle x}

a se stesso è il bordo (per un grafo semplice diretto) o è incidente su (per un multigrafo diretto) ( x , x ) {\displaystyle (x,x)}

che non è in { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } {\displaystyle \(x,y)\mid (x,y)\in V^{2}};{\textrm {e}}};x\neq y\}}

. Quindi, per permettere i loop, le definizioni devono essere espanse. Per i grafi semplici diretti, la definizione di E {displaystyle E}

dovrebbe essere modificata in E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } (x,y)\mid (x,y)\in V^{2}}}

. Per i multigrafi diretti, la definizione di ϕ {displaystyle \phi }

dovrebbe essere modificata in ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle \phi :E\to \(x,y)\mid (x,y)\in V^{2}}}

. Per evitare ambiguità, questi tipi di oggetti possono essere chiamati precisamente rispettivamente un grafo semplice diretto che permette i loop e un multigrafo diretto che permette i loop (o un quiver).

I bordi di un grafo semplice diretto che permette dei cicli G {displaystyle G}

è una relazione omogenea ~ sui vertici di G {\displaystyle G}

che è chiamata relazione di adiacenza di G {\displaystyle G}

. In particolare, per ogni bordo ( x , y ) {\displaystyle (x,y)}

, i suoi punti finali x {\displaystyle x}

e y {displaystyle y}

sono detti adiacenti l’uno all’altro, il che è indicato con x {\displaystyle x}

~ y {\displaystyle y}

.

Grafico mistoEdit

Un grafo misto è un grafo in cui alcuni bordi possono essere diretti e alcuni possono essere indiretti. È una tripla ordinata G = (V, E, A) per un grafo semplice misto e G = (V, E, A, ϕE, ϕA) per un multigrafo misto con V, E (i bordi indiretti), A (i bordi diretti), ϕE e ϕA definiti come sopra. I grafi diretti e indiretti sono casi speciali.

Grafo pesatoModifica