ESERCIZIO 1

(1)

Disegnare un grafo G = (V, E) che abbia le seguenti caratteristiche:

a) G è connesso,

b) G soddisfa il teorema di König, e c) α(G) + τ(G) = 8.

ESERCIZIO 1

(2)

Ricordiamo il teorema di Gallai:

ESERCIZIO 1

Dal teorema di Gallai deduciamo che G deve avere 8 nodi.

Per ogni grafo G con n nodi si ha:

α(G) + τ(G) = n (1) Se inoltre G non ha nodi isolati

μ(G)+ ρ(G) = n (2)

(3)

Ricordiamo il teorema di König:

ESERCIZIO 1

Dal teorema di König deduciamo che G deve essere bipartito.

Se G = (X, Y, E) è un grafo bipartito allora μ(G) = τ(G).

Proviamo a disegnare un grafo bipartito con 8 nodi.

G soddisfa le condizioni a), b) e c)?

Il grafo è connesso ⇒ a) è verificata.

1 2 3 4

a b c d

(4)

ESERCIZIO 1

1 2 3 4

a b c d

Calcoliamo su G un massimo matching M e un minimo trasversale T:

M={(1,a), (2,b), (3,c), (4,d)}

μ(G) = 4

1 2

c T={1, 2, 3, 4}

τ(G) = 4

Poiché μ(G) = τ(G), il teorema di König è soddisfatto

b) è verificata.

d

(5)

ESERCIZIO 1

1 2 3 4

a b c d

Ricordiamo che, se T è un trasversale su G allora V–T è un insieme stabile. In particolare, se T è minimo allora V–T è massimo.

3 4

a b

V–T={a, b, c, d}

α(G) = 4

Pertanto, α(G) + τ(G) = 8 ⇒ c) è verificata.

(6)

Disegnare un grafo G = (V, E) che abbia le seguenti caratteristiche:

a) G è connesso,

b) G soddisfa il teorema di König, c) α(G) + ^μ(G) = 9, e

d) ρ(G) = 8.

ESERCIZIO 2

(7)

Poiché deve essere verificato il teorema di König, deduciamo che

• il grafo G deve essere bipartito, e

• su G deve essere verificata la condizione μ(G) = τ(G).

ESERCIZIO 2

Dalla condizione c) sappiamo che deve essere α(G) + μ(G) = 9.

Pertanto, dal teorema di König e dalla condizione c) abbiamo:

α(G) + τ(G) = 9.

Dal teorema di Gallai deduciamo che G deve avere 9 nodi.

(8)

ESERCIZIO 2

Proviamo a disegnare un grafo bipartito con 9 nodi.

G soddisfa le condizioni a), b) c) e d)?

Il grafo è connesso ⇒ a) è verificata.

1 2 3

4 a

5 6 7 8

(9)

ESERCIZIO 2

1 2 3

4 a

5 6 7 8

Calcoliamo su G un massimo matching M e un minimo trasversale T:

M={(1,a)}

μ(G) = 1

T={a}

τ(G) = 1

a

Poiché μ(G) = τ(G), il teorema di König è soddisfatto

b) è verificata.

(10)

ESERCIZIO 2

1 2 3

4 a

5 6 7 8

Un massimo insieme stabile su G è dato da V–T: ₁

2 3

4 5 6 7 8

V–T={1, 2, 3, 4, 5, 6, 7, 8}

α (G) = 8

Pertanto, α(G) + τ(G) = 9 ⇒ c) è verificata.

(11)

ESERCIZIO 2

Calcoliamo il minimo edge-cover F su G: ₁

2 3

4 a

5 6 7 8

F={(1,a), (2,a), (3,a), (4,a), (5,a), (6,a), (7,a), (8,a)}

ρ (G) = 8

Poiché ρ(G) = 8 ⇒ d) è verificata.

(12)

Dato il grafo in figura G e il matching M = {(1,2)}

determinare i valori di un massimo matching e di un minimo trasversale.

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5

(13)

