Graphs plugin 20160923-ita

Un plugin python di QGIS per il trattamento dei

gra�

Giuliano Curti (giulianc51 at gmail dot com)

A mio padre Gaetano

Rev. 0.01

Indice

Cronologia 4Avvertenza 5

Capitolo 1. Prefazione 61.1. Cos'è un grafo? 61.2. Cos'è questo plugin? 71.3. L'Interfaccia Gra�ca 81.4. Bibliography 14

Capitolo 2. Ambiente Educativo / Ricreativo 152.1. Supporto Gra�co 152.2. Suggerimenti 262.3. Vertici 282.4. Lati 322.5. Sottogra� 342.6. Alberi (Trees) 352.7. Percorsi e Cicli 522.8. Connectività 622.9. Shortest Paths 732.10. Rapida Introduzione ai Gra� orientati ed alle Reti 772.11. Riepilogo Informativo 78

Capitolo 3. Ambiente Analitico 793.1. Cutpoint 813.2. Bridge 833.3. Minimum Spanning Tree 853.4. Shortest Paths 863.5. Vertex Disjoint Paths 883.6. Edge Disjoint Paths 913.7. Connettività 94

Capitolo 4. Conclusioni 97

3

CRONOLOGIA 4

Cronologia

date issue

2016-09-19 Impianto2016-09-22 Visualizzazione pesi dei lati2016-09-23 Edge-connectivity del grafo stradale di Melegnano2016-09-23 Chiusura rev. 0.01-ita

AVVERTENZA 5

Avvertenza

(1) Ho scritto queste note come un aiuto al mio studio ed alla comprensionedella Teoria dei Gra�. Esse ri�ettono lo stato della mia attuale conoscenzasull'argomento, pertanto vi prego di scusare ogni imperfezione ed errorecontenuto nello scritto.

(2) Queste note ri�ettono il mio approccio alla Teoria dei Gra�, pertanto nondevono intendersi in alcun modo critiche, competizioni o sostituzioni dialtri lavori sullo stesso argomento.

(3) Condivido queste note nella speranza che possano essere di aiuto ad altristudenti della Teoria dei Gra�.

(4) Ogni commento, suggerimento, contributo o critica sono ben accetti.(5) Assumo ogni responsabilità per i contenuti di questo scritto, ma in ogni

caso nessuna garanzia, implicita e/o esplicita, è connessa con il suo uso;il lettore assume i contenuti a proprio rischio e responsabilità.

(6) Come ormai a tutti noto, molti termini inglesi sono diventati di uso co-mune pertanto eviterò di farne scempio con improbabili traduzioni, quindilascerò intatti termini come mouse, layer, shapefile, python, tree,cycle, console, ecc.; nei casi più ostili il ricorso alla rete risolverà ognivostro dubbio.

(7) Questo documento è rilasciato sotto la licenza CC by SA NC.

CAPITOLO 1

Prefazione

1.1. Cos'è un grafo?

Un Grafo è una struttura molto elementare: un insieme di Punti (d'orain avanti chiamati Vertici) ed un insieme di Linee (d'ora in avanti chiamateLati) che collegano una coppia di vertici; matematicamente un grafo è de�nitodal simbolo G (V,E) dove V è l'insieme dei vertici e E = V 2 l'insieme dei lati.Non approfondiamo i dettagli dei gra�, alcuni di essi verranno spiegati nei capitolisuccessivi: limitiamo la nostra analisi ai gra� semplici; inoltre ci limitiamo ai gra�connessi, quelli cioè in cui tutti i vertici sono collegate in qualche modo al resto delgrafo (il lettore curioso può riferirsi ai testi indicati nella bibliogra�a per maggioriinformazioni).

Quello della �gura è un grafo, in realtà si tratta di un tree (Albero), dotatodi

• vertici V = {B,C,G,N, S, T, Y,W}• lati E = {(B, T ) , (T,N) , (C, Y ) , (Y,W ) , (G,W ) , (W,N) , (N,S)}.

Quello che è interessante notare è che i gra� sono independenti dalla posizione,dimensione, distanze, ecc., l'unica cosa importante è se il vertice u è connesso omeno con il vertice v, per tutti i vertici u, v ∈ V .

6

1.2. COS'È QUESTO PLUGIN? 7

1.2. Cos'è questo plugin?

Come alcuni di voi sapranno, QGIS (un applicativo free & open source per lacartogra�a numerica) è dotato di una libreria per l'Analisi delle Reti che imple-menta alcuni strumenti, l'algoritmo di Dijkstra principalmente; recentemente molticontributori hanno aggiunto altri plugin con lo stesso obbiettivo, quindi è lecitochiedersi: perchè un nuovo plugin per i gra�?

Come ho detto nelle Avvertenze, questo plugin è principalmente intesocome un aiuto per l'apprendimento della Teoria dei Gra�. Il mio orizzonteattuale non è l'analisi delle prestazioni globali di una rete o di un grafo orientato, enemmeno quello di scrivere una potente libreria: questi compiti sono meglio assoltida parecchi strumenti, all'interno ed all'esterno del mondo QGIS, disponibili agliutenti; il mio riferimento attuale è di consentire all'utente (il sottoscritto per primo)di imparare le proprietà basilari dei gra�: paths, cycles, spanning trees, connectivity,ecc. Spero di riuscire a sviluppare il mio plugin per compiti maggiori nel futuro,ma ora il mio obiettivo è quello che ho appena raccontato.

