Algoritmi - Dubbio sui matroidi
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?:(

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?:(
Risposte
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.
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.
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

non capisco

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?
Avrei potuto scegliere anche un altro elemento...
Capito adesso?