Innanzi tutto dobbiamo verificare che G sia un grafo bipartito.

Vediamo se G è bicolorabile:

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5 1

2

3

6

10

5

8

4 7

9 1

3

6

7

9

2 4

5

8

10 G è bipartito

(14)

Step 1: Matching corrente: M = {(1,2)}.

Scegliamo un nodo esposto rispetto a M: v = 3.

LABEL (3) = PARI

Nodi adiacenti a v = δ (3) = {2, 4, 10}

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5 3

P

Avviamo la procedura esplora pari:

Analizziamo i nodi in δ(3):

2 ∈M ⇒ LABEL (2) = DISPARI, pred (2) = 3 4∉M ⇒ STOP, pred (4) = 3,q = 4

D

q

Cammino aumentante: P = {(3,4)}

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (3,4)}.

(15)

Step 2: Matching corrente: M = {(1,2), (3,4)}.

LABEL (6) = PARI

Nodi adiacenti a v = δ (6) = {4}

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5

4 ∈M ⇒ LABEL (4) = DISPARI, pred (4) = 6

6 P D

(16)

LABEL (6) = PARI

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5

Avviamo la procedura esplora dispari:

u = 3 =nodo accoppiato a 4 nel matching M LABEL (3) = PARI, pred (3) = 4

6 P

P D

(17)

LABEL (6) = PARI

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5 6

P

P D

Nodi adiacenti a v = δ (3) = {2,10,4}

2 ∈M ⇒ LABEL (2) = DISPARI, pred (2) = 3 10∉M ⇒ STOP, pred (10) = 3,q = 10

Cammino aumentante: P = {(6,4), (4,3), (3,10)}

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (3,10), (6,4)}.

D q

(18)

Step 3: Matching corrente: M = {(1,2), (3,10), (6,4)}.

LABEL (5) = PARI

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

55 P

7∉M ⇒ STOP, pred (7) = 5,q = 7 q Cammino aumentante: P = {(5,7)}

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (3,10), (6,4), (5,7)}.

(19)

Step 4: Matching corrente: M = {(1,2), (3,10), (6,4), (5,7)}.

LABEL (8) = PARI

Nodi adiacenti a v = δ (8) = {9,7}

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5

8 P

9∉M ⇒ STOP, pred (9) = 8,q = 9 q

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (3,10), (6,4), (5,7), (8,9)}.

(20)

Poiché non esistono nodi esposti rispetto al matching corrente, possiamo concludere che M è massimo.

ESERCIZIO 3

2 1

3 4

6

7

10 9

8

5

M = {(1,2), (3,10), (6,4), (5,7), (8,9)} ⇒ ^μ(G) = 5.

(21)

Per calcolare un minimo trasversale, riscriviamo G nella forma con le due partizioni:

ESERCIZIO 3

1 3

6

7

9

2 4

5

8

10

X₁ = insieme di nodi saturi rispetto a M = {1,3,6,7,9}

X₂ = X – X₁ = ∅

Y₁ = nodi raggiungibili da X₂ = ∅ Y₂ = Y – Y₁ = {2, 4, 5, 8, 10}

X₁

Y₂

(22)

Come scegliamo i nodi da inserire nel trasversale T?

Per ogni arco (x_i,y_i) ∈ M,

• Se y_i ∈ Y₁ ⇒ y_i ∈ T

• Se y_i∉ Y₁ ⇒ x_i ∈ T

ESERCIZIO 3

Nella situazione corrente, poiché Y₁ = ∅ il trasversale T conterrà solo i nodi della partizione X.

Pertanto T = {1,3,6,7,9} ⇒ τ (G) = 5.

OSSERVAZIONE: Se il massimo matching su G è PERFETTO, allora il minimo trasversale T coincide con la partizione X di G.

1 3

6

7

9 1 3

6

7

9

2 4

5

8

10

X₁ Y₂

(23)

Dato il grafo in figura G e il matching M = {(1,4), (6,8)}

determinare i valori di un massimo matching e di un minimo trasversale.

ESERCIZIO 4

