Matroid je uređeni par formiran na sledeći način:

  1. Skup je konačan.
  2. Neka je neprazna familija podskupova skupa (koji se nazivaju nezavisnim podskupovima) takva da ako je i , tada je . Ako familija zadovoljava ovu osobinu tada je nazivamo nasleđenom (Hereditary). Primetimo da prazan skup obavezno pripada familiji .
  3. Ako je i , tada postoji element , takav da je . Govorimo da struktura zadovoljava osobinu zamene.

Termin „matroid“ je uveo Vitni Hasler. On je proučavao matrične matroide, čiji su elementi 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 , koji je definisan pomoću pojma neorijentisanog grafa , gde je:

  • skup ivica grafa ,
  • Ako je podskup skupa , tada je ako i samo ako je necikličan tj, skup ivica je nezavisan ako i samo ako podgraf obrazuje šumu.

Teorema 1

уреди

Ako je   neorijentisan konačan graf tada je   matroid.

Očigledno je da je   konačan skup. Osim toga   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   odgovara osobini zamene. Pretpostavimo da su   i   šume grafa   i da je   , tj.   i   su aciklični skupovi ivica, i da u skupu   ima više ivica nego u skupu  . Iz jedne od teorema koje su ranije razmatrane sledi da šuma u kojoj imamo   ivica ima tačno   drveta. Da to dokažemo pođimo od   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   ima   drveta, a šuma   ima   drveta.
Kako šuma   ima manje drveta od šume   tada u šumi   postoji ivica   takva da se vrhovi   i   nalaze u dva različita drveta šume  . Pošto ova ivica spaja vrhove dvaju različitih drveta šume   tada je možemo dodati u šumu   ne obrazujući krug na taj način. Na taj način struktura   zadovoljava osobinu zamene, čime se završava dokaz da je   matroid.

Za zadati matroid   definišimo element   kao proširenje skupa  , ako je njega moguće dodati u   bez narušavanja nezavisnosti tj.   je proširenje skupa   ako je  . Kao primer razmotrimo matroid grafa  . Ako je   nezavisan skup ivica, tada je ivica   proširenje skupa   ako i samo ako ne pripada tom skupu i ako njeno dodavanje skupu ne dovodi do stvaranja ciklusa.

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

Teorema 2

уреди

Svi maksimalni nezavisni podskupovi matroida imaju istu veličinu.

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

Kao ilustraciju primene ove teoreme razmotrimo primenu na matroid grafa   vezanog za neorijentisani povezani graf  . Svaki maksimalni nezavisni podskup matroida   mora da bude (da predstavlja) slobodno drvo koje ima tačno   ivica koje spajaju vrhove grafa  . Takvo drvo se zove osnovno drvo grafa  .

Kažemo da je matroid   težinski, ako je sa njim povezana težinska funkcija   koja svakom elementu   pridružuje strogo pozitivnu težinu  . Težinska funkcija   se uopštava na podskupove skupa   putem sumiranja:

  za proizvoljni podskup  .

Na primer, ako sa   označimo dužinu ivice   matroida grafa  , tada je   ukupna dužina svih ivica koje pripadaju skupu  .

Види још

уреди

Литература

уреди