В математике , особенно в комбинаторике , учитывая семейство множеств , здесь называемое набором C , трансверсаль (также называемая сечением [1] [2] [3] ) - это набор, содержащий ровно один элемент из каждого члена коллекция. Когда наборы коллекции взаимно не пересекаются, каждый элемент трансверсали соответствует ровно одному члену C (набору, членом которого он является). Если исходные множества не пересекаются, есть две возможности для определения трансверсали:
- Одна из вариаций состоит в том, что существует биекция f из трансверсали в C, такая что x является элементом f ( x ) для каждого x в трансверсали. В этом случае трансверсаль также называют системой различных представителей (SDR). [4] : 29
- Другие, менее широко используются, не требуют отношений один-к-одному между элементами поперечного и наборами C . В этой ситуации члены системы представителей не обязательно различны. [5] : 692 [6] : 322
В информатике вычисление трансверсалей полезно в нескольких прикладных областях, при этом входное семейство наборов часто описывается как гиперграф .
Существование и количество
Фундаментальный вопрос при изучении SDR заключается в том, существует ли SDR. Теорема Холла о браке дает необходимые и достаточные условия для того, чтобы конечный набор множеств, некоторые из которых, возможно, перекрывались, имел трансверсаль. Условие состоит в том, что для каждого целого числа k каждый набор из k множеств должен содержать не менее k различных элементов. [4] : 29
Следующее уточнение Х. Дж. Райзера дает нижние оценки количества таких SDR. [7] : 48
Теорема . Пусть S 1 , S 2 , ..., S m набор множеств такой, чтосодержит не менее k элементов для k = 1,2, ..., m и для всех k -комбинаций {} целых чисел 1,2, ..., m и предположим, что каждое из этих множеств содержит не менее t элементов. Если t ≤ m, то в наборе не менее t ! SDR, и если t > m, то в коллекции не менее t ! / ( т - м )! СДР.
Отношение к соответствию и покрытию
Можно построить двудольный граф, в котором вершины на одной стороне - это множества, вершины на другой стороне - это элементы, а ребра соединяют набор с элементами, которые он содержит. Тогда трансверсаль (определенная как система различных представителей) эквивалентна совершенному паросочетанию в этом графе.
Можно построить гиперграф, в котором вершины - элементы, а гиперребра - множества. Тогда трансверсаль (определенная как система необязательно различных представителей) является вершинным покрытием гиперграфа .
Примеры
В теории групп , дан подгруппа H из группы G , правый (соответственно слева) трансверсально представляет собой набор , содержащий ровно один элемент из каждых справа (соответственно слева) смежного класса из Н . В этом случае «множества» (смежные классы) попарно не пересекаются, т. Е. Смежные классы образуют разбиение группы.
Как частный случай предыдущего примера, учитывая прямое произведение групп , То Н является трансверсально для смежных классов K .
В общем, поскольку любое отношение эквивалентности на произвольном множестве порождает разбиение, выбор любого представителя из каждого класса эквивалентности приводит к трансверсали.
Другой пример трансверсали на основе разбиения возникает, когда рассматривается отношение эквивалентности, известное как (теоретико-множественное) ядро функции , определенное для функциис областью X в качестве раздела области. который разбивает область определения f на классы эквивалентности, так что все элементы в классе отображаются через f в одно и то же значение. Если f инъективен, существует только одна трансверсаль к. Для необязательно инъективной f фиксация трансверсали T киндуцирует взаимно-однозначное соответствие между Т и изображением из F , далее обозначается. Следовательно, функциякорректно определяется тем свойством, что для всех z вгде x - единственный элемент в T такой, что; кроме того, g может быть расширен (не обязательно уникальным образом) так, чтобы он был определен во всей области области f путем выбора произвольных значений для g (z), когда z находится вне образа f . Это простое вычисление, чтобы проверить, что определенная таким образом g обладает свойством:, что является доказательством (когда область определения и область значений f - одно и то же множество), что полугруппа полного преобразования является регулярной полугруппой .действует как (не обязательно единственный) квазиобратный для f ; в теории полугрупп это просто называется обратным. Заметим, однако, что для произвольного g с указанным выше свойством «двойственное» уравнениеможет не держаться. Однако если обозначить через, то f является квазиобратным к h , т. е..
Общие трансверсали
Общая трансверсаль из коллекций А и В (где) Представляет собой набор , который является трансверсалью как A и B . Коллекции A и B имеют общую трансверсаль тогда и только тогда, когда для всех,
Обобщения
Частичная трансверсально представляет собой набор , содержащий не более одного элемента из каждого члена коллекции, или (в более строгой форме концепции) в комплекте с инъекцией из множества в C . Трансверсали конечного набора C конечных множеств образуют основу наборы в матроиде , то трансверсальна матроиды из C . Независимые наборы поперечной матроиды являются частичными трансверсалями С . [9]
Независимая трансверсально (также называемый радужный-независимый набор или независимая система представителей ) является трансверсально который также является независимым множеством данного графа. Чтобы объяснить разницу в переносных терминах, рассмотрим факультет с m отделениями, где декан факультета хочет создать комитет из m членов, по одному члену на факультет. Такой комитет является трансверсальным. Но теперь предположим, что некоторые преподаватели не любят друг друга и не соглашаются вместе заседать в комитете. В этом случае комитет должен быть независимым трансверсалом, где лежащий в основе граф описывает отношения «неприязни».
Другое обобщение понятия секущей будет набор , который просто имеет непустое пересечение с каждым членом C . Пример последнего был бы множество Бернштейна , который определяется как набор , который имеет непустое пересечение с каждым набором C , но не содержит набора C , где C является совокупностью всех совершенных множеств топологического польски пространство . В качестве другого примера, пусть C состоит из всех линий проективной плоскости , тогда блокирующий набор в этой плоскости - это набор точек, которые пересекают каждую прямую, но не содержат прямой.
Теория категорий
На языке теории категорий , трансверсально из совокупности непересекающихся множеств является раздел о факторизации индуцированной коллекции.
Вычислительная сложность
Вычислительная сложность вычисления всех трансверсалей входного семейства множеств был изучен, в частности , в рамках алгоритмов перечисления .
Смотрите также
- Аксиома выбора
- Постоянный
Рекомендации
- ^ Джон Макинтош Хауи (1995). Основы теории полугрупп . Кларендон Пресс. п. 63. ISBN 978-0-19-851194-6.
- ^ Клайв Рейс (2011). Абстрактная алгебра: введение в группы, кольца и поля . World Scientific. п. 57. ISBN 978-981-4335-64-5.
- ^ Бруно Курсель ; Йост Энгельфриет (2012). Структура графа и монадическая логика второго порядка: теоретико-языковой подход . Издательство Кембриджского университета. п. 95. ISBN 978-1-139-64400-6.
- ^ а б Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту 0859549
- ^ Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN 978-1-4200-9982-9
- ^ Brualdi, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-602040-2
- ^ Райзер, Герберт Джон (1963), комбинаторная математика , The Carus Mathematical Monographs # 14, Математическая ассоциация Америки
- ^ EC Milner (1974), ПОПЕРЕЧНАЯ ТЕОРИЯ, Труды международного конгресса математиков , стр. 161
- ^ Оксли, Джеймс Г. (2006), Теория матроидов , Оксфордские выпускные тексты по математике, 3 , Oxford University Press, стр. 48, ISBN 978-0-19-920250-8.
дальнейшее чтение
- Лоулер, Э.Л. Комбинаторная оптимизация: сети и матроиды. 1976 г.
- Мирский, Леон (1971). Трансверсальная теория: изложение некоторых аспектов комбинаторной математики. Академическая пресса. ISBN 0-12-498550-5 .