Tutti gli algoritmi implementati nel plugin sono �sicamente scritti all'internodel suo codic, senza uso di alcuna libreria esterna; ovviamente questo rende ilplugin prono a bachi ed errori, ma penso anche molto più interessante per scopieducativi. In generale gli algoritmi derivano dalla letteratura tecnica, in particolarmodo dai testi citati nella bibliogra�a del prossimo paragrafo, tuttavia la necessitàdi alcuni strumenti di analisi di connectività, normalmente presi da una parte piùavanzata della teoria (gra� orientati), mi ha obbligato a scrivere alcuni algoritmi dalnulla; ovviamente devono essere validati e sono a disposizione di chiunque volesseesaminarli.

Nello scrivere queste note ho avuto in mente due situazioni:1) un ambiente educativo e/o ricreativo2) un ambiente più serio, analitico;la prima parte di questa note è centrata sul primo punto; proverò, nella seconda

parte, un utilizzo più impegnativo per studiare situazioni più interessanti.Il plugin può trattare un grafo alla volta e non può passare da un grafo all'altra;

un lavoro chiuso deve essere riaperto per essere trattato.

1.3. L'INTERFACCIA GRAFICA 8

1.3. L'Interfaccia Gra�ca

Il plugin è controllato attraverso un pannello di controllo; questo è organizzatoin di�erenti tabs (questo è una nuova caratteristica, peraltro in continua evoluzione,pertanto nelle �gure seguenti potranno apparire versioni del pannello di�erenti enon aggiornate).

(1) I/O


(2) Proprietà del grafo:


(3) Interrogazione dei Vertici e dei Lati:


(4) Alberi e Cicli:


(5) Connettività:


(6) Percorsi:

1.4. BIBLIOGRAPHY 14

1.4. Bibliography

I gra� sono un argomento a�rontato in molti settori della Matematica, per cuiè frequente incontrare utili documenti in aree come la Programmazione Lineare el'Ottimizzazione, l'Ingegneria del Software, l'Analisi delle Reti e cosi via.

Io ho mosso i miei primi passi sui testi che seguono; essi consentono un approcciotimido come il mio, ma possono o�rire argomenti stuzzicanti al lettore, quindipossono costituire una guida completa allo studio dei gra�:

(1) J.A.Bondy, U.S.R.Murty, Graph Theory, Springer, 2008

(2) Frank Harary, Graph Theory, AddisonWesley, 1969

CAPITOLO 2

Ambiente Educativo / Ricreativo

2.1. Supporto Gra�co

Come detto in precedenza un grafo non è determinato dalle sue dimensioni,forme, distanze, ecc. tuttavia il suo schizzo è molto utile: consente al lettore diconoscere immediatamente il grafo.

Questo fatto costituisce la prima utile relazione con QGIS: QGIS come supportoper la visualizzazione del grafo.

Questa è in realtà la modalità più semplice, una interazione più intelligente fraQGIS e graph4qgis sarà presentata in seguito.

Ci sono tre modalità per aprire un �le con il plugin graphs4qgis, questi irispettivi schemi di funzionamento:

(1) caricamento di un �le Graph(a) se il plugin trova uno shape�le dei vertici collegato al grafo lo carica

previa conferma dell'utente(b) altrimenti crea automaticamente una geometria dei vertici e genera

il relativo shape�le(c) crea lo shape�le dei lati

(2) caricamento di uno Shapefile dei lati(a) crea la struttura del grafo(b) crea lo shape�le dei vertici

(3) caricamento di un �le CSV (analogo al caricamento di uno shape�le)(4) creazione di un layer a mano libera(5) ci sarebbe una quinta modalità di caricare �le TXT ma non la discutiamo

quì.

15

2.1. SUPPORTO GRAFICO 16

2.1.1. Caricamento di un �le Graph. Questa è la modalità standard:l'utente carica un �le Graph:


il sistema riconosce se ci sono shape�le collegati al grafo aperto; in caso a�er-mativo il sistema o�re all'utente la possibilità di caricarlo:


alla risposta a�ermativa dell'utente il sistema carica lo shape�le, altrimenti creaautomaticamente e carica a video i layer dei vertici e dei lati (NB: il layer dei lati edil layer dei vertici quando creato automaticamente risiedono in memoria, pertantose necessario occorre salvarli):

Questa è la rappresentazione grezza di un grafo pubblicato sul testo di FrankHarary.


L'utente può modi�care la disposizione dei vertice con gli strumenti usuali diQGIS come sotto rappresentato


Premendo il tasto update SHP ricostruiamo lo schema come rappresentatodall'Autore in Graph Theory, Addison Wesley, 1969, �g. 5.1, pag. 44:


2.1.2. Caricamento di uno Shape�le. La seconda modalità consente all'u-tente di caricare un �le SHP, più esattamente un �le vettoriale di tipo linestring:

caricato lo shape�le, il sistema costruisce automaticamente la struttura delGrafo; provvede inoltre a creare ed a caricare a video il layer dei vertici.


2.1.3. Caricamento di un �le CSV. L'utente può partire da un �le di testocome il seguente:

per l'inserimento dei lati; il �le contiene una linea per ogni lato del grafo di cuifornisce la geometria degli estremi;


l'Utente può caricarlo con i comandi usuali di QGIS e questo è il risultato:

in realtà il �le CSV carica un layer vettoriale nello spazio video di QGIS, quindil'utente segue la procedura descritta al paragrafo �2.1.2.


