Ricerca Operativa

Il problema di Koenigsberg

La teoria dei grafi riconduce la sua origine al '700 per un divertimento di Eulero. Ecco in sintesi se fosse possibile partire e tornare dal punto di partenza passando 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 bloccata, ma pose le basi della teoria dei grafi (fu poi corretto 150 anni dopo da un matematico tedesco). Il modello di un appunto abbiamo bisogno e il grafo.

É un problema di verità: ogni volta che "attraverso" un nodo, percorro due ponti. Dunque condizione necessaria per cui 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 vera.

Questo problema è risolubile con un algoritmo enumerativo le possibili soluzioni sono n!. Con in questo caso:

A-B-C-I-H-G-F-E-D

3 punti: Questo algoritmo non è enormemente efficiente.

Indicheremo con

• m = # vert.
• m = # rigoli.

Svolgere un problema si riconduce a:

• dare condizioni necessorie 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 è sottinsieme delle coppie che posso formare a partire da un certo insieme di vertici.

E = (V₂)

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 esist. non più una rigolo). In un grafo con rigoli paralleli E diventa multi- insieme, ovvero un insieme in cui degli rigoli tra due nodi possono ripetersi più volte.

Tra parentesi graffe "{ ... }" si indica un insieme non ordinato Tra parentesi tonde "( ... )" si indica un insieme ordinato.

Allora ho finito, poiché a loro volta anche a e b li posso esprimere come prodotto di numeri primi, poiché sono più piccoli di m.

Un grafo G connesso con n vertici ha almeno n-1 spigoli.

Dimostrazione

(per induzione sul numero di vertici: )

Assumiamo per ipotesi induttiva che un qualunque grafo connesso con n-1 o meno vertici e' tale che:

|E(G_i)| ≥ |V(G_i)| - 1

Vogliamo dimostrare che un qualunque grafo connesso con n + 1 vertici ha questa proprieta'.

Per G connesso v ∈ V(G).

Considero G-v che ha n vertici. So che G-v ha al piu' deg(v) componenti connesse.

Siano G₁, G₂, ..., G_K le componenti connesse di G-v, con K ≤ deg(v).

Per l'ipotesi induttiva:

|E(G_i)| ≥ |V(G_i)| - 1   ∀i = 1...K

Osservo che gli spigoli del mio grafo di partenza:

• se non erano incidenti in v, sono in qualche componente connessa;
• se erano incidenti in v, noto che

|E(G)| = (∑_i=1^K|E(G_i)|) + deg(v)

|V(G)| = (∑_i=1^K|V(G_i)|) + 1

(con le dovute sostituzioni in ☐ ottengo che):

∑_i=1^K|E(G_i)| ≥ ∑_i=1^K|V(G_i)| - K

|E(G)| - deg(v) ≥ |V(G)| - 1 - K

⇒ |E(G)| ≥ |V(G)| - 1 + deg(v) - K

e' sicuramente positivo dato che K ≤ deg(v)

Regola della somma

Supponiamo di dover scegliere un oggetto da due insiemi A e B disgiunti (A ∩ B = 0). Posso farlo in |A| + |B| modi diversi, ovvero

^k∑_i=1 m_i

con m_i modalità singola in cui posso svolgere il processo.

Regola del prodotto

Supponiamo di dover scegliere più oggetti da due insiemi A e B disgiunti (A ∩ B = 0). Posso farlo in |A| · |B| modi diversi, ovvero

^k∏_i=1 m_i

Esempio

Centiamo le stringhe generabili di 9 numeri binari. Per la regola del prodotto, sono 2⁹

Esempio

Quanti codici alfanumerici posso creare nella forma

→ 21³ · 10³

Quando devo creare qualcosa, devo trovare un oggetto corrispondente con 0, ho una rappresentazione univoca. Nel nostro esempio, ad ogni sottoinsieme corrisponde una e una sola stringa binaria e viceversa.

Da qui i possibili sottoinsiemi ricavabili a partire da un insieme I con cardinalità m (|I| = n) e 2^m

Nel nostro esempio e 2¹⁰

Se volessimo sapere quante stringhe come nel nostro esempio può assumere i 9 numeri binari, ce ne sono 2³

Ogni volta che identifico un path con spigoli ottengo una sequenza ordinata di (r-1) spigoli. Un cammino da u a v con r spigoli determina un sottinsieme di (r-1) verità. Devo ordinare, tra gli m-2 verità totali (ho tolto u e v), r-1 possibili verità. Il numero di (r-1) path è

P(m-2, r-1) = &binom;(m-2)!{(m-r-1)!}

Osservazione:

C(m, k) #sottinsiemi di cardinalità k che posso formare da un insieme di m elementi.

C(m, k) = &binom;^m!/_k!(m-k)! = &binom;^{(m, m-k)}/_(m-k)(m-r)!

C(m, 0) = 1

C(m, m) = 1

C(m+1, r) = C(m, r-1) + C(m, r)

"Identità di Pascal ci aiuta a costruire il triangolo di Tartaglia"

C(m, r-1) + C(m, r) = &binom;^m!/_{(r-1)!(m-r+1)!} + &binom;^m/_r!(m-r)!=

m&binom;^r+1/_m+r+1=&binom;^(m+1)! /_r!(m+1-r)!= 

({m+1, r}) ({0,0}) 1

({1,0}) ({1,1}) 1 1

({2,0}) ({2,1}) ({2,2}) 1 2 1

…

Analisi 1

Analisi 2

Analisi 3

Analisi 4

Analisi 5

Geometria

I vertici sono i corsi mentre gli spigoli sono i corsi che nell'orario collidono e non possono essere contemporanei. Devo dare ad ogni vertice colori tali che vertici adiacenti abbiano colori diversi. In questo caso sono necessari 4 colori. Si dimostra che il numero di vertici mutuamente adiacenti sono al più tre.

Esempio

Supponiamo di avere un certo numero di processi, o lavori ("job"), da dover essere effettuati in un giorno. Dovendo assegnare delle macchine a dover svolgere i processi, le persone possono effettuarne uno solo alla volta, quante macchine servono come minimo?

ore tempo m³ che non è polinomiale.

Viesserò esistono algoritmi per il problema di colorare grafi che hanno complessità polinomiale ma per quanto bene detti questi algoritmi non garantiscono una soluzione ottima, anzi potrebbero restituire una colorazione che utilizza un numero di colori maggiore di x(G).

Ad esempio (a nome di algoritmi greedy voraci), essi sono miei. I miei si preoccupano del lungo periodo, i calcoli da ogni iterazione emi prediligono l'operazione più facile da effettuare, pregiudicando sul lungo periodo l’os- satura.

Consideriamo, per il problema di colorazione:

• Scegliere un ordinamento [V₁, V₂, ..., V_n] dei vertici di G.

1. For i = 1 to n:

   coloriamo v_i con il colore e {1,2,...,n} più pic- colo tra quelli non assegnati a vertici a un v_i è adiacente

ovvero, f(v_i) = il più piccolo colore dell’insieme {1,2,…,m} = {f(V_j), j = 1 to i - 1} / v_j adiacente a v_i

Esempio:

Esempio:

Qui, il funzionamento dell'algorit- mo dipende dall'ordinamento.

essendo literario convincentemente l'ordinamento [ u₁, u₂, u₃, ..., w₂ ] seguendo { v₁, v₄, v₂, v₁u₃, v₅ v₃ ] che