1 2

3 4

6 7

10 9

8 5

(24)

ESERCIZIO 4

1 2

4 3

6 7

10 9

8 5

Vediamo se G è bicolorabile:

1 2

4

7 8

10 3 5

6

9

1 3 5 6 9

2 4 7 8 10 G è bipartito

(25)

LABEL (5) = PARI

ESERCIZIO 4

4 ∈M ⇒ LABEL (4) = DISPARI, pred (4) = 5 5

P

D

1 2

3 4

6 7

10 9

8 5

(26)

LABEL (5) = PARI

ESERCIZIO 4

P

5 P

D

1 2

3 4

6 7

10 9

8 5

(27)

LABEL (5) = PARI

ESERCIZIO 4

P

5 P

D

1 2

4 3

6 7

10 9

8 5

Nodi adiacenti a 1 = δ (1) = {2, 4}

2 ∉M ⇒ STOP, pred (2) = 1,q = 2 q

Cammino aumentante: P = {(5,4), (4,1), (1,2)}

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (5,4), (6,8)}.

(28)

7

9∉M ⇒ STOP, pred (9) = 7,q = 9

Aggiorniamo il matching corrente: M = (M – P)∪(P – M) = {(1,2), (5,4), (6,8), (7,9)}.

Step 2: Matching corrente: M = {(1,2), (5,4), (6,8)}.

LABEL (7) = PARI

ESERCIZIO 4

7 P D

1 2

4 3

6

10 9

8 5

q

(29)

10 7

6∈M ⇒ LABEL(6) = DISPARI, pred (6) = 10 9∈M ⇒ LABEL(9) = DISPARI, pred (9) = 10

LABEL (10) = PARI

ESERCIZIO 4

P 10 D

1 2

4 3

6

9 8

5

D

(30)

10 7

LABEL (10) = PARI

ESERCIZIO 4

10 P D

1 2

4 3

6

9 8

5

D

P

(31)

10 7

LABEL (10) = PARI

ESERCIZIO 4

10 P D

1 2

3 4

6

9 8

5

D P

P

Non esistono nodi NON ETICHETTATI tra gli adiacenti del nodo 8.

Non esistono cammini aumentanti a partire dal nodo esposto v=10 ⇒Possiamo

cancellare v=10 e tutti gli archi incidenti su

(32)

7

LABEL (10) = PARI

ESERCIZIO 4

1 2

3 4

6

9 8

5

NON POSSO FERMARMI SE ESISTE QUALCHE NODO ESPOSTO RISPETTO AL MATCHING CORRENTE CHE NON E’

ANCORA STATO ANALIZZATO!

v = 3 è un nodo esposto rispetto ad M non ancora analizzato.

(33)

3

7

2∈M ⇒ LABEL(2) = DISPARI, pred (2) = 3 4∈M ⇒ LABEL(4) = DISPARI, pred (4) = 3

LABEL (3) = PARI

ESERCIZIO 4

P

1 2 D

4 3

6

9 8

5 D

(34)

ESERCIZIO 4

3

7 P

1 2 D

4 3

6

9 8

5 D

LABEL (3) = PARI

P

(35)

ESERCIZIO 4

Nodi adiacenti a 5 = δ (5) = {4}

Non esistono cammini aumentanti a partire dal nodo esposto v=3 ⇒Possiamo

cancellare v=3 e tutti gli archi incidenti su v..

LABEL (3) = PARI

3

7 P

1 2 D

4 3

6

9 8

5 D

P

(36)

ESERCIZIO 4

POICHE’ NON ESISTONO ALTRI NODI ESPOSTI RISPETTO AL MATCHING CORRENTE CHE NON SONO STATI ANALIZZATI, POSSIAMO CONCLUDERE CHE IL MATCHING CORRENTE E’

MASSIMO.

LABEL (3) = PARI

7

1 2

4

6

9 8

5

M = {(1,2), (5,4), (6,8), (7,9)} ⇒ μ(G) = 4.

(37)