2.1.4. A mano libera. Come ultima risorsa potete usare i potenti strumentidi QGIS per disegnare un layer vettoriale; in tal caso vanno osservate queste regole:

(1) create un layer vettoriale di tipo LineString(2) inserite le linee (lati) del grafo (avendo cura di far coincidere le estremità

condivise settando opportunamente la funzione di snapping di QGIS)(3) i vertici del grafo saranno le estremità delle linee (lati)(4) le eventuali intersezioni fra le linee non saranno considerate (tecnicamente

si dice che sono ammessi gra� non-piani); è vostra responsabilità spezzarele linee nel caso vogliate utilizzare le intersezioni.

Fatto questo, dovete seguire la procedura descritta al paragrafo �2.1.2; questo è unesampio:


.. e questo il grafo �nale:

2.2. SUGGERIMENTI 26

2.2. Suggerimenti

2.2.1. Python Console. É probabilmente buona cosa tenere aperta la con-sole Python di QGIS per vedere eventuali messaggi del sistema:

2.2. SUGGERIMENTI 27

2.2.2. Capacità di modi�ca di QGIS. Una opzione molto potente è o�ertadalle potenzialità di QGIS: gli elementi evidenziati a video, come vedremo fra poco,possono essere copiati con il comando standard di QGIS

e duplicati in un layer vettoriale di�erente, per usi futuri

2.3. VERTICI 28

2.3. Vertici

2.3.1. Lista dei Vertici. Il plugin consente di elencare a video la lista di tuttii vertici:

Il numero totale dei vertici è normalmente denominato n.

2.3. VERTICI 29

2.3.2. Coordinate dei Vertici. ... lo stesso per l'elenco delle coordinatecartesiane dei vertici:

2.3. VERTICI 30

2.3.3. Grado dei Vertici. ... ed anche per l'elenco dei gradi dei vertici:

2.3. VERTICI 31

2.3.4. Interrogazione dei Vertici. L'utene può interrogare il singolo ver-tice selezionandolo nella casella a discesa; del vertice selezionato sono riportate lecoordinate cartesiane, il grado, i vertici adiacenti, i lati incidenti e se ilvertice costituisce un cutpoint:

2.4. LATI 32

2.4. Lati

2.4.1. Lista dei Lati. L'utente può ottenere l'elenco di tutti i lati del grafo:

Il numero totale dei lati è normalmente denominato m.

2.4. LATI 33

2.4.2. Interrogazione dei Lati. .. oppure può interrogare il singolo lato

ottenendo i vertici di estremità, il peso, se il lato è un bridge, ecc.

2.5. SOTTOGRAFI 34

2.5. Sottogra�

2.5.1. Sottogra�. Dato il grafo G = {VG, EG}, il grafo H = {VH , EH} taleche vH ⊆ VG e EH ⊆ EG è detto sottografo di G.

2.5.2. Sottogra� Indotti. (da fare)

2.6. ALBERI (TREES) 35

2.6. Alberi (Trees)

Tipi particolari di sottogra� di G sono gli Alberi (trees) T = {VT , ET }; laloro caratteristica è di contenere il numero minimo di lati necessari a connetteretutti i vertici di cui sono dotati.

Particolarmente importanti sono gli spanning trees che hanno la proprietàVT = VG, cioè comprendono tutti i vertici del grafo; i lati ET ⊆ EG sono in numerodi n − 1; con ragionamenti elementari l'utente può veri�care che questo numeroè necessario per connettere i vertici (un numero minore di lati lascerebbe qualchevertice sconnesso) e su�ciente allo scopo (un numero maggiore connetterebbe verticigià connessi).

Fra i numerosi alberi di G analizziamo i tre più importanti:

(1) Breath First Search (BFS)(2) Depth First Search (DFS)(3) Minimum Spanning Tree (MST);

più tardi vedremo l'importanza di questi alberi nell'analisi dei gra�.Alla �ne del capitolo introdurremo un quarto albero, il Maximum Spanning

Tree, il cui signi�cato apparirà chiaramente dal nome.


2.6.1. Breath First Search. Abbiamo già notato che in un albero ogni cop-pia di vertici è connessa, quindi possiamo de�nire una vertice base, detto radice,e navigare l'albero dalla radice �no a raggiungere tutti gli altri vertici; questa nav-igazione può essere fatta in diversi modi, una è la Breath First Search; inquesto modo partiamo dalla radice (livello 1) e congiungiamo tutti i vertici adia-centi (livello 2), da quì raggiungiamo i vertici adiacenti ai precedenti (livello 3) ecosi via; questo è molto simile all'organizzazione del sistema di �le di un computer,dove abbiamo la radice, un livello sotto le cartelle e i �le, un livello ancora sottoabbiamo altre cartelle e �le e così via; un altro esempio familiare può essere l'alberogenealogico dove i livelli sono rappresentati dalle generazioni.

Questo è un esempio di BFS con la radice nel vertice v1:

i lati dell'albero BFS sono evidenziati in colore rosso;


questo è un ingrandimento della tabella visualizzata nella console python diQGIS:

dove possiamo vedere

(1) il predecessore(2) il livello(3) l'ordine cronologico

dei vertici attraversati dal BSF


o, se preferite, direttamente a schermo:

..


