What is a graph?

Nel 1736, Königsberg, l'attuale Kaliningrad, era una città attraversata dal fiume Pregel, che la divideva in quattro zone, due rive e due isole, collegate fra loro da sette ponti. Fra i suoi abitanti circolava una domanda: è possibile effettuare una passeggiata che attraversi ogni ponte una volta sola?

Questa domanda fu risolta da Leonhard Euler e rappresenta la nascita della teoria dei grafi. Per dare una risposta Euler ha infatti modellato matematicamente la connessioni tra le varie zone della città. Togliendo tutti i dettagli non utili, come la lunghezza dei punti, la larghezza del fime, la forma delle isole, e via dicendo, e lasciando solo ed esclusivamente le informazioni sulle connessioni tra le varie zone e sul numero di ponti, Euler introduce al mondo il concetto di grafo. Ridotta all'osso, Königsberg diventa quattro punti e sette linee.

In questa forma la risposta arriva da sé. Ogni volta che si entra in una zona bisogna poi uscirne, consumando due ponti alla volta: una zona toccata nel mezzo della passeggiata deve quindi avere un numero pari di ponti, e le sole a potersi permettere un numero dispari sono quella di partenza e quella di arrivo. A Königsberg il Kneiphof ha cinque ponti e le altre tre zone ne hanno tre ciascuna: sono tutti numeri dispari. Questo significa che la passeggiata desiderata non esiste perché non può esistere.

La teoria dei grafi è oramai di fondamentale importanza nello studio della matematica e dell'informatica. Reti stradali, pagine del web, corridoi di un labirinto: tutti scenari che possono essere modellati da un grafo. Abbiamo degli oggetti, i nodi del grafo, e delle relazioni tra questi oggetti, che sono gli archi che connettono i vari nodi del grafo.

È tempo ora di formalizzare qualche idea.

Definizione

Utilizzando il linguaggio della matematica, un grafo è una coppia \(G = (V, E)\), dove:

• \(V\) è un insieme di vertici, o nodi

  \[V = \{\; v_1 \;,\; v_2 \;,\; v_3 \;,\; \ldots \;,\; v_n\}\]

• \(E\) è un insieme di archi, ciascuno dei quali collega due vertici

  \[E \subseteq \big\{\, \{u, v\} \;:\; u, v \in V \,\big\}\]

Possiamo rappresentare un grafo sia utilizzando la notazione matematica appena introdotta, e sia graficamente. Consideriamo ad esempio il seguente grafo:

• \(V = \{a, b, c, d, e\}\)
• \(E = \big\{\{a,b\}, \{a,c\}, \{b,d\}, \{c,d\}, \{d,e\}\big\}\)

Graficamente possiamo rappresentare tale grafo come segue.

Quando un arco è un insieme non ordinato \(\{u, v\}\) il grafo è non orientato, e l'arco si percorre in entrambi i versi. Questo significa che da \(u\) possiamo andare a \(v\) e, viceversa, da \(v\) possiamo andare ad \(u\). Se invece un arco è una coppia ordinata $(u, v)$ il grafo è detto orientato. In questo progetto i grafi sono sempre non orientati, come i corridoi di un labirinto.

Un grafo può anche essere pesato. In questi casi abbiamo che ad ogni arco è associato un numero. Possiamo immaginare quel numero come un peso, come la lunghezza di una strada. Alcune strade sono più lunghe di altre, e quindi hanno pesi diversi. Matematicamente per rappresentare un grafo pesato abbiamo una funzione di peso \(w : E \to \mathbb{R}\) che assegna ad ogni arco \(e \in E\) un peso \(w(e) \in \mathbb{R}\).

Il vocabolario minimo

Andiamo a definire alcuni termini utili quando lavoriamo con dei grafi. Questi saranno utili per poi procedere a vedere come implementare un grafo in un qualsiasi linguaggio di programmazione.

• Due vertici collegati da un arco si dicono adiacenti.

• Dato un vertice \(v\), Il grado di \(v\) è indicato con \(\deg(v)\) e rappresenta il numero di archi che toccano \(v\).

• Un cammino è una sequenza di vertici \(v_0, v_1, \dots, v_k\) in cui tutti i vertici consecutivi sono adiacenti. La sua lunghezza è \(k\), il numero di archi.

• Un ciclo è un cammino che torna al vertice di partenza senza ripetere archi.

• Un grafo è connesso se esiste un cammino fra ogni coppia di vertici.

• Un albero è un grafo connesso e senza cicli.

Come vedremo più avanti, un labirinto ben costruito è esattamente un albero.

Liste di adiacenza

Ci sono vari modi di memorizzare un grafo in memoria. Partiamo dal più semplice: un dizionario che ad ogni vertice associa la lista dei suoi vicini. Queste sono proprio le liste di adiecenza.

adjacency = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d"],
    "d": ["b", "c", "e"],
    "e": ["d"],
}

Osserviamo che in un grafo non orientato ogni arco compare due volte: b è fra i vicini di a, ed a è fra i vicini di b. Entrambe le occorrenze devono essere inserite in quanto permettono di navigare il grafo in due direzioni diverse.

Scheletro del progetto

Iniziamo quindi a scrivere il nostro codice. Possiamo partite con questa struttura, dove in graph.py avremo tutta la logica principale dei grafi.

Makefile      
.gitignore
graph.py      

Il modulo graph.py definisce funzioni che lavorano su dei grafi. Importarlo non deve eseguire nessun codice. Il compito iniziale quindi è implementare le seguenti due funzioni. Da notare l'utilizzo dei type hints.

def degree(adjacency: dict[str, list[str]], u: str) -> int
def edge_count(adjacency: dict[str, list[str]]) -> int

Dove la funzione degree ritorna il grado di u, mentre edge_count ritorna il numero di archi. Per calcolare tale numero è possibile sfruttare un risultato matematico chiamato "lemma delle strette di mano".

Una volta scritto il codice dobbiamo ottenere questo comportamento

>>> adjacency = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d"],
    "d": ["b", "c", "e"],
    "e": ["d"],
}
>>> from graph import degree, edge_count
>>> degree(adjacency, "d")
3
>>> edge_count(adjacency)
5

Makefile e type hints

Ogni funzione del progetto va annotata con i type hints. Questi sono controllati da mypy. Il Makefile per adesso deve offrire due target.

• all

  il target di default, che lancia mypy su tutti i sorgenti.

  all:
  	@python3 -m mypy --disallow-untyped-defs --disallow-incomplete-defs $(wildcard *.py)

• clean

  elimina __pycache__ e .mypy_cache, e deve funzionare anche quando le cartelle non ci sono.

I file generati dall'interprete non vanno versionati, e vanno quindi messi nel .gitignore.

__pycache__/
*.pyc
.mypy_cache/

Alla fine dobbiamo ottenere il seguente risultato.

$ make
Success: no issues found in 1 source file