Дискретно-непрерывная математика (стр. 11 )

(3) Покажите, что матроид М можно определить как пару (Е, C), где Е — непустое конечное множество, а С — совокупность его подмножеств (называемых циклами), удовлетворяющая следующим условиям: (i) никакой цикл не содержит в качест­ве собственного подмножества другой цикл; (ii) если C1 и С2— два различных цикла, каждый из которых содержит эле­мент е, то в C1 С2 существует цикл, не содержащий е.

(4) Докажите, что разрезы графа G удовлетворяют условиям пре­дыдущего упражнения; каково соотношение между ранговой функцией соответствующего матроида и ранговой функцией циклического матроида графа G.

(5) Если М = (E, ρ) — матроид, то замыканием φ(A) подмно­жества А из E называется совокупность всех элементов е множества E, обладающих тем свойством, что ρ (А {е})= ρ (A); докажите, что (i)

А φ (A) = φ (φ (A)); (ii) если A В E, то φ (А) φ (В); (iii) если е содержится в φ (A { f}) и не содержится в φ (А), то f содержится в φ (А {е}). Назовем множество А замкнутым, если φ (А) = А; покажите, что пересечение двух замкнутых множеств явля­ется замкнутым множеством. Верно ли аналогичное ут­верждение для объединения двух замкнутых множеств?

(6) Покажите, как расширить на матроиды определение фунда­ментальной системы циклов графа; а как расширить опреде­ление фундаментальной системы разрезов?

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

1.8.2. Примеры матроидов

В этом параграфе мы рассмотрим несколько важных ти­пов матроидов.

Тривиальные матроиды. На любом данном непустом конечном множестве Е можно определить матроид, единственным независимым множеством которого является пустое множество. Этот матроид называется тривиальным матроидом на Е; ясно, что его ранг равен нулю.

Дискретные матроиды. Другим крайним случаем является дискретный матроид на Е, в котором каждое под­множество из Е независимо; заметим, что дискретный мат­роид на Е имеет только одну базу, а именно само Е, и что ранг любого подмножества А равен числу элементов в А.

Однородные матроиды. Оба предыдущих примера явля­ются частными случаями k-однородного магроида на Е, базами которого являются все подмножества из Е, содер­жащие каждое ровно k элементов. Следовательно, незави­симыми множествами являются те подмножества из Е, которые содержат не более k элементов, а ранг любого под­множества А равен меньшему из чисел | А | и k. Заметим, что тривиальный матроид на Е является 0-однородным, а дискретный матроид | Е |-однородным.

Прежде чем развивать примеры, описанные в предыду­щих абзацах, удобно формализовать идею изоморфизма между матроидами. Два матроида М1 = (Е1, J1) и М2 = (Е2, J2) называются изоморфными, если существует вза­имно однозначное соответствие между множествами Е1 и Е2, сохраняющее независимость, или, другими словами, если множество элементов из Е1 независимо в М1 тогда и только тогда, когда соответствующее множество элементов из Е2 независимо в М2. В качестве примера отметим, что цикли­ческие матроиды трех графов, изображенных на рис. 1, изоморфны между собой; подчеркнем тот факт, что, хотя изоморфизм матроидов сохраняет циклы, разрезы и число ребер в графе, он, вообще говоря, не сохраняет связность, число вершин и их степени.

Рис. 1.

С помощью данного выше опре­деления изоморфизма можно теперь определить графические, трансверсальные и представимые матроиды.

Графические матроиды. Как мы видели в предыдущем параграфе, матроид M(G) можно определить на множестве ребер графа G, взяв в качестве циклов матроида циклы гра­фа G; при этом М(G) называется циклическим матроидом гра­фа G, и его ранговая функция равна коциклическому рангу κ. Закономерен следующий вопрос: является ли данный матроид М циклическим матроидом некоторого графа — другими словами, существует ли такой граф G, что матроид М изоморфен М(G)? Такие матроиды называ­ются графическими