2.6.2. Depth First Search. Probabilmente l'utente può pensare al BFScome ad una strati�cazione del grafo ed alla sua analisi strato per strato; possi-amo però immaginare di attraversare il nostro grafo in modo di�erente, ad esempionavigando in profondità dalla radice attraverso il primo vertice incontrato ed anco-ra più giù; raggiunto il punto più basso si riprende dal primo vertice disponibile ecosì via: questa modalità si chiama Depth First Search; questo ne è un esempiocon la radice posta sempre nel vertice v1:

i lati dell'abero DFS sono sempre evidenziati in colore rosso;


questo un ingrandimento della tabella visualizzata nella console python diQGIS:

dove possiamo vedere:

(1) il predecessore(2) l'ordine di andata(3) l'ordine di ritorno

dei vertici attraversati dal DSF.


Questo invece un esempio dello stesso grafo con la radice posta nel vertice v4:

quì i lati del DFS sono colorati in giallo;


i dettagli sono visualizzati nella tabella che segue:

La stessa cosa può essere ovviamente eseguita con la modalità BFS.


2.6.3. Pesi. Prima di passare al terzo ed ultimo tipo di albero dobbiamo in-trodurre un nuovo concetto: il Peso dei lati. Finora abbiamo considerato i latitutti uguali, cioè andare dal vertice A al vertice B era lo stesso che andare dal ver-tice C al vertice D; in molte situazioni reali dove i gra� costituiscono un utilissimomodello, le cose possono presentarsi diversamente: A può essere più vicino a B cheC con D; in altri casi passare da A a B può essere meno costoso che passare daC a D, ecc. Pertanto dobbiamo introdurre una proprietà che caratterizzi i lati delgrafo, questa proprietà è il peso (nella letteratura tecnica è detto anche Costo);selezionando un lato nella casella a discesa, insieme ad altre proprietà già discusse,abbiamo anche il peso del lato:

(il lato (G,W ) ha peso 837).


Possiamo ottenere in qualsiasi momento l'elenco dei pesi dei lati del grafo, siain forma tabellare:

che in forma gra�ca:


2.6.4. Minimum Spanning Tree. Ritornando agli alberi, possiamo immag-inare di costruire l'abero di peso (o costo) minore fra tutti gli altri, questo è ilMinimum Spanning Tree.

Un esempio semplice è il problema di costruire una costosa rete (quì il termineè usato in senso generico) illustrato da J.A.Bondy, U.S.R.Murty, Graph Theory,Springer, 2008, �6.2, �g. 6.5, pag. 165 sulla griglia idro-elettrica della RepublicaPopolare di Cina.

Due algoritmi sono particolarmente noti per questo calcolo:

(1) l'algoritmo di Jarnik-Prim(2) l'algoritmo di Boruvka-Kruskal.

L'utente è indirizzato verso la letteratura tecnica per i dettagli; il plugin esegueentrambi gli algoritmi.


2.6.4.1. Algoritmo di Jarnik-Prim. Questo è un esempio dell'algoritmo di Jarnik-Prim:

con l'elenco dei pesi:oppure con i pesi sullo sfondo:


2.6.4.2. Algoritmo di Boruvka-Kruskal. Questo è un esempio dell'algoritmo diBoruvka-Kruskal:

con l'elenco dei pesi:

Avvertenza: il MST è unico, quindi nessuna sorpresa se i due algoritmi for-niscono lo stesso risultato, non ci sono altre possibilità. L'esecuzione dei duealgoritmi può essere utile per confrontarne i risultati.


2.6.5. Maximum Spanning Tree. É un gioco di simmetria pensare al max-imum spanning tree: invertendo il segno dei pesi del grafo w → −w l'algoritmoesegue la ricerca del Maximum Spanning Tree (si potrebbe anche usare l'inversow → 1

w , ma la somma degli inversi non è l'inverso della somma, quindi preferiamousare gli opposti):

(il MxST è individuato con il colore giallo).


2.6.6. Fogliame. Elementi caratteristici di un albero sono le foglie, i verticiterminali, quelli con grado 1. Ovviamente possono essere presenti anche gra� nor-mali; nonostante siano visibili direttamente, il plugin dispone di un comando perevidenziare il fogliame, l'insieme dei vertici terminali:

2.7. PERCORSI E CICLI 52

2.7. Percorsi e Cicli

2.7.1. Generalità. Come abbiamo visto la presenza di lati fra i vertici con-sente di navigare da un punto all'altro; dati due vertici p e q abbiamo diversi modidi navigare da uno all'altro: ad esempio ripercorrendo alcuni lati oppure ripassandoda alcuni vertici; la navigazione senza ripassare dagli stessi vertici (e quindi senzaripassare gli stessi lati) è forse la più importante, chiamata Path e denotata conpPq.

Ripensando ad esempio gli alberi, vediamo che fra ogni coppia di vertici esisteun percorso; di più, il percorso è unico: questa è un'importante caratteristica deglialberi.

Però abbiamo visto che l'albero comprende tutti i vertici del grafo, ma noncontiene tutti i lati: qual'è il ruolo di questi lati addizionali? questo è l'argomentodel prossimo paragrafo.


2.7.2. Cotrees. Non cerco di tradurre il temine che indica chiaramente ilcomplementare di un albero, quindi dato il grafo G = (V,EG) e l'albero coprenteT = (V,ET ), il sottografo complementare C = (V,EC) dove EC = E − ET è ilcotree.

2.7.2.1. BFS cotree. Il cotree dell'albero BFS del paragrafo �2.6.1 è:

