10.4. Двойственность матроидов и графоиды

В этом разделе мы сначала введем понятие двойственности матроидов и обсудим некоторые результаты, связывающие матроид с двойственным к нему матроидом. Затем мы сформулируем теорему о «раскрашивании», которая приведет нас к понятию графоида. Мы завершим раздел развитием самодвойственной системы аксиом Минти для матроидов, основанной на графоидах.

Начнем с теоремы, предложенной Уитни [10.1], в которой определяется двойственный матроид.

Теорема 10.10. Пусть — множество баз матроида М на множестве S. Тогда есть множество баз матроида М на

Доказательство. Очевидно, что удовлетворяет аксиоме Чтобы показать, что аксиома также выполняется, рассмотрим любые такие два произвольных члена набора что Пусть Тогда Из упражнения 10.4 следует, что существует такое что является базой М. Теперь Таким образом, аксиома выполняется и, следовательно, 33— множество баз матроида М на

Определенный в теореме матроид М называется двойственным матроидом к М. Легко видеть, что М — двойственный к М матроид. Поэтому будем говорить, что М и М—двойственные матроиды.

Определенные в разд. 10.1 матроид разрезов и циклический матроид графа, как нетрудно заметить, являются двойственными матроидами.

База М называется кобазой М. Аналогично цикл М—коцикл М, петля М — копетля М, функция ранга М — функция коранга М и т. д. Функция ранга М обозначается через . Если В — база М, то кобаза обозначается через В. Набор кобаз М обозначается через , а набор коциклов — через

Теперь сформулируем результаты, связывающие матроид с двойственным к нему матроидом. Многие из них хорошо известны в теории графов (гл. 2).

Очевидно, что из определения двойственного матроида следует

В следующей теореме раскрывается взаимосвязь .

Теорема 10.11. Если М и М* — двойственные матроиды на множестве S, тогда для любого справедлива формула

Доказательство. Рассмотрим пусть В — такая база М, что — максимально. Тогда В — такая база М, что - максимально. Из определения функции ранга следует, что

Тогда Таким образом, из выражений (10.6) и (10.7) следует

Заметим, что для любого утверждения о циклах, базах и т. д. матроида существует двойственное утверждение о коциклах, кобазах и т. д. матроида. Это обусловлено тем, что коциклы, кобазы и т. д. сами являются циклами, базами и т. д. матроида.

Все леммы и теоремы этого раздела мы дополняем, где это возможно, двойственными утверждениями. Доказательства этих двойственных утверждений очевидны.

Лемма 10.1. Пусть М — матроид на множестве S. Если — независимое множество М, то содержит кобазу М. Двойственное утверждение: если — независимое множество М, то содержит базу М.

Доказательство. Существует такая база В матроида М, что Поэтому содержит соответствующую кобазу В.

Теорема 10.12. Пусть М — матроид на множестве S. Если А и А — такие подмножества S, что — независимое множество М, а А — независимое множество М, то существует такая база В матроида М, что

Доказательство. По предыдущей лемме содержит базу матроида М. Поскольку независимое множество М, то по теореме 10.2 существует такая база В матроида М, что а, следовательно, АВ.

Лемма 10.2. Пусть М — матроид на множестве S. Тогда любая база В матроида М имеет непустое пересечение с любым коциклом М.

Аналогично любая кобаза М имеет непустое пересечение с любым коциклом М.

Доказательство. Если бы для некоторого коцикла С матроида , то содержало бы S, что противоречит независимости В в М.

Пусть В — произвольная кобаза матроида на множестве S. По двойственному утверждению к следствию 10.4.2 для любого содержит в точности один коцикл. Он называется базисным коциклом элемента по отношению к В. Заметим, что этот коцикл содержит точно один элемент из В, а именно

Лемма 10.3. Пусть М — матроид. Для любого независимого множества А матронда М существует коцикл, имеющий точно один элемент из А. Кроме того, если , то существует коцикл, имеющий пустое пересечение с А.

Аналогично для любого независимого множества А матроида М существует цикл, имеющий точно один элемент из А. Если , то существует цикл, имеющий с А пустое пересечение.

Доказательство. Пусть В — такая база М, что АВ, а С — базисный коцикл элемента по отношению к В. Тогда если если . Таким образом, лемма доказана.

Теорема 10.13. Пусть М — матроид на множестве S. Подмножество является базой М тогда и только тогда, когда X — минимальное подмножество, имеющее непустое пересечение со всеми коциклами М.

Аналогично подмножество — кобаза М тогда и только тогда, когда оно является минимальным подмножеством, имеющим непустое пересечение со всеми циклами М.

Доказательство. Необходимость следует из лемм 10.2 и 10.3.

Для доказательства достаточности положим, что X — минимальное подмножество S, имеющее непустое пересечение со всяким коциклом М. Тогда — максимальное подмножество, не содержащее коциклов М. Поэтому является по определению кобазой М, а следовательно, X — базой М.

Получим сейчас несколько новых характеризаций циклов и коциклов.

Теорема 10.14. Пусть М — матроид на множестве 5. Подмножество XS есть цикл М тогда и только тогда, когда оно является минимальным подмножеством, имеющим непустое пересечение со всякой базой М.

Аналогично подмножество XS есть коцикл М тогда и только тогда, когда оно является минимальным подмножеством, имеющим непустое пересечение со всякой базой М.

Доказательство аналогично доказательству теоремы 2.13.

Пусть С — коцикл матроида М на 5. По предыдущей теореме С — минимальное подмножество, имеющее непустое пересечение со всякой базой М. Поэтому — максимальное подмножество, не содержащее баз М. Таким образом, получаем следующее утверждение.

Лемма 10.4. Если С — коцикл матроида М на множестве , то содержит базу В матроида М для любого

Аналогично если С — цикл матроида М на множестве S, то содержит кобазу М для любого

Теорема 10.15. Пусть М — матроид на множестве S. Подмножество есть цикл М тогда и только тогда, когда оно является минимальным подмножеством с для всякого коцикла С матроида М.

Аналогично подмножество есть коцикл М тогда и только тогда, когда оно является минимальным подмножеством с для всякого цикла С матроида М.

Доказательство. Необходимость. Допустим противное. Тогда для любого собственного подмножества С цикла С по лемме 10.3 существует такой коцикл С, что

Допустим, что для некоторого цикла С и некоторого коцикла С, пусть . Рассмотрим теперь Очевидно, что . По лемме 10.4 содержит базу. Пусть — такая база, что Заметим, что Поэтому цикл содержится в В; получили противоречие.

Достаточность. Если X — такое подмножество S, что для всякого коцикла С, то X должно содержать цикл, иначе бы X было независимым множеством М и по лемме 10.3 существовал коцикл, имеющий в точности один элемент их X.

Пусть С — содержащийся в X цикл. Из доказанного необходимого условия теоремы очевидно, что для всякого коцикла С. Поэтому иначе минимальность X приводит к противоречию.

Теперь введем понятие раскрашивания конечного множества и сформулируем теорему о «раскрашивании».

Раскрашивание множества S — это разбиение S на три таких подмножества R, G и В, что Для облегчения представления мы считаем, что элементы R «окрашены» в красный цвет, элемент G — в зеленый, а элементы В — в голубой.

Теорема 10.16. (теорема о раскрашивании). Пусть М — матроид на множестве S. Для любого раскрашивания 5 существует

1) цикл С матроида М, содержащий зеленый элемент и не имеющий голубых элементов, либо

2) коцикл С матроида М, содержащий зеленый элемент и не имеющий красных элементов.

Доказательство. Допустим, что зеленый элемент входит в некоторый цикл, иначе он был бы копетлей и утверждение теоремы становится тривиальным.

Предположим, что для некоторого раскрашивания S утверждение 1 не истинно. Рассмотрим тогда подмножество Очевидно, что любой содержащийся в S цикл состоит только из красных элементов. Пусть R — минимальное подмножество красных элементов, для которого не содержит циклов, база, для которой . Тогда легко видеть, что базисный цикл любого элемента по отношению к В состоит только из красных элементов.

Пусть теперь С — базисный коцикл зеленого элемента по отношению к В. Допустим, что С содержит красный элемент Тогда где базисный цикл по отношению к В. Это противоречит теореме 10.15, следовательно, С — коцикл, содержащий зеленый элемент и не имеющий красных элементов. Таким образом, утверждение 2 истинно.

Теоремы 10.15 и 10.16 приводят нас к определению графоида, введенному Минти [10.2].

Графоид — это структура состоящая из конечного множества S и двух наборов непустых подмножеств S, удовлетворяющих следующим условиям:

Для любого раскрашивания существует а) член содержащий зеленый элемент и не имеющий голубых элементов, либо б) член «2», содержащий зеленый элемент и не имеющий красных элементов.

G.3. Никакой член не содержит другого члена в качестве собственного подмножества; никакой член не содержит другого члена в качестве собственного подмножества.

Теорема 10.17. Пусть М — матроид на множестве 5. Тогда — графоид.

Доказательство следует из теорем 10.15 и 10.16.

Установим сейчас обратную теорему.

Теорема 10.18. Пусть — графоид. Тогда — максимальное подмножество, не содержащее члена тогда и только тогда, когда В не содержит членов — членов

Доказательство.

Необходимость. Пусть В — максимальное подмножество S, не содержащее членов Допустим, что содержит . Пусть Тогда содержит Поэтому что противоречит аксиоме Таким образом, не содержит членов

Достаточность, Пусть не содержит членов а — членов . Покажем, что для любого содержит

Рассмотрим раскрашивание , в котором все элементы В — красные, — зеленый, а все оставшиеся элементы голубые. Очевидно, что не существует члена содержащего только зеленый и голубые элементы. Таким образом, по аксиоме содержит

Теорема 10.19. Пусть — графоид. Если В — максимальное подмножество , не содержащее элементов то максимальное подмножество , не содержащее элементов

Доказательство следует из теоремы 10.18 и двойственной к ней.

Теорема 10.20. Пусть — графоид. Тогда — набор циклов матроида М на , а — набор его коциклов.

Доказательство. Покажем сначала, что — набор циклов матроида на

Очевидно, что аксиома удовлетворяется.

Пусть произвольные различные члены g, для которых Рассмотрим раскрашивание S, в котором у — зеленый, — голубой, оставшиеся элементы -красные, а остальные элементы S — голубые (рис. 10.2).

Члена содержащего зеленый элемент и не имеющего красных элементов, не существует. Если бы такой член существовал, то, как легко показать, выполнялось бы условие или что противоречит аксиоме Поэтому по аксиоме существует содержащий зеленый элемент

и не имеющий голубых. По аксиоме не является членом Отсюда следует, что . Таким образом, аксиома удовлетворяется. Следовательно, — набор циклов матроида на

Аналогично можно показать, что есть набор циклов матроида на

Рис. 10.2.

По теореме 10.19 базы являются дополнениями баз Поэтому двойственные матроиды.

Из теорем 10.17 и 10.20 следует эквивалентность системы аксиом для графоида и системы аксиом для циклов. Этот вывод сделан Минти [10.2], давшим элегантное изложение теории матроидов на основе графоидов.