Teoria dei grafi - Appunti

TEORIA DEI GRAFI

Dato un grafo G(V, E), non orientato, un ciclo euleriano è un ciclo che attraversa tutti gli archi del grafo una ed una sola volta. Un ciclo euleriano contiene m_1 archi, con m=|E|. Un grafo che contiene un ciclo euleriano è detto grafo euleriano.

TEO 1.

Se G è connesso, le seguenti affermazioni sono equivalenti:

• G è euleriano
• Ogni nodo di G ha grado pari
• G si può ottenere come unione di cicli disgiunti sugli archi

Questo teorema ci fornisce due condizioni necessarie e sufficienti. (2-3)

Dobbiamo mostrare che 1->2, 2->3, 3->1

1->2

Se G è euleriano allora ∃ un ciclo euleriano C. V_i₁, V_i₂, V_i_k, ..., V_i_k, ..., V_i_m, E_m, V_i_k Sia d_G(V_i_h) il grado in G del nodo V_i_h. Questo arco è ottenuto dagli archi E_j_-1 e E_j che hanno contribuito a (...), sono gli archi che lo precedono e lo seguono nella sequenza descritta in C.) Poiché in d_G(V_i_k) per qualsiasi h (h, h+1), con h+1 allora avremo sempre contributi pari al grado del nodo ( + 1 -1 =)

2->3

Sappiamo che d_G(V_i)≥2, e pari ∀V∈V