Come si può vedere, l'insieme dei lati del cotree EC = {e3, e5, e7, e10, e11} èl'insieme complementare dei lati ET = {e0, e1, e2, e4e6, e8, e9} dell'albero.


2.7.2.2. DFS cotree. Possiamo fare la stessa cosa con l'albero DFS:


2.7.3. Cyclomatic number. (Anche in questo caso preferisco non tradurreil termine) Sappiamo che il numero dei lati di un albero è |ET | = n− 1, pertanto ilnumero dei lati di un cotree è |EC | = |E|−|ET | = m−n+1; questo viene chiamatocyclomatic number ed è visualizzato nel tab proprietà dell'interfaccia gra�ca delplugin:

vedremo fra poco la ragione del suo nome.


2.7.4. Cicli. In un albero abbiamo un unico percorso fra due vertici; se ag-giungiamo un lato del cotree (quì di seguito abbiamo usato un albero BFS e il suocotree) abbiamo un circuito; il lato e3 del cotree unisce i vertici v2, v4 del grafo,ma fra questi esiste già un percorso nell'albero, esattamente il percorso v2Pv4 =(v2, v0, v4); il risultato �nale è il percorso (v2, v0, v4) + (v4, v2) = (v2, v0, v4, v2);questo percorso speciale, dove possiamo partire da ogni vertice e raggiungerlo dinuovo è chiamato Ciclo.


Lo stesso succede con il lato e5:


E lo stesso con il lato e7:


E lo stesso con il lato e10


E lo stesso con il lato e11


2.7.5. Cicli Fondamentali. Come abbiamo visto, per ogni lato del cotreeabbiamo un ciclo, questa è la ragione per la quale il numero dei lati del cotreem− n+ 1 è chiamato cyclomatic number.

Notate che il grafo può contenere un maggior numero di cicli, ma è importanteosservare che qualsiasi altro ciclo può essere ottenuto a partire dai cicli precedenti,giusti�cando così il loro nome di Cicli Fondamentali.

Combinando ad esempio il primo ed il quarto ciclo otteniamo il nuovo ciclo:

{e1, e10, e6}+ {e0, e3, e6} = {e1, e10, e3, e0}.

2.8. CONNECTIVITÀ 62

2.8. Connectività

2.8.1. Generalità. Abbiamo �nora parlato di connettività come di una pro-prietà booleana di un grafo G, in realtà la connettività è una proprietà variabile,ad esempio i gra� seguenti presentano gradi di connessione molto diversi:

nel primo è su�ciente eliminare il lato centrale o uno solo dei vertici centraliper disconnetterlo in due parti separate; nel secondo l'eliminazione di parecchi latie/o vertici lascia il grafo comunque connesso; analizziamo meglio questa proprietàchiamata Connettivita.


2.8.2. Bridges. Un Bridge è un lato la cui eliminazione separa il grafo

come il lato (v1, v3) della �gura che separa la parte {v0, v1, v2} dalla parte{v3, v4, v5} del grafo.


2.8.3. Cutpoints. Un vertice la cui cancellazione disconnette il grafo è dettoCutpoint:

nel grafo della �gura la cancellazione del vertice 5 disconnette il grafo, quindiil vertice 5 è un cutpoint ; lo stesso vale per il vertice 6.


2.8.4. Vertex-connectivity & Line-connectivity. I due ultimi gra� sonoparticolari, hanno un bridge e due cutpoint ; non tutti i gra� hanno bridge e/ocutpoint; normalmente è necessario cancellare un certo numero di lati o di verticiper disconnettere il grafo; mantenendo questi due aspetti separati, possiamo parlaredi Vertex-connectivity e Line-connectivity. La connettività è molto legataai disjoint paths, speci�camente la vertex-connectivity con i vertex-disjoint-pathse la edge-connectivity con gli edge-disjoints-paths; si potrebbe anzi dimostrare confacile evidenza che eliminando un vertice (lato) si sopprime un vdp (edp) e quindiil loro numero deve coincidere; il numero k di vertici (lati) necessari a disconnettereil grafo danno il livello di connettività e parliamo di vertex(edge)-connectivity = k.Ovviamente la connettività varia a seconda della coppia di vertici interessati; in talcaso si parla di connettività locale; il valore minimo fornisce la connettivitàdel grafo.


2.8.4.1. Vertex-disjoint. In generale, in un grafo G abbiamo più percorsi fradue vertici; siamo interessati ai percorsi particolari che non condividono vertici,i cosiddetti Vertex-Disjoint Paths; nel grafo sottostante (da F.Harary, GraphTheory, Addison Wesley, 1969, p. 44), dal vertice a al vertice h abbiamo il percorso(a, c, l, h):


e il percorso (a, d, f, h):

Ogni percorso può essere variato, ad esempio l'ultimo percorso può essere sosti-tuito con (a, b, e, d, f, i, g, h), ma il numero di percorsi senza vertici condivisi rimane2, questa è una proprietà invariante del grafo.

Quindi il concetto può essere parafrasato: in un grafo il numero di vertex-disjoint paths fra due vertici è �sso; quelli visualizzati sono due fra i molti percorsidisponibili.


2.8.4.2. Vertex-connectivity. La proprietà vista sopra è un'importante indicedella connettività del grafo; è evidente che la cancellazione di un vertice da ognipercorso distrugge la connessione del grafo; nell'esempio sotto

