proprietà dei grafi

• condizioni che certi grafi rispettano e altre no
• grafi derivati da altri
• grafi correlati con altri

tutte condizioni che si possono scrivere in modo matematico
a partire dalla definizione formale di grafo

definizione matematica di grafo

grafo orientato:

un grafo è una coppia (N,E) dove:
N è un qualsiasi insieme di elementi
E è un insieme di coppie di elementi di N

grafo non orientato:
stessa cosa, ma E sono insiemi di cardinalità due

grafi completi

un grafo è completo se ogni nodo è collegato a ogni altro

generalmente si assume grafo non orientato

esempi di grafi completi e non completi

K_m è il grafo completo di m nodi

esercizio

disegnare il grafo completo di due nodi

soluzione

esercizio

dire se questo grafo è completo

soluzione

è completo:
se si prendono due nodi qualsiasi, si vede che c'è un arco

esercizio

dire se questo grafo è completo

soluzione

grafo non completo

manca l'arco fra 2 e 3

completezza, in termini matematici

un grafo può essere completo o meno
condizione che si può scrivere come una formula matematica
a partire dalla espressione matematica (N,E) di grafo

formula che dice la completezza

(N,E) completo iff
∀ x ∈ N . ∀ y ∈ N . (x,y) ∈ E

un grafo è completo
se e solo se ogni nodo x ha una freccia
verso ogni altro nodo y

condizione matematica che è vera per i grafi completi
verrà data per quasi tutte le altre proprietà dei grafi

formula alternativa per la completezza

(N,E) completo iff
E = N × N

prodotto cartesiano
tutte le coppie di nodi

formule matematiche

per le successive proprietà:
la formula viene prima richiesta come esercizio

si possono usare:

• operatori proposizionali: ∧, ∨, ¬, →, ↔
• operatori insiemistici: ⊂, ⊆, ×
  |S| è il numero di elementi dell'insieme S
• numeri e operatori numerici
• quantificatori ∃, ∀
• variabili che rappresentano nodi, archi, insiemi

provare davvero a farli come esercizio!

proprietà

dimostare che K_n ha
n + (n-1) + … 1 archi

assumendo che questi grafi contengano anche tutti i cappi

dimostrazione

dimostrazione per induzione:

caso base

K₁ ha un arco

induzione

si assume che K_n-1 abbia (n-1) + … 1 archi
si dimostra che K_n ha n + (n-1) + … 1 archi

caso base

K₁ è il grafo
con un nodo 1
e tutti gli archi possibili

({1}, E)

per definizione: E = N × N
in questo caso: N={1}

({1}, {1} × {1}) = ({1}, {(1,1)})

un arco, cvd

induzione, graficamente

K_n si ottiene aggiungendo il nodo n a K_n-1
e collegandolo a tutti
incluso se stesso (i cappi non sono disegnati)

gli archi di K_n-1 sono (n-1) + … + 1 per induzione

si aggiungono gli (n-1) archi fra n e n-1,…,1
e il cappio su n

totale n + (n-1) + … + 1

induzione, in formule

