Capitolo 3. Il grafo come modello della conoscenza
3.1. Il grafo come strumento di modellazione
Il grafo è un modello matematico costituito da un insieme di elementi e da una r lazione fra gli stessi che li collega a due a due. Gli elementi della struttura sono chi mati convenzionalmente nodi
la relazione che collega due nodi è detta
Figura 3.
Più formalmente, si dice grafo una con V insieme dei nodi ed
Il grafo come modello della
ono vengono esposte le nozioni fondamentali della teoria dei matematico svizzero Euler0 (1707-1783), con particolare riguardo alla terminologia e agli algoritmi fondamentali pertinenti al modello proposto
proprietà di grafi reali, quali quelli che si possono derivare da Internet e del Web, e di due grafi ‘sintetici’, più funzionali alla n tra ricerca, vale a dire WordNet, il database lessicale originariamente solo della lingua inglese, e le Mappe Concettuali. L’analisi dei grafi è cruciale per arrivare ad approfondire le conoscenze di un fenomeno e a progettare algoritmi efficienti ed aci per la sua elaborazione. Dimostrata la pervasività del grafo come modello
capace di rappresentare diversi fenomeni e, in generale, strutture sarà dimostrata la possibilità di utilizzare questa stessa strutt presentare una disciplina scolastica, con i vantaggi e le criticità che ne
nsegnanti sia per gli studenti; questa stessa struttura,
potrà costituire lo scheletro di un libro digitale realmente dinamico e
come strumento di modellazione
Il grafo è un modello matematico costituito da un insieme di elementi e da una r lazione fra gli stessi che li collega a due a due. Gli elementi della struttura sono chi
nodi o vertici e si rappresentano come punti la relazione che collega due nodi è detta arco e si rappresenta con una linea
Figura 3.1 Esempio di grafo con sei nodi e cinque archi.
Più formalmente, si dice grafo una coppia ordinata G= (V, E) E insieme degli archi, tali che gli elementi di
come modello della
o vengono esposte le nozioni fondamentali della teoria dei , con particolare riguardo pertinenti al modello proposto.
Se-quelli che si possono derivare dal-, più funzionali alla no-tra ricerca, vale a dire WordNet, il database lessicale originariamente solo della
cruciale per arrivare ad e a progettare algoritmi efficienti ed la pervasività del grafo come modello diversi fenomeni e, in generale, strutture ed sarà dimostrata la possibilità di utilizzare questa stessa struttu-presentare una disciplina scolastica, con i vantaggi e le criticità che ne
struttura, una vol-realmente dinamico e
Il grafo è un modello matematico costituito da un insieme di elementi e da una re-lazione fra gli stessi che li collega a due a due. Gli elementi della struttura sono chia-e si rapprchia-eschia-entano comchia-e punti su un piano;
e si rappresenta con una linea tra essi.
grafo con sei nodi e cinque archi.
= (V, E) di insiemi, insieme degli archi, tali che gli elementi di E siano coppie
di elementi di V. Si chiama “cammino di lunghezza k” da un nodo ua un nodo v una sequenza di k archi consecutivi che collegano u a v. I vertici u e v si dico-no estremi del cammidico-no. Dato un grafo G = (V, E) due dico-nodi u,v
∈
V si dicono “con-nessi” se esiste un cammino con estremi u e v. Se tale cammino non esiste, v e u sono detti “sconnessi”. Come si può osservare nella Figura 3.1, il nodo D è “sconnesso” da-gli altri. Perciò si definisce “connesso” un grafo in cui ogni coppia di nodi è collegata da un cammino.Quando u= v il cammino è detto ciclo. Il grafo che non contiene cicli si chiama “a-ciclico”. Un nodo v si dice raggiungibile da un nodo u in G se esiste un cammino da u a v. La visita di un grafo G a partire da un nodo u è un algoritmo che restituisce tutti i nodi di G che sono raggiungibili da u. Una visita di un grafo G permette, quindi, di esaminare i nodi e gli archi di G in modo sistematico. Se si considerano i nodi rag-giunti e tutti gli archi tra essi presenti in G, si ottiene un sottografo di G che è il risul-tato della visita. Il “diametro” di un grafo è il più lungo cammino tra tutte le coppie u, v di nodi del grafo. Il grafo in Figura 3.1 ha diametro 3, perché sia la coppia (E, C) sia la coppia (F, C) hanno distanza 3.
Si definisce “grado” di un nodo il numero di archi incidenti in esso; “grado massi-mo” e il “grado minimassi-mo” di G, rispettivamente, il grado del vertice di G con il maggior numero di archi incidenti e il grado del vertice di G che ha meno archi incidenti. Quando il grado massimo ed il grado minimo coincidono con un numero k, si è in presenza di un “grafo k-regolare”, o più semplicemente “grafo regolare”. Nel grafo di Figura 3.1 il nodo A ha grado 3, mentre il nodo D ha grado zero.
Un grafo si dice “pesato” quando agli archi vengono associate delle informazioni numeriche, chiamate appunto “pesi”. Molte reti reali dimostrano un’evidente etero-geneità nella capacità e nell’intensità dei collegamenti. Esempi di ciò sono l’esistenza di legami deboli e forti fra individui nelle reti sociali; le diverse interazioni predatore-preda nella catena alimentare; la differente capacità di trasmettere segnali elettrici nella rete neurale; il diseguale traffico di passeggeri nella rete stradale o aerea. L’intensità di questi collegamenti può essere quantificata con numeri interi o reali, positivi o negativi.
Figura 3.2 Esempi di grafi: a) G
A seconda che gli archi siano simmetrici o asimmetrici il grafo si definirà rispett vamente “non-orientato” e “orientato”
gli archi lasciano un nodo in uscita e raggiungono un altro nodo in entrata con una freccia che ne indica la direzione (in questo senso sono “asimmetrici”). Viceversa, in un grafo “non-orientato” gli archi non hanno direzione (sono, dunque, “simmetrici”). Facendo riferimento alla F
orientato ed è ciclico: infatti contiene due cicli di lunghezza 2 relativi i due insiemi di nodi {q,s} e {n,p}. Un grafo
cammino fra una qualunque coppia di nodi in qualunque ordine essi siano presi.
Figura 3.3 Esempi di alberi:
grafi: a) G1 è un grafo non orientato; b) G2 è un grafo orientato con cicli.
seconda che gli archi siano simmetrici o asimmetrici il grafo si definirà rispett orientato” e “orientato” (esempi in Figura 3.2). In un grafo “orientato” archi lasciano un nodo in uscita e raggiungono un altro nodo in entrata con una freccia che ne indica la direzione (in questo senso sono “asimmetrici”). Viceversa, in orientato” gli archi non hanno direzione (sono, dunque, “simmetrici”). ferimento alla Figura 3.2, il grafo G1 è non orientato, mentre il grafo d è ciclico: infatti contiene due cicli di lunghezza 2 relativi i due insiemi di
Un grafo orientato si dice “fortemente conness
qualunque coppia di nodi in qualunque ordine essi siano presi.
alberi: a) albero libero; b) albero radicato; c) albero binario completo. è un grafo orientato con cicli.
seconda che gli archi siano simmetrici o asimmetrici il grafo si definirà rispetti-. In un grafo “orientato” archi lasciano un nodo in uscita e raggiungono un altro nodo in entrata con una freccia che ne indica la direzione (in questo senso sono “asimmetrici”). Viceversa, in orientato” gli archi non hanno direzione (sono, dunque, “simmetrici”). è non orientato, mentre il grafo G2 è d è ciclico: infatti contiene due cicli di lunghezza 2 relativi i due insiemi di si dice “fortemente connesso” se esiste un qualunque coppia di nodi in qualunque ordine essi siano presi.
Una classe importante di grafi sono gli alberi. L’albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino. L’albero si defi-nisce altrimenti come grafo non orientato connesso e privo di cicli: questo tipo di al-bero si definisce propriamente “alal-bero lial-bero” (Figura 3.3, T1 è un albero libero). Si chiama “albero radicato” (Figura 3.3, T2) quello in cui è stato selezionato un partico-lare nodo, definito radice, nel quale dunque si determina un’implicita direzione fra la radice e gli altri nodi discendenti per cui si può dire che: w è il padre di v, ovvero v è figlio di w se esiste l’arco (w, v) e w è sul cammino dalla radice a v; f è una foglia, se non ha figli. In un albero un nodo o è una foglia o è un nodo interno; l’altezza di un albero è data dalla lunghezza del più lungo fra tutti i cammini dalla radice a una fo-glia.
Com’è facile intuire, l’albero radicato si presta a rappresentare strutture gerarchi-che in tanti campi della realtà: si va dalle organizzazioni aziendali alla rappresenta-zione della conoscenza dal generale al particolare, denominata “mappa concettuale”, di cui si parlerà nel seguito. Un albero radicato si dice “binario” se ogni nodo ha al massimo due figli, e “albero binario completo” quello in cui ogni nodo interno ha e-sattamente due figli (Figura 3.3, T3).
Un altro concetto che risulterà cruciale nel prosieguo è quello di “ordinamento to-pologico” di un grafo orientato G. Questo consiste in una serializzazione di tutti i nodi del grafo tale che gli archi di G risultano così orientati da sinistra a destra. Condizio-ne Condizio-necessaria e sufficiente affinché sia possibile definire compiutamente l’ordinamento topologico, è che il grafo G sia aciclico. L'ordinamento topologico non è un ordinamento totale, poiché la soluzione può non essere unica. Si possono infatti avere al più n! (= n * (n-1) * (n-2) * ... * 1) ordinamenti topologici diversi che corri-spondono a tutte le possibili permutazioni degli n nodi di G.
Figura 3.4 Esempio di funzionamento dell’algoritmo per
La Figura 3.4 riportata
G, indicati con le lettere maiuscole per cui è possibile calcolare il suo
presenta due nodi che non hanno archi in entrata, i cosiddetti “ C). L’idea alla base dell’algoritmo di ordinamento consiste
nodo tra quelli sorgente, eliminarlo insieme a tutti i suoi archi uscenti, e poi ripetere l’operazione di selezione sui nodi sorgente
nodi nel grafo. L’esistenza di almeno un nodo sorgente grafo; ad esempio in Figura
da della prima scelta che possiamo fare, conseguono diversi ordinamenti topologici, che ora andiamo a dettagliare.
Caso con selezione ini
Se si sceglie come sorgente della scelta C, viene eliminato archi da esso uscenti. Il nuovo grafo
F. Se F è la nuova scelta, vuol dire che si procede a elimi
esso uscenti. A questo punto la scelta obbligata è il nodo A, poiché gli altri nodi no almeno un arco entrante (F
scelte che sono obbligate, vale a dire BDEG
nodi A-G sarà completamente determinata quando saranno stati eliminati tutti i nodi e gli archi del grafo, ed è dunque: CFABDEG. Questa, però, non è l’unica. Altre co
Esempio di funzionamento dell’algoritmo per il calcolo dell’ordinamento topologico grafo in a).
riportata illustra come sia possibile serializzare i 7 nodi di un grafo maiuscole dell’alfabeto. Si noti che G è o
per cui è possibile calcolare il suo ordinamento topologico. Nella F
presenta due nodi che non hanno archi in entrata, i cosiddetti “nodi sorgente . L’idea alla base dell’algoritmo di ordinamento consiste nello scegliere se
, eliminarlo insieme a tutti i suoi archi uscenti, e poi ripetere e di selezione sui nodi sorgente rimasti, fintanto che esistono ancora dei nodi nel grafo. L’esistenza di almeno un nodo sorgente è garantita
igura 3.4 esistono due nodi sorgente al passo iniziale.
da della prima scelta che possiamo fare, conseguono diversi ordinamenti topologici, che ora andiamo a dettagliare.
Caso con selezione iniziale di C
Se si sceglie come sorgente della scelta C, viene eliminato questo nodo
archi da esso uscenti. Il nuovo grafo della figura b) presenta ancora due sorgenti, A e F. Se F è la nuova scelta, vuol dire che si procede a eliminare F dal g
esso uscenti. A questo punto la scelta obbligata è il nodo A, poiché gli altri nodi no almeno un arco entrante (Figura 3.4.c). L’eliminazione di A porta alle successive
obbligate, vale a dire BDEG (Figura 3.4.d-g). La
sarà completamente determinata quando saranno stati eliminati tutti i nodi è dunque: CFABDEG. Questa, però, non è l’unica. Altre co
l’ordinamento topologico del
possibile serializzare i 7 nodi di un grafo dell’alfabeto. Si noti che G è orientato e aciclico, ordinamento topologico. Nella Figura 3.4.a il grafo nodi sorgente” (A e nello scegliere sempre un , eliminarlo insieme a tutti i suoi archi uscenti, e poi ripetere rimasti, fintanto che esistono ancora dei è garantita dall’aciclicità del esistono due nodi sorgente al passo iniziale. A secon-da della prima scelta che possiamo fare, conseguono diversi ordinamenti topologici,
questo nodo con tutti gli ella figura b) presenta ancora due sorgenti, A e dal grafo e gli archi da esso uscenti. A questo punto la scelta obbligata è il nodo A, poiché gli altri nodi
han-c). L’eliminazione di A porta alle successive g). La serializzazione dei sarà completamente determinata quando saranno stati eliminati tutti i nodi è dunque: CFABDEG. Questa, però, non è l’unica. Altre
com-patibili, senza esaurire tutte le possibilità, sarebbero per esempio: CABDEFG e CA-FBDEG. La prima si ottiene scegliendo A al posto di F, durante il secondo passo, e la seconda si ottiene da quella indicata sopra scambiando l’ordine di selezione tra A e F.
Caso con selezione iniziale di A
Se si scegliesse A come sorgente, allora si eliminerebbe dal grafo A con gli archi da esso uscenti. Perciò si originerebbe un grafo con due possibili nodi sorgenti: B e C. Scegliendo B, lo si elimina dal grafo ottenendo così la scelta obbligata C, unico nodo privo di archi in entrata. Si arriva, dunque, a una sequenza ABC. Eliminato C, si può proseguire con D o F. Se viene eliminato F, si procede con D-E-G. La serializzazione che si ottiene è ABCFDEG. Altre compatibili, senza esaurire tutte le possibilità, sa-rebbero per esempio: ABCDEFG; ACBDFEG; ACFBDEG.
Come si è fatto notare, sia partendo da C sia partendo da A si arriva a un certo punto della visita a dover scegliere fra più nodi (nel caso esaminato la scelta è tra due nodi, A e F quando si parte da C, o B e C, e poi D e F, quando si parte da A). Ciascuna scelta induce una serializzazione diversa, e quindi è evidente che le serializzazioni conseguenti sono numerosissime. Solitamente gli algoritmi per il calcolo dell’ordinamento topologico di un grafo producono una sola serializzazione che di-pende dall’ordine con cui i nodi e gli archi del grafo sono enumerati; nel nostro mo-dello a grafo di un libro digitale avremo bisogno di generare più serializzazioni che soddisfano specifici criteri di compatibilità, per cui sarà necessario rivedere parzial-mente gli algoritmi noti.