Двойной матроид
-
Определение и свойства двойственности матроидов
- Двойственность матроида — это матроид, который имеет те же элементы и в котором множество является независимым, если и только если его пересечение с базисным набором исходного матроида пусто.
- Двойственность является инволюцией, и базисные множества двойного матроида являются дополнениями базисных множеств исходного матроида.
- Аксиома базисного обмена гарантирует, что дуал матроида также является матроидом.
- Квартиры в исходном матроиде являются дополнительными к циклическим наборам в двойственном матроиде, и наоборот.
- Ранговая функция двойного матроида определяется как сумма ранга множества и его размера минус ранг исходного множества.
-
Операции с матроидами
- Минор дуала матроида является его дуалом, что означает, что операции ограничения и сокращения в исходном матроиде соответствуют двойственным операциям в двойственном матроиде.
- Самодвойственные матроиды изоморфны своим собственным двойственным, но проверка самодвойственности требует экспоненциального числа запросов к независимому оракулу.
-
Семейства матроидов и их двойственность
- Многие важные семейства матроидов, включая бинарные, гаммоиды и однородные матроиды, являются самодвойственными.
- Графические матроиды плоских графов и двудольные матроиды являются двойственными эйлеровым матроидам.
- Вопрос о самодвойственности алгебраических матроидов остается открытым.
-
Рекомендации
- В статье приведены ссылки на цитируемые работы для более детального изучения темы.
Полный текст статьи: