Introduzione
Nel precedente articolo (vedi qui), abbiamo visto come realizzare una classe che rappresenti al meglio possibile il modello dei grafi. In questo articolo vedremo in dettaglio alcune sue caratteristiche come il grado di un grafo (graph degree) e la sequenza dei gradi (degree sequence).
Il grado di un grafo
Considerando un grafo, il grado di un nodo è il numero di connessioni che questo ha con gli altri nodi e viene indicato con
deg(v)
Inoltre si deve tenere conto anche dei casi in cui i nodi possono essere connessi con se stessi. In questo caso si chiama loop e il nodo in questione avrà ulteriori due connessioni da considerare nel conto del grado.
Per quanto riguarda invece il grafo, il grado massimo di un grafo, indicato con Δ(G), indica il grado maggiore presente nei suoi nodi, mentre il grado minimo di un grafo, indicato con δ(G), indica il grado più piccolo presente tra i nodi del grafo.
Per farci un’idea più chiara, consideriamo il grafo di esempio che avevamo utilizzato nell’articolo precedente:
Il grado massimo del grafo è equivalente a 3 (quello del nodo B), mentre il grado minimo è 1 (quello del nodo C). Se avessimo avuto un nodo isolato nel grafo allora il grado minimo sarebbe stato pari a 0.
Ma consideriamo una sottoclasse dei grafi: i grafi regolari. Un grafo si dice regolare quando tutti i suoi nodi hanno lo stesso grado. Solo in questo caso possiamo parlare quindi del grado del grafo. Un grafo regolare con tutti i nodi di grado k si chiama grafo k-regolare.
Nella figura seguente vengono riportati alcuni grafi regolari:
Handshaking Lemma
Per continuare con la nostra analisi, e cioè per poter implementare delle funzioni in grado di calcolare i gradi dei nodi ed il grado di un grafo è necessario conoscere un particolare problema matematico: handshaking lemma. Questo teorema dichiara che in un qualsiasi grafo non orientato i nodi con un grado dispari sono in numero pari. Il suo particolare nome, “Handshaking” (scambio di saluto con le mani) deriva dal fatto che si può immaginare un evento in cui un numero pari di persone devono essersi scambiate il saluto con un numero dispari di mani delle altre persone.
Questo teorema si ottiene dall’equazione della somma dei gradi (degree sum formula):
∑v ∈ Vdeg(v) = 2 |E|
Cioè la somma dei gradi di tutti i nodi del grafo è uguale al numero delle connessioni E (edges) moltiplicato per due.
E da questo si deduce che il numero dei nodi con grado dispari deve essere pari. Questa conclusione è nota proprio come handshaking lemma.
Calcolo dei gradi in un grafo
Adesso che abbiamo analizzato la teoria necessaria, passiamo all’implementazione. Per prima cosa scriviamo una funzione che sia in grado di calcolare il grado di un nodo.
def node_degree(self, node):
adj_nodes = self.__graph[node]
degree = len(adj_nodes) + adj_nodes.count(node)
return degree
Nel calcolo del grado di un nodo avremo bisogno anche di una funzione che controlla la presenza di nodi isolati all’interno di un grafo.
def find_isolated_nodes(self):
graph = self.__graph
isolated = []
for node in graph:
print(isolated, node)
if not graph[node]:
isolated += [node]
return isolated
Adesso che abbiamo le funzioni base, implementiamo il metodo delta() che ci permetterà di calcolare il grado minimo di un grafo, ed il metodo Delta() per il grado massimo di un grafo.
def delta(self):
min = 100000000
for node in self.__graph:
node_degree = self.node_degree(node)
if node_degree < min:
min = node_degree
return min
def Delta(self):
max = 0
for node in self.__graph:
node_degree = self.node_degree(node)
if node_degree > max:
max = node_degree
return max
Proviamo il codice appena scritto, calcolandoci il grado massimo ed il grado minimo del grafo di esempio. E controlliamo aggiungendo un nodo isolato, se il metodo find_isolated_node riesce a trovarlo.
g = Graph(graph)
print("d(g): ", g.delta())
print("D(g): ", g.Delta())
g.add_node("F")
print(g.find_isolated_node())Eseguendo il codice, otterrai il seguente risultato:
Il risultato è proprio quello atteso.
Degree Sequence
Un’altra caratteristica molto utilizzata nella teoria dei grafi è la degree sequence di un grafo. La sequenza dei gradi di un grafo non orientato è definita come la sequenza dei gradi dei suoi nodi in ordine non crescente.
Anche in questo caso implementiamo un metodo che calcoli la degree sequence di un qualsiasi grafo.
def degree_sequence(self):
seq = []
for node in self.__graph:
seq.append(self.node_degree(node))
seq.sort(reverse=True)
return tuple(seq)
Il metodo che abbiamo appena implementato restituisce una tupla contenente la sequenza dei gradi (degree sequence). Applichiamola al nostro grafo di esempio
g = Graph(graph) print(g.degree_sequence())
Ottenendo il seguente risultato:
Grafi isomorfi
Un qualsiasi grafo può esistere in moltissime forme, mantenendo invariato il numero di nodi e le stesse connessioni tra di loro. Quindi queste forme, ci appaiono in realtà come grafi diversi, chiamati grafi isomorfi. Quindi se si hanno due grafi diversi, spesso può essere utile conoscere se essi siano isomorfi (diverse forme dello stesso grafo)
I due grafi nella figura seguente sono due grafi isomorfi.
Due grafi sono isomorfi se :
- hanno lo stesso degree sequence
Comunque due grafi con lo stesso degree sequence non sono necessariamente isomorfi.
Il teorema di Erdös-Gallai
Abbiamo visto come sia possibile ricavare un degree sequence da un grafo qualsiasi. Ora interessante sarebbe sapere se dato un certo degree sequence sia possibile realizzare da esso un grafo.
Il teorema di Erdös-Gallai dichiara che una sequenza non crescente di n numeri di (i = 1, …, n) è la degree sequence di un grafo semplice se e solo se la somma dei numeri della sequenza è un numero pari e se la seguente condizione venga soddisfatta:
Quindi dobbiamo implementare un metodo per questo teorema che restituisca un valore booleano, con True in caso positivo e False in caso negativo. Per prima cosa dovremo controllare se la somma degli elementi della sequenza è pari. Successivamente, dovremo controllare se la sequenza passata come argomento è una degree sequence, controllando che gli elementi della sequenza siano non crescenti. Per questo controllo implementeremo una funziona a parte: is_degree_sequence(). Infine il metodo controllerà che la disequazione del teorema venga soddisfatta.
Definiamo entambe questi metodi come metodi statico, attraverso l’aggiunta del decoratore @staticmethod, dato che queste funzioni sono correlata ai grafi ma non sono relative ed applicabili ad una singola e specifica istanza.
@staticnethod
def is_degree_sequence(seq):
return all( x>=y for x, y in zip(seq, seq[1:]))
@staticmethod
def erdoes_gallai(dsequence):
if sum(dsequence) % 2:
return False
if Graph.is_degree_sequence(dsequence):
for k in range(1,len(dsequence) + 1):
left = sum(dsequence[:k])
right = k * (k-1) + sum([min(x,k) for x in dsequence[k:]])
if left > right:
return False
else:
return False
return True
Testiamo il tutto inserendo dapprima una degree sequence ricavata dal grafo di esempio, ed una sequenza di valori inventata.
g = Graph(graph) s = g.degree_sequence() print(Graph.erdoes_gallai(s)) s2 = [4,3,3,2,2,1,1,1] print(Graph.erdoes_gallai(s))
Eseguendo il codice otterrete il seguente risultato.
Conclusioni
In questo articolo abbiamo visto altre due aspetti nell’ambito della teoria dei grafi: il grado e la degree sequence. In successivi articoli vedremo ulteriori aspetti della teoria dei grafi, e come è possibile implementare molti di questi con opportuni algoritmi, arricchendo via via la nostra classe con ulteriori funzioni.