Matroid

Matroid je uređeni par ${\displaystyle M=(S,{\mathcal {I}})}$ formiran na sledeći način:

1. Skup ${\displaystyle S}$ je konačan.
2. Neka je ${\displaystyle {\mathcal {I}}}$ neprazna familija podskupova skupa ${\displaystyle S}$ (koji se nazivaju nezavisnim podskupovima) takva da ako je ${\displaystyle B\in {\mathcal {I}}}$ i ${\displaystyle A\subseteq B}$, tada je ${\displaystyle A\in {\mathcal {I}}}$. Ako familija ${\displaystyle {\mathcal {I}}}$ zadovoljava ovu osobinu tada je nazivamo nasleđenom (Hereditary). Primetimo da prazan skup ${\displaystyle \varnothing }$ obavezno pripada familiji ${\displaystyle {\mathcal {I}}}$.
3. Ako je ${\displaystyle A\in {\mathcal {I}},B\in {\mathcal {I}}}$ i ${\displaystyle |A|<|B|}$, tada postoji element ${\displaystyle x\in B\setminus A}$, takav da je ${\displaystyle A\cup \{x\}\in {\mathcal {I}}}$. Govorimo da struktura ${\displaystyle M}$ zadovoljava osobinu zamene.

Termin „matroid“ je uveo Vitni Hasler. On je proučavao matrične matroide, čiji su elementi ${\displaystyle S}$ redovi zadate matrice. Skup redova je nezavisan, ako su oni linearno nezavisni u običnom smislu. Lako se pokazuje da ova struktura definiše matroid.

Kao suštinu drugog primera matroida razmotrimo matroid grafa ${\displaystyle M_{G}=(S_{G},{\mathcal {I}}_{G})}$, koji je definisan pomoću pojma neorijentisanog grafa ${\displaystyle G=(V,E)}$, gde je:

• ${\displaystyle S_{G}}$ skup ${\displaystyle E}$ ivica grafa ${\displaystyle G}$,
• Ako je ${\displaystyle A}$ podskup skupa ${\displaystyle E}$, tada je ${\displaystyle A\in {\mathcal {I}}_{G}}$ ako i samo ako je ${\displaystyle A}$ necikličan tj, skup ivica ${\displaystyle A}$ je nezavisan ako i samo ako podgraf ${\displaystyle G_{A}=(V,A)}$ obrazuje šumu.

Teorema 1

Ako je ${\displaystyle G=(V,E)}$ neorijentisan konačan graf tada je ${\displaystyle M_{G}=(S_{G},{\mathcal {I}}_{G})}$ matroid.

Dokaz

Očigledno je da je ${\displaystyle S_{G}=E}$ konačan skup. Osim toga ${\displaystyle {\mathcal {I}}_{G}}$ je nasledna familija jer je podskup šume takođe šuma. Drugim rečima, odstranjivanje ivica iz acikličnog skupa ivica grafa ne može dati cikličan skup.

Na taj način ostaje nam da pokažemo da struktura ${\displaystyle M_{G}}$ odgovara osobini zamene. Pretpostavimo da su ${\displaystyle G_{A}=(V,A)}$ i ${\displaystyle G_{B}=(V,B)}$ šume grafa ${\displaystyle G}$ i da je ${\displaystyle |A|<|B|}$ , tj. ${\displaystyle A}$ i ${\displaystyle B}$ su aciklični skupovi ivica, i da u skupu ${\displaystyle B}$ ima više ivica nego u skupu ${\displaystyle A}$. Iz jedne od teorema koje su ranije razmatrane sledi da šuma u kojoj imamo ${\displaystyle k}$ ivica ima tačno ${\displaystyle |V|-k}$ drveta. Da to dokažemo pođimo od ${\displaystyle |V|}$ drveta od kojih svako ima samo jedan vrh i ne sadrži ni jednu ivicu. Tada svako rebro (ivica) koje se dodaje šumi, za jedan smanjuje broj drveta. Na taj način šuma ${\displaystyle G_{A}}$ ima ${\displaystyle |V|-|A|}$ drveta, a šuma ${\displaystyle G_{B}}$ ima ${\displaystyle |V|-|B|}$ drveta.

