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 archi, con m = |E|. Un grafo che contiene un ciclo euleriano è detto grafo euleriano.

TEOREMA

Sia G connesso, le seguenti affermazioni sono equivalenti:

1. G è euleriano
2. Ogni nodo di G ha grado pari.
3. G si può ottenere come unione di cicli disgiunti sugli archi.

Questo teorema ci fornisce due condizioni necessarie e sufficienti: (2-3) affinché un grafo sia euleriano.

Dim: dobbiamo mostrare che 1 => 2, 2 => 3, 3 => 1

• 1 => 2

Se G è euleriano allora ∃ un ciclo euleriano C. Vi₁E₁Vi₂Vi₂E₂Vi₃...Vi_mE_mVi₁

Se d_G(Vi_k) il grado in G del nodo Vi_k. Questo grado è ottenuto dagli archi ...E_h - E_h che hanno contribuito 1 (sono gli archi che lo precedono o lo seguono nella sequenza definita da C). Poiché inoltre Vi_h-Vi_k per qualche (h,k), con k ≠ h allora avremo altre contribuzioni pari al grado del nodo.

• 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 è un grafo connesso aciclico, quindi G deve avere almenoun un ciclo, C₁.Sia G₁ = G\C₁ ottenuto rimuovendo da G gli archi di C₁

d_G1(V) : 0 oppure d_G1(V) pari

d(a(V)) ≤ 2 *(a(V)) se V ∈ C₁

d_G1(V) = 0 se V ∈ C₁

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 archi, con m=|E|. Un grafo che contiene un ciclo euleriano è detto grafo euleriano.

Teo:

Sia G connesso, le seguenti affermazioni sono equivalenti:

1. G è euleriano
2. Ogni nodo di G ha grado pari.
3. G si può ottenere come unione di cicli disgiunti sugli archi.

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

affinché un grafo sia euleriano.

Dim:

Dobbiamo mostrare che 1 → 2, 2 → 3 e 3 → 1

1 → 2

Se G è euleriano allora ∃ un ciclo euleriano C.

C: V_iE_i,V_iC_i...V_im,E_m,V_i.

Sia d_G(V_i) il grado in G del nodo V_i. Questo grado è ottenuto dagli archi E_ih-1 e E_ih che hanno contribuito 1 (sono gli archi che lo precedono e lo seguono nella sequenza definita da C). Poiché inoltre V_ih,V_ik per qualche (h,k), con h≠k allora avremo altre contributi pari al grado del nodo ⁺ ₊pari.

2 → 3

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

→G non ha nodi di grado 1.

Un grafo connesso senza nodi di grado 1 non è un albero, e un albero è un grafo connesso aciclico, quindi G deve avere almeno un ciclo, C₁.

Sia G₁:G\C₁ ottenuto rimuovendo da G gli archi di C₁

d_G1(V′)

• 0 oppure d_G1(V)

d_G1(V′) se V∅C₁

d_G1(V′) = {

• 0 se V∅C₁

}

Se d_G(v)=0 allora v è un nodo isolato. Se G è costituito solo danodi isolati. Allora segue la tesi, altrimenti, si consideri una delle componenti connessedi G

in cui ogni nodo ha grado pari: v è in un ciclo C₂.Sia G₂ = G \ C₁.Come sopra, se G₂ è costituito solo da nodi isolatisegue la tesi, altrimenti si itera il ragionamento.Abbiamo trovato cicli C₁ C₂ ... C_k la cui unione è G.3 => 1

Siano C₁, C₂, ... C_k cicli disgiunti, la cui unione è G.Consideriamo C₁, all'ipotesi di connessione si ha che ∃ almeno un ciclo C_i conalmeno un nodo in comune con C₁ (i ≠ 1). Senza perdere di generalitàsupponiamo che questo ciclo sia C₂, e sia C₁₂ il ciclo che si ottiene unendo,intersecando C₁ con C₂, ad esempio:

C₁: A-B-C-D-A

C₁: B-F-E-B

C₁₂: A-B-F-E-B-C-D-A

• C₁

-G è connesso => ∃ C₁ ≠ ⾺, ∀i ≠ 1 con un nodo in comune con C_i