⇒ G non ha nodi di grado 1. Un grafo connesso senza nodi di grado 1 non è un albero, e un albero (...) e un grafo connesso aciclico, quindi G deve avere almeno un ciclo, C₁. Sia G_1 = G\C_i, ottenuto rimuovendo da G gli archi di C₁ d_G(V)=0 oppure d_G(V)_-2(2kv), se v ∈ C₁ d_G1 (V)={ 0 se v ∉ C₁ (..)

Se deg(u)=0

allora u è un nodo isolato. Se G è costituito solo da nodi isolati allora G è degenrativamente connesso con delle componenti connesse di G-d, in cui ogni nodo ha grado pari =2, quindi G è un ciclo. C.Q.D

Sia G un G.E.C ogni coppia di regole. Se G è costituito solo da nodi isolati segue la tesi, altrimenti C.E B.B il ragionamento.

Abbiamo trovato due cicli C1…Cn la cui unione è G

O [diverso da] 3

(ⁿ _i=1 Ci)=C1-C2

Ci sono (o due) cicli disgiunti la cui unione è G: consideriamo Ci/Cq collegati di connessione con la (almeno un ciclo Cq con almeno un nodo in comune con ci ( 1/2). Senza ciclo di generalità supponiamo che questo ciclo sia C2, e sia C1 il ciclo che si ottiene ancora iterando C1 con C2. ad esempio:

C1: A•B•C•B•D•A

C2: B•F•E•B

C1= A•B•F•E•B•C•D•A

G è connesso

(ⁿ _i=1 Ci +1 con un nodo in comune con Ci, sia esso C3

Iterando, si ottiene un ciclo C2ù 1 contenete tutti e soli gli archi di G che è quindi un grafo euleriano

Es.

(grafico non trascrivibile)

Il grafo è euleriano perché è connesso e tutti i nodi hanno grado pari.

• Determinare su di esso un ciclo euleriano
• decomponiamo il grafo in cicli
• C1=A•B•C•D•E•F•G•A
• (grafico non trascrivibile) C2=B•F•C•E•G•B

TEO S: G(V,E) orientato

G è bigrafico <=> G cicli dispari (un ciclo è dispari se e solo se ha un numero dispari di archi)

Dim (=>)

Sia G bipartito e sia (V₁, V₂) la bipartizione dell’insieme di nodi. Sia C un qualsiasi ciclo di G percorriamolo partendo da un U ∊ V₁.

Stimiamo passaggio ai nodi di V₁ ad un nodo di V₂ e così via. Tutti i nodi di V₁ che si trovano in C vengono visitati dopo aver percorso un numero dispari di archi e quelli di V₂ dopo un numero pari => C si può trovare in U solo dopo un numero pari di archi => C pari.

(=>)

Supponiamo di avere un grafo G senza cicli dispari. Supponiamo che G sia connesso (se non lo è si ripete il ragionamento per ogni componente connessa). Consideriamo un nodo u ∊ V qualsiasi e calcoliamo la distanza tra u ed ogn’altro nodo v in V. Sia d(u,v) tale distanza (come numero di archi).

• V₁ = {u ∊ V / d(u,v) pari} U {u}
• V₂ = {u ∊ V / d(u,v) dispari}

Ora bisogna dimostrare che ∄ archi a(v) Va = V₁ e v_a ∊ V₂. Facciamo vedere che E(V₂) = Ø, supponiamo per assurdo che esista un arco tra due nodi s,t tale che s,t∊V₂. Siano P_s e P_t i due cammini minimi che collegano U a s e t. Sia X l'ultimo nodo in comune ai dei cammini (X può coincidere con u nel caso in cui P_s e P_t non abbiano nodi in comune). Consideriamo il ciclo C che si forma percorrendo P_s tra x e s, l’arco (s,t) e P_t tra t e x. Calcoliamo la lunghezza di C:

L(c) = L(P_s, da x e s) + L(P_t, tra t e x) + 1 ma: L(P_s) = L(P_s, da x - s) L(P_t, da x - t) L(P_s + L(P_t, U L(P_t) = dispar = pari s,t∊V₂ => L(P_t) pari

Essendo cammini minimi P_s e P_t sono per forza uguali fino a x e t = L(P_s, x - t) = L(P_s, da x - s) sono entrambi pari => x estremo dispari L 'assurdo pari.

Questo contraddice l’ipotesi quindi gli archi che connettono V₂ con V₁.

Allo stesso modo si dimostra che se E (V₁)= Ø => G bigrafico

Dim. König

• A partire da G costruiamo un nuovo grafo G' ottenuto orientando tutti gli archi di G da V₁ a V₂ e aggiungendo 2 nodi s,t e collegando s,dai rispettivamente con tutti nodi di V₁ e con tutti i nodi di V₂ con capacità archi.
• archi da V₁ a V₂ con
• archi da s a V₁ e da V₂ a t

Là dimostrazione si basa di:

1. Su G' un matching M di cardinalità z, s' su G' un flusso ammissibile, da S a t di valore z
2. B) Su G' un vertex cover di cardinalità z

Dim. A

(=>) Dato M poniamo a 1 il flusso di ogni arco di M,e qual a 0 il sugli archi (s,i) con i ε M.s'; verifica facilamente che e un flusso ammissibile (per ogni nodo accapliato enter ed esce un quota di flussu e le capacità sono viaggiate)

((...) un cammino costituito da un numero di archi di M superiore

al numero di archi di M m', M = ...

=> quindi iniziare il cammino con un arco di M' ma questo tipo di

cammino si aumentate per M e ci� contraddice l'ipotesi.

=>(...) M e massimo

Il problema dell'assegnamento

Sia dato un grafo bipartito completo (V₁, V₂, V₁ x V₂) pesato sugli archi. Il problema dell'assegnamento consiste nel trovare un matching perfetto di peso minimo. Per questo problema sappiamo che |M| = |V₁| = |V₂| / 2.

Si può formulare come il problema di PL:

Siano c_ij i pesi degli archi i ∈ V₁ e j ∈ V₂.

Variabili:

• x_ij =
  • 1 se (i, j) ∈ M, i ∈ V₁, j ∈ V₂
  • 0 altrimenti

Funzione obiettivo

min Σ c_ij x_ij

• i ∈ V₁, j ∈ V₂

Vincoli

• ∀i = 1, ..., n Σ x_ij = 1
  • j = 1
  • ogni nodo deve essere accoppiato
• ∀j = 1, ..., n Σ x_ij = 1
  • i = 1
• x_ij ∈ {0, 1}

La matrice dei vincoli è una matrice TUM (e la matrice di incidenza nodi - archi di un grafo bipartito), e il vincolo di interezza può essere riscritto:

x_ij ≥ 0

x_ij ≤ 1 non è necessario, perchè i vincoli forzano le x_ij a valere al piu1.

Con queste osservazioni possiamo risolvere il problema dell'assegnamento con tecniche di PL e trovare soluzioni intere.

Duale

Chiamiamo a_i le variabili associate ai vincoli di V₁ e b_i quelle associate ai vincoli di V₂. Per ogni variabile del primale c’e un vincolo del duale, per ogni vincolo del primale c’e una variabile nel duale. I coefficienti diventano termini noti:

max ( Σ a_i + Σ b_j )

• a_i + b_j ≤ c_ij

∀i ∈ V₁, ∀j ∈ V₂