la cancellazione del vertice c di un percorso e del vertice d dell'altro (o lacancellazione dei vertici f e l) disconnette il grafo; pertanto il numero dei vertex-disjoint paths eguaglia il numero dei vertici la cui eliminazione disconnete il grafo;il valore minimo di tale numero per tutte le coppie di vertici è detto Vertex-connectivity del grafo G; il suo valore è riportato nel riepilogo informativo.


2.8.4.3. Edge-disjoint. In questo capitolo siamo invece interessati a quei per-corsi particolari che non hanno lati condivisi, i cosiddetti Edge-Disjoint Paths;nel grafo sottostante (da F.Harary, Graph Theory, Addison Wesley, 1969, p. 44),dal vertice a al vertice h abbiamo il percorso (a, d, l, h):


il percorso (a, e, d, f, h):


e il percorso (a, c, l, i, h):

Come nel caso precedente dei VDP, anche in questo caso ogni percorso puòavere diverse varianti, ma il loro numero è comunque 3, anche questa è una proprietàinvariante del grafo.


2.8.4.4. Line-connectivity. Anche questa proprietà è un'importante indice del-la connessione di un grafo; risulta evidente che l'eliminazione di un lato di ognipercorso distrugge la connessione del grafo; nell'esempio sotto

l'eliminazione del lato d− l del primo percorso, del lato d− f del secondo e dellato c− l del terzo disconnette il grafo; pertanto il numero degli edge-disjoint pathseguaglia il numero di lati la cui cancellazione separa il grafo; il valore minimo fraquelli di tutte le coppie di vertici è detto Edge-connectivity del grafo G; il suovalore è riportato nel riepilogo informativo del grafo.

2.9. SHORTEST PATHS 73

2.9. Shortest Paths

2.9.1. Generalità. Anche in questo caso preferisco non tradurre il termineperaltro a tutti noto data la larga introduzione dei navigatori per autoveicoli.

Come già detto, in un grafo connesso G possiamo raggiungere, a partire dalvertice generico p, ogni altro vertice del grafo; questo può essere fatto in diversimodi, quindi possiamo chiederci: quale la strada più breve da p a q? Anche i criterida soddisfare possono essere diversi, ad esempio la distanza (la via più corta dap a q), il costo (la via meno costosa da p a q) e così via. Noi uni�chiamo tutti ipossibili criteri nella proprietà già introdotta del peso, quindi usiamo il termine piùcorto come sinonimo di più leggero, esattamente come abbiamo visto a propositodel Minimum Spanning Tree, con la sola di�erenza che adesso siamo interessati solonel percorso da p a q.


2.9.1.1. Single Shortest Path (Dijkstra). L'algoritmo di Dijkstra assolve aquesto compito; sotto è evidenziato il percorso più breve dal vertice 1 al vertice 9del grafo pubblicato da J.A.Bondy, U.S.R.Murty, Graph Theory, Springer, 2008,�g. 6.7, pag. 150:

il percorso transita dai vertici (1, 3, 9); il suo peso totale è 2.00: fra tutti ipercorsi da 1 a 9, il percorso evidenziato è il più corto o, se preferite, il più leggero.


2.9.1.2. All Shortest Paths SP (Dijkstra). Lo stesso algoritmo di Dijkstra puòessere usato per conoscere tutti i shortest paths da un vertice a tutti gli altri;sotto è visualizzato il percorso fra il vertice 6 e il vertice 9: (6, 12, 7, 3, 9) di pesototale 7.00:


e quì il percorso fra i vertici 6 e 10: (6, 12, 7, 3, 1, 4, 10) di peso totale 10:

2.10. RAPIDA INTRODUZIONE AI GRAFI ORIENTATI ED ALLE RETI 77

2.10. Rapida Introduzione ai Gra� orientati ed alle Reti

Come abbiamo visto, i gra� sono un potente modello matematico applicabilein molti settori della Scienza o dell'Industria; tuttavia la loro generalità deve esserecompressa per adattarli a speci�che situazioni; quì introduco brevemente i principalisviluppi dei gra�; lo faccio solo per dare un quadro più completo della materiaal lettore, senza entrate in dettaglio; il presente lavoro si limita ai gra�: vogliorimarcare la loro importanza come base per ulteriori sviluppi.

2.10.1. Gra� orientati. Nella teoria dei Gra� il lato che connette il verticep al vertice q, connette vicendevolmente il vertice q al vertice p, cioè è simmetrico;ma nella realtà non è sempre così, ci sono situazioni dove un lato connette p conq, ma non viceversa; basta pensare ai sensi unici stradali ; probabilmente lo stessovale per i circuiti elettronici ; o al �usso del sangue nelle vene e arterie del nostrocorpo.

In questi casi la direzione è importante, quindi viene considerata nei gra� conorientazione o gra� orientati, detti in breve Digraphs.

2.10.2. Networks. In speci�che applicazioni la direzione non è su�ciente; adesempio nelle analisi di tra�co e di trasporto la conoscenza delle direzioni è neces-saria per sapere se dal vertice p si può raggiungere il vertice q; anzi, l'introduzionedegli algoritmi per la ricerca dei percorsi più brevi sono un grande aiuto per ragionieconomiche evidenti; bene, ma questo non è su�ciente: probabilmente vogliamoanche sapere quanti veicoli possono transitare sulle strade, quanti prodotti possi-amo trasportare e così via. In questi casi dobbiamo introdurre due nuove proprietàdegli arcs (questo è il nome usuale che viene usato per i lati nei gra� orientati): lacapacità c ed il �usso f con la clausola f ≤ c.

