Capitolo 11 Grafi e visite di grafi Algoritmi e Strutture Dati.
GRAFI CONNESSI - MathUniPDcarla/docs/MatDiscrProb13-14/6LEZ-28-0… · grafo connesso. • Vertex...
12
Un grafo non orientato G(V,E) si dice connesso se, per ogni coppia di vertici, esiste un cammino che li collega, altrimenti si dice sconnesso. Le componenti connesse di un grafo sono i suoi sottografi connessi massimali. Esempio: PROBLEMA: Quanto "robusta" è la connessione di un grafo connesso, cioè quanti spigoli o quanti vertici devo togliere per farlo diventare sconnesso? GRAFI CONNESSI lunedì 28 aprile 2014 14:27 GRAFI CONNESSI Pagina 1
Transcript of GRAFI CONNESSI - MathUniPDcarla/docs/MatDiscrProb13-14/6LEZ-28-0… · grafo connesso. • Vertex...
Un grafo non orientato G(V,E) si dice connesso se, per ogni coppia di vertici, esiste un cammino che li collega, altrimenti si dice sconnesso.
Le componenti connesse di un grafo sono i suoi sottografi connessi massimali.Esempio:
PROBLEMA: Quanto "robusta" è la connessione di un grafo connesso, cioè quanti spigoli o quanti vertici devo togliere per farlo diventare sconnesso?
GRAFI CONNESSI lunedì 28 aprile 201414:27
GRAFI CONNESSI Pagina 1
Dato G(V,E) grafo connesso:
Connettività sugli spigoli = λ(G) = minimo numero di spigoli la cui rimozione trasforma G in un grafo sconnesso.
la rimozione di tutti gli spigoli di S trasforma G in un grafo sconnesso;
•
la rimozione di alcuni degli spigoli in S, ma non tutti, lascia il grafo connesso.
•
Edge cutset = insieme di spigoli S E con le seguenti proprietà:
Quindi:λ(G) = cardinalità dell'edge cutset di G di cardinalità minima.
CONNETTIVITÀ SUGLI SPIGOLIlunedì 28 aprile 201414:37
GRAFI CONNESSI Pagina 2
Dato G(V,E) grafo connesso e non completo:
Connettività sui vertici = κ(G) = minimo numero di vertici la cui rimozione trasforma G in un grafo sconnesso.
la rimozione di tutti i vertici di U trasforma G in un grafo sconnesso;
•
la rimozione di alcuni dei vertici di U, ma non tutti, lascia il grafo connesso.
•
Vertex cutset = insieme di vertici U V con le due seguenti proprietà:
Quindi, se G non è completo:κ(G) = cardinalità del vertex cutset di G di cardinalità minima.
Un grafo completo con n vertici non ha vertex cutsets. Per convenzione, la connettività sui vertici di un grafo completo con n vertici è posta uguale a n-1.
CONNETTIVITÀ SUI VERTICIlunedì 28 aprile 201414:37
GRAFI CONNESSI Pagina 3
κ(G) ≤ λ(G) ≤ δ(G),
E' facile dimostrare che in ogni grafo connesso G con almeno due vertici, vale:
dove il simbolo δ(G) indica il grado del vertice di grado minimo di G.
In particolare, se G è il grafo completo con n vertici, n ≥ 2, allora κ(G) = λ(G) = δ(G) = n-1.
DISEQUAZIONIlunedì 28 aprile 201415:07
GRAFI CONNESSI Pagina 4
ESEMPIlunedì 28 aprile 201414:56
GRAFI CONNESSI Pagina 5
Rete di comunicazione tra soggettiè necessario fornire percorsi alternativi di comunicazione, per fronteggiare:inattività di un soggetto;guasto di una linea;carico eccessivo di una linea, che superi la sua capacità.
per ogni coppia di nodi esistono almeno λ(G) cammini alternativi che li collegano (tali che non ci siano due cammini che usano qualche spigolo in comune);
-
per ogni coppia di nodi esistono almeno κ(G) cammini alternativi che li collegano (tali che non ci siano due cammini che usano qualche vertice in comune).
-
Dato G grafo:
κ(G) ≤ λ(G) ≤ δ(G) ≤
In generale vale la seguente formula:
κ(G) = λ(G) = δ(G) =
Si dice che un grafo ha connettività ottima se vale
ha massima connettività sugli spigoli e sui vertici tra tutti i grafi con |V| vertici e |E| spigoli
•
è regolare.•
Proprietà:
AFFIDABILITÀ DI UNA RETElunedì 28 aprile 201415:19
GRAFI CONNESSI Pagina 6
Problema dei ponti di Konigsberg
Multigrafi: stessa definizione dei grafi, ma sono permessi spigoli (archi) paralleli e cappi.
Grafi Multigrafi
cammino trail
circuito ciclo
MULTIGRAFIlunedì 28 aprile 201415:17
CICLI EULERIANI Pagina 7
CICLI EULERIANI Pagina 8
Ciclo euleriano = ciclo che contiene tutti gli spigoli del multigrafo e visita ogni vertice almeno una volta.
Sia G(V,E) un multigrafo non orientato.
Procedura per costruire un ciclo euleriano in un multigrafo connesso con tutti i vertici di grado pari: esempio
CICLI EULERIANIlunedì 28 aprile 201423:18
CICLI EULERIANI Pagina 9
Teorema di Eulero (1736):
è connesso, •ha tutti i vertici di grado pari.•
Un multigrafo non orientato ha un ciclo di Eulero se e solo se
Dimostrazione
TEOREMA DI EULERO NON ORIENTATOlunedì 28 aprile 201423:29
CICLI EULERIANI Pagina 10
Corollario
è connesso, •ha esattamente due vertici di grado dispari.•
Un multigrafo non orientato ha un trail di Eulero, ma non un ciclo di Eulero, se e solo se
CICLI EULERIANI Pagina 11
Teorema di Eulero (1736):
è fortemente connesso,•in ogni nodo il grado entrante è uguale al grado uscente.•
Un multigrafo orientato ha un ciclo di Eulero se e solo se
TEOREMA DI EULERO ORIENTATOlunedì 28 aprile 201423:29
CICLI EULERIANI Pagina 12
