Ricerca Operativa

Il problema di Koenigsberg

La teoria dei grafi riconduce la sua origine al '700 per un "divertimento" di Eulero. Egli si chiese se fosse possibile partire e tornare al punto di partenza percorrendo solo una volta, da ogni ponte. Nel mio approccio associo un modello che permette di isolare gli aspetti ricorrenti del problema. La soluzione di Eulero era sbagliata, ma pose le basi della teoria dei grafi. Fu poi corretto 150 anni dopo da un matematico tedesco. Il modello di cui appunto abbiamo bisogno è il grafico.

Condizioni del problema

È un problema di perizia: ogni volta che "attraverso" un nodo, percorro due ponti. Dunque, condizione necessaria perché esista un circuito euleriano è che il numero di archi incidenti su ogni nodo deve essere pari. E questo fu l'errore di Eulero: questa condizione è corretta, ma non è sempre vero.

Questo problema è risolvibile con un algoritmo numerativo: le possibili soluzioni sono n!=!. In questo caso, il problema di Koenigsberg la teoria dei grafi riconduce la sua origine al '700 per un divertimento di Eulero. Egli si chiese se fosse possi - bile partire e tornare al punto di partenza percorrendo solo una volta da ogni ponte.

Modellazione e algoritmo

Nel mio approccio uso un modello che permette di isolare gli aspetti ricorrenti del problema. La soluzione di Eulero era sbagliata, ma pose le basi della teoria dei grafi. Fu poi corretto 250 anni dopo da un matematico tedesco. Il modello di cui appunto abbiamo bisogno è il grafico. È un problema di perizia: ogni volta che "attraverso" un nodo, percorro due ponti. Dunque, condizione necessaria perché esista un circuito euleriano è che il numero di archi incidenti su ogni nodo deve essere pari. Questo fu l'errore di Eulero: questa condizione è corretta, ma non è sempre vero.

Questo problema è risolubile con un algoritmo numerativo: le possibili soluzioni sono n!, ed in questo caso, i punti. Questo algoritmo non è enormemente efficiente.

Formalizzazione del problema

Indicheremo con m = # vertici, m = # spigoli. Formalizzare un problema si riconduce a:

• Dare condizioni necessarie e sufficienti
• Dare condizioni di ottimalità

Grafo: un grafo è una coppia G = (V, E) dove V è un insieme di nodi (o vertici) ed E è un insieme di rigoli (o archi). E è un insieme di coppie non ordinate di vertici, ed è sottoinsieme delle coppie che posso formare a partire da un certo insieme di vertici: E = (V/2).

Ad esempio V = {A, B, C, D}, E = {AB, AC, AD, BC, CD}. Una rappresentazione grafica è appunto la rappresentazione di un grafo. Assumeremo sempre che i grafi siano semplici (ovvero auto anelli e rigoli paralleli tra una coppia di vertici esiste al più uno spigolo). In un grafo con rigoli paralleli è detto multinsieme, ovvero un insieme in cui degli spigoli tra due nodi possono ripetersi più volte. Tra parentesi graffe "{...}" si indica un insieme non ordinato. Tra parentesi tonde "(...)" si indica un insieme ordinato.

Srigoli incidenti

Due srigoli sono incidenti se hanno un vertice in comune. I vertici in comune tra uno srigoli si dicono estremi. Il grado di un vertice è uguale al numero di srigoli incidenti su quel vertice. Per il problema di Koenigsberg, è condizione necessaria che il grado di ogni vertice sia pari.

Handshaking lemma: Σ_{v ∈ V} deg(v) = 2m   # srigoli

Corollario: Il numero di vertici di grado dispari di un qualunque grafo è un numero pari.

Viste di un grafo

Walk → B, M, C, C, D, D, D, A, A, AB... Walk aperto se il punto d'inizio è diverso dal punto di fine. Walk chiuso se il punto d'inizio è proprio il punto finale. Trail - percorso dove non passo per due volte o più sullo stesso srigolo (parleremo di trail aperti e chiuso - circuito). Un trail chiuso che visita tutti gli srigoli una sola volta. Si dice circuito euleriano.

Path: è un cammino che non visita lo stesso vertice due volte, cioè un trail che visita ogni vertice al più una volta. Anche qui distingueremo il path aperto ed il path chiuso (ciclo).

Connessione di un grafo (per grafi non orientati)

Due vertici di un grafo sono connessi se esiste un walk/trail/path che li unisce. Una relazione si dice di equivalenza se gode delle proprietà di: riflessività; simmetria; transitività. Queste relazioni partizionano il mio insieme in classi. Nel nostro caso l'insieme di partenza sono i vertici del grafo. La connessione è la relazione di equivalenza sui vertici quindi le nostre classi sono le nostre componenti.