Упражнения

10.1. Пусть М — матроид на S, а Определим как набор таких подмножеств что X — независимое множество в М и Докажите, что

— набор независимых множеств матроида на 5.

10.2. Пусть множество 5 имеет элементов. Покажите, что набор всех подмножеств S, имеющих k или менее элементов, есть множество независимых множеств матроида. Этот матроид называется однородным матроидом ранга k и обозначается через

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

10.4. Докажите, что если базы матроида М и то существует такое что являются базами М [10.44]; см. также [10.12], глава V.

10.5. Пусть D — набор таких непустых подмножеств 5, что для двух любых членов X и К набора существует такое

Докажите тогда, что набор ??) минимальных членов образует множество циклов матроида [10.3],

10.6. Докажите, что если С — цикл матроида , а то существует такая база В, что .

10.7. Докажите, что если В — база матроида М и то имеется точно один такой коцикл С матроида М, что

10.8. Докажите, что если С — цикл матроида М и у — его различные элементы, то существует коцикл С, содержащий у и никакого другого элемента цикла С [10.2].

10.9. Пусть М — матроид на S, а — различные элементы S. Докажите, что если существуют циклы С, содержащий х содержащий у и , то существует и цикл содержащий .

10.10. Множество называется замкнутым в матроиде М на S, если для всех Покажите, что пересечение двух замкнутых множеств есть замкнутое множество.

10.11. Пусть М — матроид на множестве S. Замыканием о (Л) подмножества называется множество всех таких элементов что . Докажите, что а) если входит в но не входит в а то у входит в a элемент принадлежит а (А) тогда и только тогда, когда или существует цикл С матроида М, для которого

10.12. Гиперплоскостью матроида М на S называется максимальное собственное замкнутое подмножество S. Покажите, что Я является гиперплоскостью тогда и только тогда, когда — коцикл матроида М (систему аксиом для матроида, исходя из гиперплоскостей, можно найти в работе [10.4]).

10.13. Покажите, что если М — матроид на S и то сужение матроида М на Т — матроид, коциклы которого являются в точности коциклами матроида М, содержащимися в А.

10.14. Докажите, что если М — матроид на S и то а)

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

Примечание. Если G — граф, то М (G) связный тогда и только тогда, когда граф О является -связным.

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

10.17. Доказать или опровергнуть: граф G стягивается к Н тогда и только тогда, когда М (G) содержит М (Н) в качестве минора сужения.

10.18. Докажите, что однородный матроид представим над всяким полем, за исключением GF (2).

10.19. Докажите, что матроид бинарный тогда и только тогда, когда для любых цикла С и коцикла С справедливо

10.20. Пусть — семейство непустых подмножеств множества S. Трансверсаль подсемейства называется частичной трансверсалью Покажите, что если — набор непустых подмножеств множества S, то набор частичных трансверсалей образует множество независимых множеств матроида на S. (Определение транс-версали дано в разд. 8.6.) Найдите функцию ранга этого матроида. Матроид М на S называется трансверсальным, если существует такое семейство подмножеств S, что есть семейство частичных трансверсалей Найдите функцию ранга трансверсального матроида (см. теорему 8.15).

10.21. Покажите, что любой однородный матроид ранга k является трансверсальным.

10.22. Матроид Фано F — это матроид, определенный на множестве базами которого являются все подмножества S, содержащие по три

элемента, за исключением Покажите, что матроид F является а) бинарным, б) трансверсальным, в) неграфическим, г) некографическим.

10.23. Покажите, что циклический матроид не является трансверсальным.

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

10.25. Пусть D — ориентированный граф без петель, а X и Y — непересекающиеся множества вершин D. Подмножество называется независимым, если существует вершинно непересекающихся цепей от F к Y. Покажите, что эти независимые множества образуют независимые множества матроида на X (такой матроид называется гаммоидом) [10.45].

10.26. Матроид М на S называется правильным, если для любых баз матроида М существует такое взаимно однозначное соответствие между и что для любого являются базами матроида М, где — элемент соответствующий Покажите, что а) — неправильный матроид; б) если М — правильный матроид на S и то матроид правильный; в) если М — правильный матроид, то любой его минор правильный.

10.27. Пусть матроиды на множестве

а) Покажите, что множество всех объединений независимых множеств I матроида и независимых множеств J матроида образует набор независимых множеств нового матроида. (Этот матроид называется объединением и обозначается )

б) Покажите, что если функции ранга матроидов на множестве S, то где — функция ранга ММ,

10.28. Пусть М — матроид на S. Докажите, что а) М содержит k непересекающихся баз тогда и только тогда, когда для любого б) S можно выразить в виде объединения не более чем k независимых множеств тогда и только тогда, когда для любого

Примечание. Рассмотрите объединение k копий матроида М и используйте результат упражнения 10.27 [10.14].

10.29. Покажите, что если «жадным» алгоритмом выбраны k элементов, то они имеют максимальный вес среди всех независимых множеств, состоящих из k или менее элементов.

10.30. Необходимо выполнить на ЭВМ множество заданий. Все задания требуют для выполнения одинакового времени. Каждому заданию присваивается крайний срок выполнения.

а) Покажите, что набор всех подмножеств заданий, которые можно выполнить по расписанию, образует множество всех независимых множеств матроида.

б) Допустим, за каждое не выполненное в срок задание необходимо заплатить штраф. В каком порядке следует выполнять задания, чтобы общий штраф был минимальным?

10.31. Пусть М — матроид, элементам которого присвоены неотрицательные веса. Докажите, что

а) никакой элемент базы максимального веса не имеет наименьшего веса в любом цикле М;

б) каждый элемент базы максимального веса имеет наибольший вес по крайней мере в одном коцикле матроида М.

Используя п. 6., предложите процедуру построения базы матроида максимального веса. (В работе [10.46] описывается такая процедура для построения остова минимального веса в связном графе.)

10.32. Пусть М — матроид на S, элементам которого присвоены неотрицательные веса. Пусть 33 — набор баз матроида М, а — набор коциклов этого же матроида М. Докажите, что