Algoritmi - Dubbio sui matroidi

[Larios1]

Dato un grafo non orientato



Per ogni grafo non orientato G una qualsiasi foresta di G è sempre un matroide.

A me è venuto pero un dubbio... se avessi

A={af,fe}
B={ae,ab,bc}

Faccio la verifica dalla definizione di matroide...

|B|=|A| + 1 è verificata

ma facendo (B-A) + A verrebbe fuori un ciclo...cosa che non puo esserci nelle foreste di G.

Dove sbaglio?:(

[pat871]

Beh le prime due proprietà del matroide sono verificate semplicemente.
Per la terza hai che:
Se per esempio prendi B e A come li hai definiti te, hai che $|B| = |A| + 1$,
quindi per la terza proprietà del matroide deve esistere una $x in B-A$, per cui $A cup {x}$ è di nuovo una foresta.
In questo caso hai che per esempio $x = {ab}$, infatti $A cup {ab} = {af,fe,ab}$ è di nuovo una foresta.

In generale se infatti hai due foreste $A$ e $B$ con $|B| = |A| + 1$, puoi infatti sempre trovare un elemento $x$ che appartiene a $B-A$ per cui $A cup {x}$ è di nuovo una foresta, ovvero senza un ciclo.

[Larios1]

ok, allora quello che sbaglio è nel passaggio B -A, ma perchè dalla differenza esce ${ab}$ ? avrei detto che il risultato fosse B stesso

non capisco

[pat871]

No aspetta, in questo caso $B-A = B = {ae,ab,bc}$ perché nessun elemento di $A$ è contenuto in $B$. Poi quello che dice la terza proprietà è che esiste un elemento x in $B-A = B$ per cui $A cup {x}$ è di nuovo una foresta.
Avrei potuto scegliere anche un altro elemento...

Capito adesso?