Matroid Theory - 9780198566946

Na czym polega podobieństwo liniowo niezależnych zbiorów kolumn macierzy i lasów w grafie? * Dlaczego algorytm zachłanny tworzy w połączonym grafie drzewo rozpinające o minimalnej wadze? * Czy możemy sprawdzić w czasie wielomianowym, czy macierz jest całkowicie jednomodułowa? Teoria matroidów bada tego typu pytania i udziela na nie odpowiedzi. Siedemdziesiąt pięć lat badań matroidów doprowadziło do opracowania bogatej teorii z powiązaniami z wykresami, kratami, kodami, transwersalami i geometrią rzutową. Matroidy mają fundamentalne znaczenie w optymalizacji kombinatorycznej, a ich zastosowania rozciągają się na inżynierię elektryczną i konstrukcyjną. Niniejsza książka składa się z dwóch części: pierwsza zawiera kompleksowe wprowadzenie do podstaw teorii matroidów, natomiast druga omawia bardziej zaawansowane tematy. Książka zawiera ponad siedemset ćwiczeń i po raz pierwszy w jednym miejscu zawiera dowody wszystkich najważniejszych twierdzeń z przedmiotu. Ostatnie dwa rozdziały stanowią przegląd aktualnych badań i zawierają listę ponad osiemdziesięciu nierozwiązanych problemów wraz z opisem postępu w kierunku ich rozwiązania.