Oddělovací matroid - Partition matroid
V matematice, a dělící matroid nebo částečný matroid je matroid vytvořený z a přímý součet z jednotné matroidy.[1] Je definován přes základní sadu, ve které jsou prvky rozděleny do různých kategorií. Pro každou kategorii existuje a kapacitní omezení - maximální počet povolených prvků z této kategorie. Nezávislé sady dělícího matroidu jsou přesně sady, ve kterých je pro každou kategorii počet prvků z této kategorie maximálně kapacitou kategorie.
Formální definice
Nechat být sbírkou disjunktní sady ("Kategorie"). Nechat být celá čísla s („kapacity“). Definujte podmnožinu být „nezávislý“, když pro každý index , . Sady splňující tuto podmínku tvoří nezávislé sady a matroid, nazvaný a dělící matroid.
Sady se nazývají bloky nebo Kategorie dělícího matroidu.
A základ maticového oddílu je sada, jejíž průsečík s každým blokem má přesně velikost . A obvod matroidu je podmnožina jednoho bloku s velikostí přesně . The hodnost matroidu je .[2]
Každý jednotný matroid je oddílový matroid s jediným blokem z prvky a s . Každý dělící matroid je přímým součtem sbírky uniformních matroidů, jednoho pro každý z jeho bloků.
V některých publikacích je pojem dělícího matroidu definován přísněji, u všech . Oddíly, které se řídí touto přísnější definicí, jsou příčné matroidy rodiny disjunktních množin daných jejich bloky.[3]
Vlastnosti
Stejně jako u uniformních matroidů, z nichž jsou vytvořeny, duální matroid of partroid matroid is also a partition matroid, and every Méně důležitý of partroid matroid is also a partition matroid. Přímé součty dělících matroidů jsou také dělícími matroidy.
Vhodný
A maximální shoda v grafu je sada hran, která je co největší, za podmínky, že žádné dvě hrany nesdílejí koncový bod. V bipartitní graf s biparticí , sady hran splňující podmínku, že žádné dvě hrany nesdílejí koncový bod jsou nezávislé sady dělícího matroidu s jedním blokem na vrchol v a s každým z čísel rovna jedné. Sady hran splňující podmínku, že žádné dvě hrany nesdílejí koncový bod jsou nezávislé sady druhého oddílu matroid. Problém s bipartitním maximálním párováním lze tedy reprezentovat jako a průnik matroidů z těchto dvou matroidů.[4]
Obecněji lze shodu grafu představovat jako průsečík dvou matroidů právě tehdy, když každý lichý cyklus v grafu je trojúhelník obsahující dva nebo více vrcholů dva vrcholy.[5]
Clique komplexy
A klikový komplex je rodina množin vrcholů grafu které indukují úplné podgrafy . Komplex kliky tvoří matroid právě tehdy je kompletní multipartitní graf, a v tomto případě je výsledný matroid dělící matroid. Klikové komplexy jsou přesně nastavenými systémy, které lze vytvořit křižovatky rodin přepážkových matroidů, pro které každý .[6]
Výčet
Počet různých oddílů matroidů, které lze definovat v sadě označené prvky, pro , je
The exponenciální generující funkce této sekvence je .[7]
Reference
- ^ Recski, A. (1975), „O částečných matroidech s aplikacemi“, Nekonečné a konečné množiny (Colloq., Keszthely, 1973; věnováno P. Erdősovi k jeho 60. narozeninám), sv. IIIColloq. Matematika. Soc. János Bolyai, 10, Amsterdam: Severní Holandsko, s. 1169–1179, PAN 0389630.
- ^ Lawler, Eugene L. (1976), Kombinatorická optimalizace: Sítě a matroidy, Rinehart a Winston, New York: Holt, s. 272, PAN 0439106.
- ^ Např. Viz Kashiwabara, Okamoto a Uno (2007). Lawler (1976) používá širší definici, ale konstatuje, že omezení je užitečné v mnoha aplikacích.
- ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1982), Kombinatorická optimalizace: Algoritmy a složitost, Englewood Cliffs, N.J .: Prentice-Hall Inc., str. 289–290, ISBN 0-13-152462-3, PAN 0663728.
- ^ Fekete, Sándor P .; Firla, Robert T .; Spille, Bianca (2003), „Charakterizace shody jako průniku matroidů“, Matematické metody operačního výzkumu, 58 (2): 319–329, arXiv:matematika / 0212235, doi:10,1007 / s001860300301, PAN 2015015.
- ^ Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), „Matroidová reprezentace komplexů klik“, Diskrétní aplikovaná matematika, 155 (15): 1910–1929, doi:10.1016 / j.dam.2007.05.004, PAN 2351976. Stejné výsledky v doplňkové formě používající nezávislé sady namísto klik, viz Tyshkevich, R. I.; Urbanovich, O. P .; Zverovich, I. È. (1989), „Matroidální rozklad grafu“, Kombinatorika a teorie grafů (Varšava, 1987), Banach Center Publ., 25, Varšava: PWN, s. 195–205, PAN 1097648.
- ^ Recski, A. (1974), „Enumerating partitional matroids“, Studia Scientiarum Mathematicarum Hungarica, 9: 247–249 (1975), PAN 0379248.