Teoria dei grafi

GRAFI ORIENTATI (DIRETTI O ASIMMETRICI)

Un grafo orientato è un tipo di grafo in cui gli archi hanno una direzione specifica.

SUPPORTO SIMMETRICO

Il supporto simmetrico di un grafo orientato è un nuovo grafo che si ottiene rimuovendo le frecce dagli archi e combinando gli archi duplicati.

INTORNO DI GRAFI ORIENTATI

L'intorno di un nodo v include tutti i nodi che sono collegati a v tramite un arco entrante (nodi di arrivo) e tutti i nodi a cui v è collegato tramite un arco uscente (nodi di partenza).

STELLA DI GRAFI ORIENTATI

La stella di un nodo in un grafo orientato si riferisce all'insieme dei suoi archi uscenti e entranti. La notazione δ(v) rappresenta la stella di un nodo v e si ottiene unendo l'insieme dei suoi archi uscenti δ(v) e l'insieme dei suoi archi entranti δ(v). + -(v) rappresenta la stella uscente da v, ovvero tutti gli archi che partono da v.

δ +• dirigono verso altri nodi nel grafo. L'insieme δ (v) rappresenta la stella entrante in v, ovvero tutti gli archi che arrivano a v da altri nodi nel grafo.

ESEMPIO: CAMMINI PERCORSI E CICLI DEI GRAFI ORIENTATI

CAMMINI: Un cammino in un grafo orientato è una sequenza di nodi e archi che connettono un nodo di partenza a un nodo di destinazione. Ogni arco nel cammino deve seguire la direzione specifica del grafo orientato.

PERCORSI: Un percorso in un grafo orientato è un cammino che non contiene nodi ripetuti. Significa che non possiamo visitare lo stesso nodo più di una volta lungo il percorso. Ciò implica che gli archi nel percorso devono essere seguiti in una sola direzione, evitando di tornare indietro ai nodi precedentemente visitati.

CICLI: Un ciclo in un grafo orientato è un percorso chiuso in cui il nodo di partenza e il nodo di destinazione sono lo stesso nodo.

ESEMPIO: Consideriamo il percorso P

relativo al grafo D:

Possiamo avere:

Gli archi diretti (5,1) e (1,2) sono archi in avanti di P

Gli archi diretti (4,2) e (3,4) sono archi all'indietro di P

