Matroid Theory - 9780198566946

Kokia yra tiesiškai nepriklausomų matricos stulpelių aibių ir miškų panašumo esmė grafike? * Kodėl godus algoritmas sujungtame grafe sukuria minimalaus svorio apimantį medį? * Ar galime polinominiu laiku patikrinti, ar matrica yra visiškai vienamodulinė? Matroidų teorija nagrinėja ir atsako į tokius klausimus. Septyniasdešimt penkerių metų matroidų tyrimo metu buvo sukurta turtinga teorija su nuorodomis į grafikus, gardelius, kodus, skersines ir projekcines geometrijas. Matroidai turi esminę reikšmę kombinatoriniam optimizavimui, o jų taikymas apima elektros ir konstrukcijų inžineriją. Šią knygą sudaro dvi dalys: pirmoji išsamiai supažindina su matroidų teorijos pagrindais, o antroje nagrinėjamos sudėtingesnės temos. Knygoje yra daugiau nei septyni šimtai pratimų ir pirmą kartą vienoje vietoje pateikiami visų pagrindinių temos teoremų įrodymai. Paskutiniuose dviejuose skyriuose apžvelgiami dabartiniai tyrimai ir išvardijama daugiau nei aštuoniasdešimt neišspręstų problemų kartu su jų sprendimų pažangos aprašymu.