Spero in un prossimo futuro di essere in grado di trattare anche questi problemi,per il momento devo chiudere quì.

2.11. RIEPILOGO INFORMATIVO 78

2.11. Riepilogo Informativo

Molte delle proprietà esaminate sopra sono riportate nel riepilogo del tab Propcompilato al caricamento dei dati del grafo:

CAPITOLO 3

Ambiente Analitico

Come ulteriore dimostrazione delle prestazioni del mio plugin, proverò ad ap-plicarle ad un caso concreto, il grafo stradale della mia città, Melegnano, vicinoMilano, Italia:

Questo è il grafo sempli�cato estratto da uno shape�le e convertito in un graforiconoscibile dal mio plugin.

Avvertenza: Come ho detto, analizzo una rete come fosse un grafo, senzaconsiderazione cioè della direzione delle strade. Propongo questa analogia: il grafostradale è hardware e la direzione di marcia è software (essendo possibile cambiarlacon un provvedimento amministrativo), il presente studio quindi può essere vistocome analisi hardware; lascio la analisi software a futuri sviluppi del mio lavoro.

79

3. AMBIENTE ANALITICO 80

Il riepilogo dice

• 179 vertici• 237 lati• peso totale 28537m (ho usato la lunghezza in metri delle strade come pesodel grafo)

• il grafo è connesso pertanto non ci sono componenti• grado minimo 1 (ci sono molte strade a fondo chiuso)• grado massimo 4• grado medio 2.6• il grafo è

� non pari� non dispari� non bipartito