(Il cammino dell'esempio non è orientato perché non è formato da tutti archi in avanti.)

QUINDI:

In conclusione possiamo dire che:

ESEMPIO: Il percorso P = [{5,1}, {1,3}, {3,4}, {4, 2}] è ORIENTATO perché formato esclusivamente da archi diretti in avanti.

FORTE CONNESSIONE

QUINDI:

Due nodi u e v si dicono fortemente connessi se possiamo raggiungere u partendo da v e possiamo raggiungere v partendo da u, seguendo le direzioni degli archi nel grafo orientato.

ESEMPIO: In questo grafo tutte le coppie di nodi sono fortemente connesse

RAPPRESENTAZIONI

Le rappresentazioni grafiche dei grafi più utilizzate includono:

• La matrice di adiacenza
• La matrice di incidenza
• La lista di adiacenza

Esse consentono una gestione più efficiente e computazionale dei grafi.

ADIACENZA

MATRICE DI

NODI-NODI è una tabella quadrata in cui le righe e le colonne rappresentano i nodi del grafo. Se ci sono collegamenti tra i nodi, viene posto un valore nella cella corrispondente. È utile per identificare le connessioni dirette tra i nodi del grafo.

ESEMPIO: ADIACENZA

MATRICE DI ARCHI-ARCHI è una matrice quadrata in cui le righe e le colonne rappresentano gli archi del grafo. Se due archi sono collegati tra loro, viene posto un valore nella cella corrispondente.

ESEMPIO: INCIDENZA

MATRICE DI NODI-ARCHI (GRAFI NON ORIENTATI) è una matrice rettangolare in cui le righe rappresentano i nodi e le colonne rappresentano gli archi. Se un nodo è collegato a un arco, viene posto un valore nella cella corrispondente, pari a 1; altrimenti si pone 0.

ESEMPIO: INCIDENZA

MATRICE DI NODI-ARCHI (GRAFI ORIENTATI) è una matrice rettangolare in cui le righe rappresentano i nodi e le colonne rappresentano gli archi. Se un nodo è il punto di partenza di un arco si pone 1

sulla cella corrispondente, se il noto è il punto di arrivo di un arco si pone -1 sulla cella corrispondente, altrimenti si pone 0.

ESEMPIO: LISTA DI ADIACENZA

È una rappresentazione basata su una lista di nodi. Per ogni nodo, viene elencato l'insieme dei nodi adiacenti ad esso. È una rappresentazione flessibile e compatta che è molto utile per grafi con molti nodi ma pochi collegamenti.

ESEMPIO: INSIEMI INDIPENDENTI E COPERTURE

INSIEMI MASSIMALI E MASSIMI

Sia U un insieme finito e discreto di elementi e un predicato che esprime una proprietà data.

Spiegazione:

Un insieme massimo è un insieme che soddisfa una determinata proprietà e che non può essere ulteriormente esteso aggiungendo elementi senza violare la proprietà. Non esiste alcun sottoinsieme che soddisfi la proprietà e abbia più elementi dell'insieme massimo.

Un insieme massimale, d'altra parte, è un insieme che soddisfa una determinata proprietà ma che può essere ulteriormente esteso aggiungendo elementi senza violare la proprietà.

determinata proprietà e non può essere ingrandito all'interno dell'insieme più grande senza violare la proprietà. Ciò significa che non esiste alcun altro sotoinsieme contenente propriamente l'insieme massimale che soddisfa la proprietà. In sintesi, un insieme massimo è l'insieme più grande che soddisfa la proprietà, mentre un insieme maximale è l'insieme che non può essere ulteriormente ingrandito all'interno dell'insieme più grande senza violare la proprietà.

ESEMPIO: INSIEMI MINIMALI E MINIMI

Sia U un insieme finito e discreto di elementi e un predicato che esprime una proprietà data.

SPIEGAZIONE: Un insieme minimale è un insieme che soddisfa una determinata proprietà e non contiene alcun sotoinsieme che soddisfi ancora la stessa proprietà. In altre parole, un insieme minimale è l'insieme più piccolo che

soddisfa la proprietà specificata. Un insieme minimo, invece, è un insieme minimale che ha anche il minor numero possibile di elementi rispetto a tutti gli altri insiemi che soddisfano la stessa proprietà. In altre parole, un insieme minimo è l'insieme minimale che ha il minor numero di elementi tra tutti gli insiemi che soddisfano la proprietà.

In sintesi, un insieme minimale è l'insieme più piccolo che soddisfa una determinata proprietà, mentre un insieme minimo è l'insieme minimale che ha il minor numero di elementi rispetto a tutti gli altri insiemi che soddisfano la stessa proprietà.

ESEMPIO: INSIEME INDIPENDENTE

Dato un grafo non orientato G = (V, E), un insieme indipendente è un qualsiasi sottinsieme di nodi S (o di archi M) costituito da elementi mutuamente non adiacenti.

DOVE: Un insieme indipendente massimale di G non è contenuto propriamente in nessun insieme indipendente.

In un grafo non orientato G = (V, E), un insieme indipendente è un sottoinsieme di nodi (o di archi) in cui gli elementi non sono collegati tra loro. Un insieme indipendente può essere chiamato anche "insieme stabile" quando si tratta di nodi e "abbinamento" quando si tratta di archi. Un insieme indipendente massimale è un insieme indipendente che non può essere ulteriormente esteso senza violare la condizione di indipendenza. Un insieme indipendente massimo è l'insieme indipendente di dimensione massima. Questi concetti sono utilizzati per analizzare la struttura dei grafi e risolvere problemi di ottimizzazione.

INSIEME STABILE

CONSIDERAZIONI:

Un insieme stabile, in un grafo non orientato, è un sottoinsieme di nodi in cui nessun nodo è direttamente collegato a un altro nodo dell'insieme. In altre parole,

Gli elementi dell'insieme stabile non hanno archi che li connettono tra loro.

ESEMPIO:

ABBINAMENTO

CONSIDERAZIONI:

QUINDI:

In un grafo non orientato, un abbinamento è un insieme di archi in cui nessun paio di archi condivide un estremo comune. In altre parole, è un insieme di archi che non si sovrappongono tra loro.

ESEMPIO:

ABBINAMENTO SU GRAFI BIPARTITI

QUINDI

Il Teorema di Hall riguarda i grafi bipartiti, che sono grafi con due gruppi separati di nodi. Il teorema dice che, in un grafo bipartito, è possibile trovare un abbinamento che copre completamente un gruppo di nodi (chiamato V1) se ogni sottinsieme di nodi di V1 ha abbastanza vicini nell'altro gruppo di nodi (chiamato V2). In altre parole, per ogni gruppo di nodi che prendiamo da V1, devono esserci abbastanza nodi in V2 che sono collegati ad essi. Se questa condizione è soddisfatta per tutti i possibili gruppi di nodi di V1, allora esiste un abbinamento che copre completamente V1.

COPERTURA

Dato un