Per calcolare un minimo trasversale, riscriviamo G nella forma con le due partizioni:

ESERCIZIO 4

X₁ = insieme di nodi saturi rispetto a M = {1,5,6, 9}

X₂ = X – X₁ = {3}

Y₁ = nodi raggiungibili da X₂ = {2, 4}

Y₂ = Y – Y₁ = {7, 8, 10}

1 3 5 6 9

2 4 7 8 10 X₁

X₁ X₂

Y₁

Y₂

(38)

Scegliamo i nodi da inserire nel trasversale T analizzando tutti gli archi del matching massimo.

ESERCIZIO 4

1 3 5 6 9

2 4 7 8 10 X₁

X₁ X₂

Y₁

Y₂

Arco (1,2): 2∈Y₁ ⇒ 2 ∈ T

2

Arco (5,4): 4∈Y₁ ⇒ 4 ∈ T

4

Arco (6,8): 8∉Y₁ ⇒ 6 ∈ T

6

Arco (9,7): 7∉Y₁ ⇒ 9 ∈ T

9

Pertanto T = {2,4,6,9} ⇒ τ (G) = 4

(39)

ESERCIZIO 5

Siano U, A₁, ..., A_n insiemi finiti, e a₁, ..., a_n ∈ IR⁺. Sia

F={X ⊆ U : |X ∩ A_k| < a_kper ciascun k = 1, ..., n}.

Dire se la coppia (U,F) individua o meno un matroide motivando la risposta.

A₁ A₂

A₃ U

X a₁ = 3

a₂ = 1

a₃ = 1

(40)

ESERCIZIO 5

Ricordiamo che la coppia (U,F) è un matroide se valgono le seguenti condizioni:

1. ∅∈F

2. Per ogni Y⊆ X, X∈F ⇒Y∈F.

3. Dati X, Y∈F, con |X|<|Y|, esiste y∈Y tale che X ∪ {y} ∈F. Banalmente ∅∈F.

Supponiamo che X∈F. Allora |X ∩ A_k| < a_k, per ciascun k = 1, ..., n.

Se Y⊆ X, allora |Y|<|X|. Pertanto

|Y ∩ A_k| < |X ∩ A_k| < a_k.

Possiamo quindi concludere che la coppia è subclusiva.

(41)

ESERCIZIO 5

Resta da verificare se la coppia (U,F) soddisfa la proprietà di scambio.

Se pensiamo che tale proprietà sia soddisfatta dobbiamo dimostrarlo in maniera formale.

Viceversa, se pensiamo che la proprietà di scambio non sia

soddisfatta dobbiamo cercare un controesempio in cui essa non vale.

(42)

ESERCIZIO 5

Consideriamo la seguente situazione:

A₁ A₂

A₃ a₁ = 2 U

a₂ = 1

a₃ = 1 1

2 3

4 7

5 6

7 8

10 9 11

Siano: Y = {1, 4, 7, 11} e X = {1, 3, 8}. Entrambi gli insiemi appartengono a F.

Infatti:

Y ∩ A₁= {1, 4} ⇒|Y ∩ A₁|= 2 < a₁ X ∩ A₁= {1,3} ⇒ |X ∩ A₁|= 2 < a₁ Y ∩ A₂= {7} ⇒|Y ∩ A₂|= 1 < a₂ X ∩ A₂= {8} ⇒ |X ∩ A₂|= 1 < a₂

Y ∩ A₃= {11} ⇒|Y ∩ A₃|= 1 < a₃ X ∩ A₃= {8} ⇒ |X ∩ A₃|= 1 < a₃

(43)

ESERCIZIO 5

Tuttavia è immediato osservare che, per ogni y ∈Y\X, l'insieme X∪ {y}

∉F.

Pertanto la proprietà di scambio non è verificata e la coppia (U,F) non è un matroide.

Consideriamo la seguente situazione:

A₁ A₂

A₃ a₁ = 2 U

a₂ = 1

a₃ = 1 1

2 3

4 7

5 6

7 8

10 9 11