• cyclomatic number 59• 49 cutpoint (uso due algoritmi sperimentali per il calcolo e il riepilogodice che la vers. A dell'algoritmo fornisce un numero di�erente di cupoint:faccenda da approfondire)

• 50 bridge;

per quanto riguarda la connettività aggiungerò qualcosa sotto.

3.1. CUTPOINT 81

3.1. Cutpoint

Guardando qualche dettaglio, possiamo evidenziare i cutpoint, tutti insieme:

3.1. CUTPOINT 82

o uno alla volta:

Il caso evidenziato è abbastanza signi�cativo: l'eliminazione o la messa fuoriservizio del vertice v108 disconnette il grafo, in tal caso il vertice v109, un centrocivico (scuola, piscina, campo di calcio, ecc.), non sono più raggiungibili, ma ancheil vertice v111, la connessione con la rete regionale è impedito.

3.2. BRIDGE 83

3.2. Bridge

Un altro aspetto sono i bridge, tutti insieme:

3.2. BRIDGE 84

o uno alla volta:

molti bridge sono costituiti dalle strade a fondo chiuse di cui abbiamo parla-to, quindi sono relativamente poco importanti data la modesta in�uenza sul grafogenerale; più importante ovviamente il bridge v108 − v111, non visualizzato nella�gura, ma presente nella precedente: la sua defezione causa la stessa disconnessionevista a proposito del cutpoint v108.

3.3. MINIMUM SPANNING TREE 85

3.3. Minimum Spanning Tree

Un aspetto a mio avviso molto interessante è il Minimum Spanning Tree nella�gura sotto:

la lunghezza totale, ricordo, del grafo è di 28.5m, la lunghezza totale del MSTè di 17km.

C'è una vecchia discussione nella mia città circa le piste pedonali e/o ciclabili;come spesso succede in Italia le discussioni sono lunghe, le piste ciclopedonali unpò meno .....

Comunque, suppongo che le risorse per questa infrastruttura a rete siano limi-tate e la necessità di dotare l'intera città di piste signi�ca attrezzare oltre 28km distrade.

Se trattiamo le piste ciclopedonali come una risorsa pregiata, del tipo di quellaconsiderata da J.A.Bondy, U.S.R.Murty, Graph Theory, Springer, 2008, 6.2, g.6.5, p. 165, già citata al paragrafo �2.6.4, potremmo pensare al MST come aduna possibile soluzione: basterebbe attrezzare 17km di piste, poco più della metàdell'intera lunghezza, per consentire l'attraversamento di tutta la città e rendereaccessibili tutti i suoi punti cruciali. Peraltro andrebbero considerate anche le pistegià esistenti che, coordinate nel quadro complessivo, potrebbero abbassare ancorail costo e le risorse necessarie.

Avvertenza: il costo delle piste e la loro maggiore o minore lunghezza nonsono i soli criteri; se lasciassi per un momento i panni del matematico dilettante erivestissi quelli di architetto che ho appena dismesso, certamente analizzerei moltialtri aspetti; quello che penso, rientrando velocemente nei più comodi panni delmatematico, è che l'informazione è molto utile per chi deve decidere, un puntofermo da mettere insieme ad altri per costruire il giusto progetto ed il migliormosaico decisionale.


3.4. Shortest Paths

Guardiamo ora i Shortest Paths, il singolo Shortest Paths, ad esempio, dalvertice v86 al vertice v173:


o tutti i Shortest Paths dallo stesso vertice v86; i percorsi possono esserevisualizzati uno alla volta, nella �gura sotto è mostrato il percorso da v86 a v153.

Avvertenza: questa analisi è la stessa disponibile nella Network Analysis Li-brary di QGIS o negli altri plugin citati all'inizio; con tutta probabilità questi ultimisono più e�cienti e robusti del mio; come ho detto più volte, la duplicazione deglialgoritmi nel mio plugin ha essenzialmente scopi didattici.

3.5. VERTEX DISJOINT PATHS 88

3.5. Vertex Disjoint Paths

Un interessante aspetto sono i Vertex Disjoint Paths; li abbiamo calcolati frail vertice v89, il centro città, e il vertice v44, la connessione verso nord (Milano);come si può vedere dalle �gure seguenti, ci sono tre di questi percorsi, il primo:


il secondo:


e il terzo:

Tutte le strade interessate sono a doppio senso di marcia per cui in questo casol'analisi hardware coincide con quella software.

É importante sottolineare la nozione di connettività locale: la connessione fracentro città e rete regionale nord è su�cientemente robusta: occorre mettere fuorigioco contemporaneamente tre vertici per distruggere questa connessione.

3.6. EDGE DISJOINT PATHS 91

3.6. Edge Disjoint Paths

Analoghi ai vertex-disjoint sono gli Edge Disjoint Paths, la di�erenza consistenel fatto che quì è possibile anche attraversare un vertice già passato, mentre tutti ilati del percorso devono essere di�erenti; usando ancora i vertici v89 e v44, abbiamotre percorsi, il primo:


il secondo:


e il terzo:

Nota matematica: detti κ (G) la vertex-connectivity, λ (G) la edge-connectivitye δ (G) il grado minimo, vale il teorema di Whitney: κ (G) ≤ λ (G) ≤ δ (G)(F.Harary, Graph Theory, Addison Wesley, 1969, th. 5.1 pag. 43); nel nostrocaso abbiamo κ (G) = 3, λ (G) = 3 e δ (G) = min (dv044, dv089) = 3, il teorema diWhitney κ (G) = λ (G) = δ (G) risulta veri�cato.

3.7. CONNETTIVITÀ 94

3.7. Connettività

3.7.1. Un Suggerimento. Abbiamo visto l'importanza della vertex- e dellaedge-connectivity per la comprensione della struttura del grafo; spesso i gra� con-tengono molti vertici terminali, quindi sono numerosi i cutpoint ed i bridge; questicutpoint e/o bridge sono banali, noti e non molto importanti in quanto incidonosu una parte limitata del grafo; peggio, questa moltitudine nasconde altri even-tuali importanti cutpoint e bridge, pertanto recuperiamo un risultato già visto alparagrafo �2.6.6: il fogliame del grafo. Eliminando �no ad esaurimento i verticiterminali, raggiungiamo un sottografo che ho chiamato core; quello sotto è il coredel grafo stradale di Melegnano:


Applicando le analisi viste a questo sottografo possiamo scoprire aspetti moltointeressanti:

(1) ci sono quattro cutpoint (v6, v21, v22, v158)(2) c'è un bridge (v21-v22).

3.7.2. Vertex Connectivity. Abbiamo già visto al paragrafo � 2.8.4 l'im-portanza della vertex-connectivity di un grafo; questa sotto è la statistica del grafostradale di Melegnano:

numero di coppie 8197minimo 1 per la coppia ['v 0', 'v 12']media 1.73

massima 4 per la coppia ['v 1', 'v 4']sqm 0.66

Confesso che il dato medio (1.73) mi preoccupa perchè quì stiamo trattandoil sottografo depurato dai nodi terminali e mi sarei aspettato un valore almenosuperiore a 2.

(Nota 1: ora il plugin o�re anche la distribuzione statistica della vertex-connectivity;questa tabella è stata preparata con una versione precedente che non la prevedeva;aggiornerò quanto prima i dati).

(Nota 2: La tabella è stata completata con una versione standalone dell'appli-cazione perchè il calcolo dei VDP di tutte le coppie di vertici costituisce un processotroppo lungo per una sessione interattiva come il plugin).

3.7.3. Edge Connectivity. Questa è la statistica della edge-connectivity delgrafo stradale di Melegnano:

numero di coppie 8385minimo 1 per la coppia ['v 0', 'v 12']media 2.10

massima 4 per la coppia ['v 1', 'v 4']sqm 0.68

la distribuzione della connettività per grado è la seguente


grado frequenza %

0 0 01 1510 182 4554 543 2288 274 33 <1

totale 8385 100Avanzo un'ipotesi: abbiamo già visto la presenza del bridge (v20, v21); questo

bridge divide il grafo in due blocchi di circa 10÷ 12 vertici a nord-est e i rimanenti130 − 10 ÷ 12 = 118 ÷ 120 (ricordate che stiamo trattanto con il core del grafostradale) per un totale di 118÷120×10÷12 = 1200÷1416 coppie, quindi le coppiecon edge-connection = 1 sono probabilmente collegate con quel bridge; possiamopensare che il restante grafo è sostantialmente robusto).

(Nota: Come sopra la tabella è stata completata con una versione standalonedell'applicazione perchè il calcolo degli EDP di tutte le coppie di vertici costituisceun processo troppo lungo per una sessione interattiva come il plugin).

CAPITOLO 4

Conclusioni

Non credo ci siamo molte conclusioni da trarre; ho sostanzialmente raccontatoquello che avevo in mente di dire; spero di aver dato una su�ciente informazione sulplugin che ho realizzato e spero che possa essere di aiuto a qualcun altro �studente�di gra�.

Resto a disposizione ed in attesa di suggerimenti, consigli, contributo e critiche,nell'attesa vedrò di approfondire qualcosa sui gra� orientati e le reti.

Grazie.

97

Graphs plugin 20160923-ita

Science

Transcript of Graphs plugin 20160923-ita