K_n = ({1,…,n}, {1,…,n} × {1,…,n}) =
({1,…,n}, {1,…,n-1} ∪ {n} × {1,…,n-1} ∪ {n}) =
({1,…,n}, ({1,…,n-1} × {1,…,n-1} ) ∪ ({1,…,n-1} × {n}) ∪ ( {n} × {1,…,n-1} ) ∪ ( {n} × {n}) =

la prima parte {1,…,n-1} × {1,…,n-1} sono gli archi di K_n-1
quindi (n-1) + … 1, per induzione

si aggiungono:

• due volte 1 × (n-1) archi orientati
  come 1 × (n-1) archi non orientati
• 1 × 1 cappio

((n-1) + … 1) + (n-1) + 1 = (n-1) + … 1 + n = n + (n-1) + … 1 + n

grafo bipartito

due gruppi di nodi

ogni nodo del primo è collegato solo a qualcuno dell'altro
a nessuno del suo stesso gruppo

un nodo può anche non essere collegato a nessuno dell'altro gruppo
oppure a tutti
oppure a qualcuno

vista in altro modo: non è collegato a nessuno del suo gruppo

esempio di grafo bipartito

altro esempio di grafo bipartito

unico grafo, disconnesso
anche bipartito: gruppi {3,5} e {1,2,4}

esercizio

è un grafo bipartito?

soluzione

i due gruppi non sono evidenti
ma ci sono

nessun arco fra due nodi dello stesso gruppo

esercizio

mostrare due grafi bipartiti
entrambi con i due gruppi di uno e quattro nodi

soluzione

gruppo di un nodo
gruppo di quattro
nessun collegamento fra i quattro

stessi gruppi
ma non tutti gli archi

formula matematica dei grafi bipartiti

esercizio: esprimere la condizione di grafo bipartito come formula matematica

(N,E) bipartito se e solo se
…

simboli che possono servire: ∀, ∃, ∈, ∉ \,

bipartito, formale ma non matematico

(N,E) bipartito se e solo se
esiste un sottoinsieme di nodi tale che
due nodi del sottoinsieme non sono collegati
e nemmeno due nodi che non sono nel sottoinsieme

bipartito, formula

(N,E) bipartito se e solo se
∃ M ⊆ N . (∀ x ∈ M . ∀ y ∈ M . (x,y) ∉ E) ∧ (∀ x ∈ N \ M . ∀ y ∈ N \ M . (x,y) ∉ E)

esiste un insieme N tale che
due nodi x, y di N non sono mai collegati
e nemmeno due nodi di N \ M

bipartito, altra formula

(N,E) bipartito se e solo se
∃ M ⊆ N . ∀ L ∈ {M, N\M}. ∀ x ∈ L . ∀ y ∈ L . (x,y) ∉ E

alternativa alla precedente
stessa condizione

bipartito, ulteriore formula

(N,E) bipartito se e solo se
∃ M ⊆ N . E ⊆ (M × (N \ M)) ∪ ((N \ M) × N)

M × (N \ M) è l'insieme delle coppie
in cui il primo elemento è in M
e il secondo no

grafo bipartito completo

non è bipartito + completo
è una restrizione di bipartito

due gruppi
ogni nodo di un gruppo è collegato a tutti quelli dell'altro
e a nessuno del suo

esercizio

disegnare K₁₃

soluzione

K₁₃ ha due gruppi di nodi
uno singolo
uno con tre nodi

il singolo nodo da una parte
è collegato ai tre dell'altra

formula dei grafi bipartiti completi

(N,E) è un grafo bipartito completo
se e solo se
…

completare

formula dei grafi bipartiti completi

(N,E) è un grafo bipartito completo
se e solo se
∃ M ⊆ N . ∀ x ∈ N . ∀ y ∈ N . (x,y) ∈ E ⇔ (x ∈ M ∧ y ∈ N \ M) ∨ (x ∈ N \ M ∧ y ∈ M)

due nodi sono collegati
se e solo se
appartengono a due gruppi diversi

stessa formula con ⇒ al posto di ⇔:
grafo bipartito, completo o meno

altra formula dei grafi bipartiti completi

(N,E) bipartito se e solo se
∃ M ⊆ N . E = (M × (N \ M)) ∪ ((N \ M) × N)

nomi dei grafi bipartiti completi

K_nm è il grafo bipartito completo
con il primo gruppo di n nodi e il secondo di m nodi

sottografo

solo alcuni nodi
3, 5, 6, 7

solo alcuni degli archi che li collegano
non tutti

esercizio

i due grafi che seguono sono o meno sottografi di quello qui sopra?

primo grafo

è un sottografo

sottoinsieme di nodi: sì

{1,2,3} ⊆ {1,2,3,4,5}

sottoinsieme di archi: sì

{(3,1), (1,2)} ⊆ {(3,1),(1,2),(1,4),(2,3),(4,5)}
non importa se manca l'arco (2,3)

secondo grafo

non è un sottografo

sottoinsieme di nodi: sì

{1,2,3} ⊆ {1,2,3,4,5}
questa parte è rispettata

sottoinsieme di archi? no

{(3,1), (1,2), (3,2)} ⊈ {(3,1),(1,2),(1,4),(2,3),(4,5)}
contiene (3,2)
che non c'è nel grafo di partenza
(che contiene invece (2,3))

formula per i sottografi

(N',E') è sottografo di (N,E)
se e solo se
…

scrivere la formula

formula per i sottografi

(N',E') è sottografo di (N,E)
se e solo se
(N' ⊆ N) ∧ (E' ⊆ (N' × N') ∩ E)

sottografo indotto

sottografo indotto da alcuni nodi
grafo con quei nodi e tutti gli archi che li collegano

esercizio

i due grafi che seguono sono sottografi indotti?

primo grafo

non è un sottografo indotto
solo un sottografo (non indotto)
contiene i nodi 2 e 3
ma non l'arco da 2 a 3

secondo sottografo

è un sottografo indotto
contiene i nodi 1, 3 e 4
e tutti gli archi fra loro nel grafo di partenza: (1,2) e (1,4)

formula per i sottografi indotti

(N',E') è il sottografo indotto da N' su (N,E)
se e solo se
…

completare la formula

formula per i sottografi indotti

(N',E') è il sottografo indotto da N' su (N,E)
se e solo se
(N' ⊆ N) = (E' ⊆ (N' × N') ∩ E)

uguale al posto di contenuto

fusione di nodi

unico nodo al posto di due
con gli archi di entrambi
nelle stesse direzioni

esercizio

({1,2,3,4,5}, {(1,2), (2,4), (2,5), (3,1), (3,5), (5,4)})

fondere i nodi 2 e 3:

soluzione

({1,2,3,4,5}, {(1,2), (2,4), (2,5), (3,1), (3,5), (5,2), (4,3)})

archi entranti in 2 e in 3:
(1,2), (5,2) e (4,3)
entrano nel nuovo nodo

archi uscenti da 2 e da 3:
(2,4), (2,5), (3,1) e (3,5)
escono dal nuovo nodo

({1,6,4,5}, {(1,6), (6,4), (6,5), (6,1), (6,5), (5,6), (4,6)})

soluzione, modo più semplice

({1,2,3,4,5}, {(1,2), (2,4), (2,5), (3,1), (3,5), (5,2), (4,3)})

si rimpiazzano 2 e 3 con 6

formula della fusione

(N',E') è il risultato della fusione
dei nodi n ed m in f nel grafo (N,E)
se e solo se
(N' = N \ {n,m} ∪ {f}) ∧ ( E' = (E ∩ N' × N') ∪ {(f,o) | (n,o) ∈ E} ∪ {(f,o) | (m,o) ∈ E} ∪ {(o,f) | (o,n) ∈ E} ∪ {(o,f) | (o,m) ∈ E} )

grafo minore

un grafo è minore di un altro se si ottiene da questo per:

• rimozione archi
• rimozione nodi isolati
• fusione nodi

esempio

grafo di partenza

fusione dei nodi 2 e 3

eliminazione di archi

eliminazione del nodo isolato 1

questo è un minore del grafo di partenza

esercizio

i tre grafi qui sotto sono minori del grafo di sopra?

               

primo grafo

eliminare gli archi (2,3) e (3,1)

eliminare il nodo isolato 3

secondo grafo

fusione dei nodi 2 e 3 nel nodo 4

terzo grafo

non è un minore

viene introdotto il nuovo arco (2,1)

planarità

un grafo è planare se si può disegnare su un piano senza incroci di archi

teoremi di Kuratowski e Wagner

un grafo è planare se e solo se non ha come minore né K₅ né K₃₃

teorema di Robertson e Seymour

generalizza il teorema di Kuratowski

se una proprietà si trasmette da un grafo a tutti i suoi minori (es. planarità)
allora esiste un insieme finito di grafi (es. {K₅,K₃₃})
tale per cui
un grafo ha la proprietà se e solo se non ha nessuno di quei grafi come minore

grafi isomorfi

due grafi sono isomorfi se sono lo stesso grafo a parte i nomi dei nodi

come sempre, le posizioni nel disegno non contano

stesso grafo, disegno diverso
sempre isomorfo

formula dell'isomorfismo

esiste una funzione biiettiva…

possibile scrivere la formula, ma complicato

grafi bipartiti, isomorfi e sottografi

proprietà: un grafo è bipartito se e solo se
è isomorfo a un sottografo di K_nm per qualche intero n ed m

dimostrazione formale possibile

grado di nodo

grafo non diretto:
numero di archi incidenti

grafo diretto:
grado uscente,
grado entrante

formule per i gradi di un nodo

k è il grado uscente del nodo n nel grafo (N,E)
se e solo se
…

suggerimento:
|S| indica il numero di elementi di un insieme S

formule per i gradi di un nodo

k è il grado uscente del nodo n nel grafo (N,E)
se e solo se
k = |{(n,s) ∈ E}|

grado entrante: stessa formula con (s,n)

grafi k-regolari

tutti i nodi hanno grado k

percorso in un grafo

sequenza di archi da a a b

formula per l'esistenza di un percorso

la sequenza di nodi n₁, …, n_m
è un percorso dal nodo a al nodo b nel grafo (N,E)
se e solo se
…

formula per l'esistenza di un percorso

la sequenza di nodi n₁, …, n_m
è un percorso dal nodo a al nodo b nel grafo (N,E)
se e solo se
a=n₁ ∧ b=n_m ∧ ∀ i ∈ {1,…,m-1} . (n_i,n_i+1) ∈ E

cicli

un ciclo è un percorso n₁, …, n_n con n₁ = n_m

proprietà dei cicli

un grafo è bipartito
se e solo se
non ha cicli di lunghezza dispari

dimostrazione?

dimostrazione della proprietà

nei due versi:

1. se ha un ciclo di lunghezza dispari, allora non è bipartito
2. se è bipartito, non ha cicli di lunghezza dispari

se ha cicli dispari, non è bipartito

ciclo dispari n₁, …, n_2*m+1, n₁
si classifica come dispari perchè contiene un numero dispari di nodi

n₁ va nel primo gruppo

n₂ va nel secondo

per induzione: i nodi di indice dispari vanno nel primo gruppo

n_2*m+1 è nel primo gruppo

il successivo è n₁, secondo gruppo

non è bipartito

se è bipartito, non ha cicli dispari

se non ha cicli, non ha nemmeno cicli dispari

altrimenti, ha dei cicli
sia n₁, n₂, …, n_m uno qualsiasi di questi cicli

si supponga che n₁ sia nel primo gruppo
l'altro caso è simmetrico

dato che il grafo è bipartito
e che n₂ è collegato
è nel secondo gruppo

per induzione, i nodi di indice dispari sono nel primo gruppo
quelli di indice pari nel secondo

dato che il percorso è un ciclo
esiste un arco (n_m, n₁)

dato che il grafo è bipartito, i due nodi sono in gruppi diversi
quindi n_m è nel secondo gruppo

quindi ha indice pari

ciclo Hamiltoniano

un ciclo che contiene tutti i nodi del grafo, senza ripetizioni

esempio di ciclo Hamiltoniano

ciclo 1,2,5,4,3

il ciclo Hamiltoniano, evidenziato

grafo connesso

esiste percorso che collega ogni nodo a con ogni nodo b

formula del grafo connesso

(N,E) è connesso
se e solo se
∀ a ∈ N . ∀ b ∈ N . &exists; n₁ ∈ N . … &exists; n_m ∈ N . (a = n₁) ∧ (b = n_m) ∧ ∀ i ∈ {1,…,m-1} . (n_i,n_i+1) ∈ E

esercizio

disegnare un grafo connesso di sei nodi che contiene solo sei archi

soluzione

esercizio

un grafo connesso di n nodi non può contenere meno di n archi

dimostrarlo, informalmente

soluzione

ogni nodo deve essere connesso agli altri

almeno un arco uscente per ogni nodo

grafo ciclico e aciclico

un grafo è ciclico se contiene almeno un ciclo
altrimenti è aciclico

formula del grafo ciclico

simile a quella del grafo connesso
con l'esistenza di un percorso da un nodo a se stesso
invece dell'esistenza di tutti i percorsi da ogni nodo a ogni altro

esercizio

disegnare un grafo cicliclo
che contiene anche una sorgente (nodo senza predecessori)
e un pozzo (nodo senza successori)

soluzione

ciclo 1,2,3
sorgente 4
pozzo 5

ciclico = esiste un ciclo
non vuol dire che il ciclo deve comprendere tutti i nodi
e nemmeno che tutti i nodi sono in un ciclo

un grafo ciclico può anche non essere connesso!

esempio di grafo ciclico disconnesso

ciclo 2 → 5 → 2

da 3 non si arriva a 4

copertura

copertura di un grafo: insieme di nodi
tale che ogni arco contiene almeno un nodo dell'insieme

esempio di copertura

una copertura: nodi 1,2,3,5

graficamente: tutti gli archi entrano, escono o sono contenuti nella copertura

esercizio: copertura?

è una copertura?

risposta

non è una copertura:
l'arco (2,3) è scoperto
né 2 né 3 sono nell'insieme

esercizio: copertura?

è una copertura?

risposta

è una copertura:

per ogni arco (a,b)
almeno uno tra a e b è nell'insieme

esercizio

trovare un'altra copertura che contiene solo due nodi

soluzione

formula della copertura

C è una copertura di (N,E)
se e solo se
…

esercizio: completare

formula della copertura

C è una copertura di (N,E)
se e solo se
C ⊆ N ∧ ∀ (a,b) ∈ E . a ∈ C ∨ b ∈ C

cricca

sottoinsieme di nodi
ognuno collegato agli altri

esempio

una cricca di tre nodi è {1,2,4}

esercizio

trovare una cricca di quattro nodi

soluzione

esercizio

trovare la cricca più grande

risposta

due nodi collegati fra loro

non ci sono cricche più grandi…

cricche più grandi?

2 non è collegato a 6

formula della cricca

C è una cricca di (N,E)
se e solo se
…

esercizio: completare

formula della cricca

C è una cricca di (N,E)
se e solo se
C ⊆ N ∧ ∀ a ∈ C . ∀ b ∈ C . (a,b) ∈ E

colorazione di un grafo

assegnare colori ai nodi
in modo che due nodi collegati abbiano sempre colori diversi

formula della colorazione

una k-colorazione è una funzione c:N → {1,…,k}
tale che
∀ (a,b) ∈ E . c(a) ≠ c(b)

teorema dei quattro colori

ogni grafo planare ha una 4-colorazione

per esempio, ogni mappa di nazioni si può colorare con quattro colori
in modo che due nazioni confinanti abbiano sempre colori diversi