Twierdzenie Rado-Edmondsa () – twierdzenie teorii matroidów określające maksymalną liczność zbioru niezależnego wspólnego dla dwóch matroidów zdefiniowanych na tym samym zbiorze bazowym. Stanowi podstawowy rezultat teorii przecięcia matroidów oraz jedno z najważniejszych twierdzeń optymalizacji kombinatorycznej.
Twierdzenie zostało rozwinięte przez Richarda Rado i Jacka Edmondsa w latach 60. XX wieku.
Treść twierdzenia Niech oraz będą matroidami określonymi na tym samym zbiorze bazowym , a i oznaczają ich funkcje rangi.
Wówczas
gdzie jest zbiorem niezależnym jednocześnie w obu matroidach.
Interpretacja Twierdzenie ma charakter minimaksowy. Określa ono maksymalny rozmiar wspólnego zbioru niezależnego dwóch matroidów wyłącznie za pomocą ich funkcji rangi.
Stanowi ono analogię twierdzenia max-flow min-cut dla struktur matroidowych oraz jest podstawą teorii przecięcia matroidów.
Zastosowania Twierdzenie znajduje zastosowanie między innymi w: teorii grafów, optymalizacji kombinatorycznej, problemach dopasowań, teorii transwersali, projektowaniu algorytmów przecięcia matroidów.
Historia Pierwsze wyniki dotyczące wspólnych zbiorów niezależnych matroidów uzyskał Richard Rado. Następnie Jack Edmonds sformułował pełne twierdzenie minimaksowe dla przecięcia matroidów, które stało się jednym z podstawowych wyników współczesnej kombinatoryki.
Przypisy
Linki zewnętrzne
Kategoria:Twierdzenia kombinatoryki