Kako šuma ${\displaystyle G_{B}}$ ima manje drveta od šume ${\displaystyle G_{A}}$ tada u šumi ${\displaystyle G_{B}}$ postoji ivica ${\displaystyle (u,v)}$ takva da se vrhovi ${\displaystyle u}$ i ${\displaystyle v}$ nalaze u dva različita drveta šume ${\displaystyle G_{A}}$. Pošto ova ivica spaja vrhove dvaju različitih drveta šume ${\displaystyle G_{A}}$ tada je možemo dodati u šumu ${\displaystyle G_{A}}$ ne obrazujući krug na taj način. Na taj način struktura ${\displaystyle M_{G}}$ zadovoljava osobinu zamene, čime se završava dokaz da je ${\displaystyle M_{G}}$ matroid.

Za zadati matroid ${\displaystyle M=(S,{\mathcal {I}})}$ definišimo element ${\displaystyle x\in A}$ kao proširenje skupa ${\displaystyle A\in {\mathcal {I}}}$, ako je njega moguće dodati u ${\displaystyle A}$ bez narušavanja nezavisnosti tj. ${\displaystyle x}$ je proširenje skupa ${\displaystyle A}$ ako je ${\displaystyle A\cup \{x\}\in {\mathcal {I}}}$. Kao primer razmotrimo matroid grafa ${\displaystyle M_{G}}$. Ako je ${\displaystyle A}$ nezavisan skup ivica, tada je ivica ${\displaystyle e}$ proširenje skupa ${\displaystyle A}$ ako i samo ako ne pripada tom skupu i ako njeno dodavanje skupu ne dovodi do stvaranja ciklusa.

Ako je ${\displaystyle A}$ nezavisan podskup u matroidu ${\displaystyle M}$, i ako u njemu nema proširenja (nisu moguća) tada kažemo da je ${\displaystyle A}$ maksimalan skup. Na taj način, skup ${\displaystyle A}$ je maksimalan ako se ne sadrži ni u jednom većem podskupu matroida ${\displaystyle M}$. Dole data osobina je često vrlo korisna.

Teorema 2

Svi maksimalni nezavisni podskupovi matroida imaju istu veličinu.

Dokaz:

Teoremu dokazujemo metodom svođenja na protivrečnost. Pretpostavimo da je ${\displaystyle A}$ maksimalan nezavisan podskup matroida ${\displaystyle M}$ i da postoji drugi maksimalni nezavisni podskup ${\displaystyle B}$ matroida ${\displaystyle M}$ čija je veličina veća od veličine podskupa ${\displaystyle A}$. Tada iz osobine zamene sledi da skup ${\displaystyle A}$ možemo proširiti do većeg nezavisnog skupa ${\displaystyle A\cup \{x\}}$ pomoću nekog elementa ${\displaystyle x\in B\setminus A}$ što je suprotno pretpostavci o maksimalnosti skupa ${\displaystyle A}$.

Kao ilustraciju primene ove teoreme razmotrimo primenu na matroid grafa ${\displaystyle M_{G}}$ vezanog za neorijentisani povezani graf ${\displaystyle G}$. Svaki maksimalni nezavisni podskup matroida ${\displaystyle M_{G}}$ mora da bude (da predstavlja) slobodno drvo koje ima tačno ${\displaystyle |V|-1}$ ivica koje spajaju vrhove grafa ${\displaystyle G}$. Takvo drvo se zove osnovno drvo grafa ${\displaystyle G}$.

Kažemo da je matroid ${\displaystyle M=(S,{\mathcal {I}})}$ težinski, ako je sa njim povezana težinska funkcija ${\displaystyle w}$ koja svakom elementu ${\displaystyle x\in S}$ pridružuje strogo pozitivnu težinu ${\displaystyle w(x)}$. Težinska funkcija ${\displaystyle w}$ se uopštava na podskupove skupa ${\displaystyle S}$ putem sumiranja:

${\displaystyle w(A)=\sum _{x\in A}w(x)}$ za proizvoljni podskup ${\displaystyle A\subseteq S}$.

Na primer, ako sa ${\displaystyle w(e)}$ označimo dužinu ivice ${\displaystyle e}$ matroida grafa ${\displaystyle M_{G}}$, tada je ${\displaystyle w(A)}$ ukupna dužina svih ivica koje pripadaju skupu ${\displaystyle A}$.

Види још

• Теорија графова
• Похлепни алгоритам

Литература