Ricerca operativa 1+2

Handshaking

∑d(i) = 2m

• ∑dⁱ⁺(i) = ∑d_i-(i) = m

In un digrafo ogni arco contribuisce una volta per il grado entrante e una volta per il grado esterno.

Grafo Completo

m = (n(n-1))/2

Grafo Connesso

m ≥ n-1

Grafo Aciclico

m ≤ n-1

Albero

• Un albero con |V| = 1 è possibile chiuso o foglia
• ∑d(i) = 2m = 2(n-1) = 2m ≤ 2
• Un albero con |V| > 1 possiede un cammino per ogni coppia di vertici

G è bipartito se esiste una partizione (V₁, V₂) tale che ogni arco è incidenti uno a un vertice di V₁ e uno di V₂.

Grafo Bipartito

In ogni ciclo ci sono un numero pari di spigoli.

Matching

Sottinsieme di spigoli t.c. un sottografo risultante ogni vertice ha grado non superiore a 1.

Clique

Sottinsieme di vertici mutuamente adiacenti.

Insieme Stabile

Sottinsieme di vertici mutuamente non adiacenti. Cardinalità α(G).

Vertex Cover

Sottinsieme di vertici t.c. ogni spigolo è incidente in almeno un vertice. Cardinalità W(G).

L'insieme stabile e il vertex cover sono complementarietà: m = |V| ≤ α(G) + W(G).

Colorazione

È una funzione che assegna due colori diversi ai vertici di uno stesso spigolo.

Circuito Euleriano

È scritto se e uno solo volta ogni spigolo del grafo.

Ciclo Hamiltoniano

È scritto se e uno solo volta ogni vertice del grafo.

• Grafo connesso ⇔ Euleriano ⇔ Ogni vertice ha grado pari

• Grafo Hamiltoniano ⇔ d(u)+d(v) > m ∀ coppia di vertici in V

Isomorfismo

Due grafi G = (V,E) e G' = (V',E') si dicono isomorfi. (G ≅ G') ≡ ∃ una biiezione.

Una funzione q: V → V'. x ∈ V, e q(x) ∈ V' tale che (x,y) ∈ E ↔ (q(x),q(y)) ∈ E'.

1. ∃ un isomorfismo se i due grafi hanno lo stesso numero di vertici e spigoli: |V| = |V'|, |E| = |E'|.
2. ∀ x ∈ V grado(x) = grado(q(x)).
3. Se G è simple e (x,y) ∈ E → anche in G' deve avere lo stesso grado.

Per testare che le adiacenze siano preservate si cerca un opportuno permutazione delle colonne delle matrici di adiacenze (nxn) di G per G' o dei caricche delle matrici di adiacenze superiori.

Connesione

1. G = (U,V) ha k componenti connesse.
2. Se n ≥ k allora m ≥ n ·1 in componenti connessi.
3. Un grafo con m < n - k ha k componenti connesse.

PERMUTAZIONI SEMPLICI

PERMUTAZIONI CON RIPETIZIONE

DISPOSIZIONI SEMPLICI

DISPOSIZIONI CON RIPETIZIONE

COMBINAZIONI SEMPLICI

COMBINAZIONI CON RIPETIZIONE

possibili CAMMINI RECORRENTI DI KN

gruppo di omom. factor della chiamara dei comandos

Una importanza l'ordine?

possibile sottogruppo

NO → COMBINAZIONI

SI → DISPOSIZIONI O PERMUTAZIONI

Un certo elemento in ogni raggruppamento puó essere ripetuto?

SI → COMBINAZIONI CON RIPETIZIONI

NO → COMBINAZIONI SEMPLICI

k = n?

SI → PERMUTAZIONI

k elementi sono distinti

NO → DISPOSIZIONI

Un certo elemento piú componenti puó essere ripetuto piú volte?