Controleren of een ingestelde familie een matroïde vormt.

Given a set family, what is the best way (empirically) to check whether the set family is equivalent to set of independent sets of some matroid. The input can be either the set family explicitly or bunch of cardinality constraints that must be satisfied. For example, given a universe E, subsets $A_1,..,A_k$ of E and positive integers $b_1,...,b_k$, a set F is in the family iff $|F\cap A_i|<= b_i$ for each $1<= i<= k$. Check whether the family is a matroid.

4
toegevoegd de auteur Dane O'Connor, de bron

3 antwoord

Eén manier is om een ​​element $ x $ te verwijderen van je vermeende matroos $ M $, controleer recursief of de kleinere structuur $ M '$ een matroos is, en controleer dan of het toevoegen van $ x $ je een single-element extensie geeft van $ M '$. Een algoritme voor het testen van uitbreidingen met één element wordt uitgelegd in dit artikel van Mayhew en Royle , waarin ze berekenen alle matroïden met maximaal negen elementen.

4
toegevoegd
Bedankt Timothy. Dit ziet er zeker een veel betere manier uit dan een uitputtende zoektocht.
toegevoegd de auteur Yang, de bron

Je zou de definitie kunnen gebruiken. Voor uw voorbeeld, als $ A_i $ s disknooppunten zijn, is het antwoord ja. Het is een partitiematroid. Anders is het antwoord in het algemeen nee.

0
toegevoegd

Hier is een probabilistische benadering.

Controleer eerst of uw ingestelde familie $ \ mathcal {I} $ gesloten is onder het nemen van subsets. Zo niet, dan is het geen matroos. Wijs vervolgens een 'willekeurige' gewichtsfunctie $ w: S \ to \ mathbb {R} _ {+} $ toe aan de grondwaarde $ S $. Voer nu het hebzuchtige algoritme uit. Als $ \ mathcal {I} $ inderdaad een matroïde is, zal het hebzuchtige algoritme een lid $ I $ van $ \ mathcal {I} $ van maximaal gewicht uitvoeren. We kunnen echter rechtstreeks het gewicht berekenen van elk maximaal (onder insluiting) lid van $ \ mathcal {I} $. Dus, als $ I $ geen maximumgewicht heeft, dan is $ \ mathcal {I} $ geen matroos. Als $ I $ het maximale gewicht heeft, betekent dit niet dat $ \ mathcal {I} $ een matroos is, we hebben misschien net geluk gehad. Dus kiezen we een andere willekeurige gewichtsfunctie en herhalen. Ik heb niet geanalyseerd hoe vaak we dit moeten doen om redelijk 'zeker' te zijn dat $ \ mathcal {I} $ een matroos is.

0
toegevoegd
Bedankt voor de aanpak. Ik heb erover nagedacht, maar aangezien de families in kwestie erg dicht bij matroids zijn en uitwisseling-axioma's op enkele plaatsen worden geschonden, weet ik niet zeker of het controleren van enkele gevallen zal werken. Maar het zal zeker werken als een vuile vuile check.
toegevoegd de auteur Yang, de bron