 |
NoWhereMan |
.illuminato.
Registered: Jul 2003
Posts: 222 (0.03 al dì)
Location: Segrate (MI)
Corso: Dottorato in Informatica
Anno:
Time Online: 1 Day, 21:56:46 [...]
Status: Offline
Edit | Report | IP: Logged |
nota: con 2^E indico 2 con E scritto all'apice, come nelle potenze, e con {} l'insieme vuoto
Si abbiano due insiemi E ed F, dove F è un sottoinsieme delle parti di E con due particolari proprietà
dati
E={a,b,c}
P(E) = 2^E = { {}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c} }
Gli elementi dell'insieme delle parti di E (ricordiamolo), come si vede, sono a loro volta degli insiemi.
La coppia <E, F> è un sistema di indipendenza se, presi due elementi di F, se A è elemento di F, e B è sottoinsieme di A allora B è elemento di F;
ad esempio se F1 = { {}, {b}, {a}, {a, b} } //mi sorge un dubbio... {} fa parte di F1?? :/
<E, F1> è s.i. infatti {a,b} elem di F1, {b} è contenuto in {a,b}, e anche {b} è elem di F1
Un matroide è un s.i. tale che presi due elementi A,B, di F (i quali, ricordiamolo ancora, sono insiemi), se la cardinalità di B è uguale alla cardinalità di A meno uno, cioè se |A| = |B| + 1, ovverosia se A ha un elemento in più di B, allora esiste un elemento "b" contenuto in B ma non in A allora l'unione tra {b} e A è comunque un elemento del matroide.
F1, per esempio, dovrebbe essere un matroide :B
infatti presi B={a} e A={a,b}, |{a}|=1, |{a,b}|=2,
la differenza tra A e B, A-B = {b}
che è proprio l'elemento che unito a B dà ancora A
si noti che <E,P(E)> è un matroide (e quindi anche un s.i.)
spero di essere stato d'aiuto :/
ciao
|
kingoff