матроидами, мы охарактеризуем их в следующем параграфе. В качестве примера графического матроида рассмотрим матроид М на множестве {1, 2, 3}, независимыми множествами которого являются Ø, {1}, {2}, {3}, {1, 2} и {1, 3}; ясно, что матроид М изоморфен цик­лическому матроиду графа, изображенного на рис. 2.

Рис. 2.

С другой стороны, можно показать, что существуют негра­фические матроиды; простейшим примером является 2-однородный матроид на множестве из четырех элементов (в чем читатель может легко убедиться).

КОГрафические матроиды. Циклический матроид M(G) данного графа G — это не единственный матроид, который можно определить на множестве ребер графа G. Аналогия между свойствами циклов и свойствами разрезов в графе позволяет надеяться, что можно построить матроид, взяв в качестве его циклов разрезы графа G. В упр. 4 разд. 1.8.1 требова­лось показать, что такое построение и в самом деле опреде­ляет матроид, который мы будем называть нециклическим матроидом (матроидом разрезов) графа G и обозначать черезM*(G); заметим, что при этом множество ребер графа G независимо тогда и только тогда, когда оно не содержит раз­резов графа G. Матроид М назовем кографическим, если су­ществует такой граф G, что матроид М изоморфен M*(G); позднее станет понятно, почему мы его так назвали.

Планарные матроиды. Матроид, являющийся одновременно графическим и кографическим, называется планарным.

Связь между пленарными матроидами и пленарными гра­фами будет выявлена в следующем параграфе.

Представимые матроиды. Поскольку определение матроида частично мотивировано понятием линейной незави­симости в векторных пространствах, интересно исследовать те матроиды, которые возникают как векторные матроиды, связанные с некоторым множеством векторов в векторном пространстве над данным полем. Более точно, данный мат­роид М на множестве Е будем называть представимым над полем F, если существуют векторное пространство V над F и отображение φ из Е в V, обладающее тем свойством, что подмножество А из Е независимо тогда и только тогда, когда φ взаимно однозначно на А и φ(А) линейно независимо в V. (Заметим, что если игнорировать петли и параллель­ные элементы, то сказанное выше означает, что М изомор­фен векторному матроиду, определенному в некотором век­торном пространстве над F.) Особенно интересны те матрои­ды, которые представимы над полем целых чисел по модулю два, — такие матроиды называются бинарными. Для удоб­ства мы будем называть М представимым матроидом, если существует такое поле F, что М представим над F. Оказы­вается, некоторые матроиды представимы над любым по­лем (это так называемые регулярные матроиды), некоторые не представимы ни над каким полем, а другие пред­ставимы лишь над некоторым ограниченным классом полей.

Нетрудно показать, что если G — граф, то его цикличес­кий матроид M(G) является бинарным. Чтобы убедиться в этом, сопоставим каждому ребру из G соответствующую ему строку в матрице инциденций графа G, рассматри­вая ее как вектор, каждая компонента которого равна нулю или единице. Заметим, что если какое-нибудь множество ребер из G образует цикл, то сумма (по модулю два) соответ­ствующих этим ребрам векторов равна нулю.

Пример бинарного матроида, не являющегося ни графи­ческим, ни кографическим, приводится в упр. 9.

Трансверсальные матроиды. Наш следующий пример устанавливает связь между теорией матроидов и теорией трансверсалей. Напомним читателю, что, как утверждается ранее, если Е — непустое конечное множест­во, а & = (S1 ..., Sm) — семейство непустых его подмно­жеств, то частичные трансверсали для & можно взять в ка­честве независимых множеств матроида на Е. Любой матроид, полученный таким образом (при подходящем выборе Е и &), называется трансверсальным матроидом и обозначается M(S1, ..., Sm). Например, описанный выше графический матроид М является трансверсальным матроидом на мно­жестве {1, 2, 3}, так как его независимые множества служат частичными трансверсалями для семейства & =(S1, S2), где S1 = {1}, a S2 = {2, 3}. Заметим, что ранг подмно­жества А φЕ равен мощности наибольшей частичной транс­версали, содержащейся в А. Пример матроида, не являюще­гося трансверсальным, приводится в упр. 4.