Programmare Grafi in Python – Parte 2

Programmare grafi in Python - parte 2Introduzione

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).

Programming Graphs in Python - part 2 main

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.

programming graphs with Python - loop node

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:

grafo

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:

programming graphs with Python - regular graphs

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.

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.

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.

Python e graphs - graph with an isolated node

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.

Eseguendo il codice, otterrai il seguente risultato:

Programming graph with Python - console output 01

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.

Il metodo che abbiamo appena implementato restituisce una tupla contenente la sequenza dei gradi (degree sequence). Applichiamola al nostro grafo di esempio

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.

Programming graph with Python - isomorphic graphs - 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:

Erdös-Gallai theorem

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.

Testiamo il tutto inserendo dapprima una degree sequence ricavata dal grafo di esempio, ed una sequenza di valori inventata.

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.

Lascia un commento