Математика 27

<

092713 0950 271 Математика 27 3) G — ациклический граф и m = n — 1;

4) любые две несовпадающие вершины графа С соединяет единственная простая цепь;

5) G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин
соединить ребром, то полученный граф будет содержать
ровно один цикл.

► 1) => 2) Воспользуемся индукцией по n. При n == 1 утверждение тривиально. Пусть n > 1, с е € ЕС. В дереве G нет циклоп, следовательно, согласно лемме 4.8, граф

092713 0950 272 Математика 27


 

Рис. 13.1

 

G — e имеет ровно две компоненты Т1 и T2, каждая из которых есть дерево. Пусть дерево Ti является (ni, mi) – графом, i =1, 2. По индуктивному предположению верно равенство

mi = ni — 1. (1)

Далее имеем

m= m1 + m2 + 1 = (n1 — 1) + (n2 — 1) + 1 = (n1 + n2) — 1 = n – 1.

2) => 3) Граф G связен и m = n — 1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть е — ребро этого цикла. Тогда граф G — e связен (лемма 4.8) и имеет n – 2 ребра, что противоречит теореме 4.9. Следовательно, G — ациклический граф.

3) => 4) Пусть k — число компонент графа G. Пусть, далее, компонента Тi является (ni,mi)-графом. Так как Тi — дерево, то верно равенство (1). Теперь имеем

n — 1 == m = m1 + m2+ …+ mk = (n1 –1) + (n2 – 1) +… +(nk –1) = (n1 + … + +nk) – k = n – k

т.е. k=1. Итак, G — связный граф и потому любые несовпадающие вершины u и v соединены в нем простои цепью. Если бы в G были две несовпадающие простые (u, v)-цепи, то согласно утверждению 4.3 их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.

4) => 5) Пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепями. Следовательно, граф G ациклический. Пусть u и v — две его несмежные вершины. Присоединим к графу G ребро е=uv. В G есть простая (u, v)-цепь, которая в G + e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.

5) => 1) Нужно доказать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G + uv не имел бы циклов, что противоречит утверждению 5). Итак, G связен и потому является деревом. ◄

Следствие 13.2. В любом дереве порядка п ≥ 2 имеется не менее двух концевых вершин.

► Пусть

d1, d2, …, dn (2)

— степенная последовательность дерева. Тогда

092713 0950 273 Математика 27

(лемма о рукопожатиях) и все d1 > 0. Следовательно, хотя бы два числа из последовательности (2) равны 1. ◄

Пусть H — основный подграф произвольного графа G.Если на каждой области связности графа G графом Н порождается дерево, то H называется остовом (или каркасом) графа G. Очевидно, что в каждом графе существует остов: разрушая в каждой компоненте циклы, т. е. удаляя лишние ребра, придем к остову. Остов в графе легко найти с помощью поиска в ширину.

Следствие 13.3. Число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно т(G)–/G/+k(G), где т(G) и k(G) — число ребер и число компонент графа G соответственно.

►Если (n1, m1)-граф H является одной из компонент графа G, то для превращения со в остовное дерево нужно удалить m1–(n1–1) подходящих ребер. Суммируя по всем k(G) компонентам, получим требуемое. ◄

Число v(G)= m(G) – |G| + k(G) называется циклическим рангом (или цикломатическим числом} графа G. Число v*(G)== |G| — k(G) ребер любого остова графа G называется нециклическим рангом графа С. Таким образом, v(G)+v*(G) = m(G).

Очевидны три следствия 13.4—13.6.

Следствие 13.4. Граф G является лесом тогда и только тогда, когда v(G) = 0.

Следствие 13.5. Граф G имеет единственный цикл тогда и только тогда, когда v(G) = 1.

Следствие 13.6. Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

В гл. III окажутся полезными утверждения 13.7, 13.8.

Утверждение 13.7. Всякий ациклический подграф произвольного графа G содержится в некотором остове графа G.

►Пусть Н — ациклический подграф в G. Очевидно, что достаточно рассмотреть ситуацию, в которой Н — остовный подграф и G связен. Если теперь Н не является остовом, то он несвязен. Пусть А — одна из областей связности графа Н. В графе G есть такое ребро аb, что а € А, b€VH\А. Граф Н + ab — ациклический остовный подграф графа G, имеющий меньше, чем Н, компонент. Повторяя аналогичное построение, доберемся до дерева, т. е.
до остова, содержащего граф Н.◄

Утверждение 13.8. Если S и Т — два остова графа G, то для любого ребра e1 графа S существует такое ребро е2 графа Т, что граф S – е1 + е2 также является остовом.

►Не ограничивая общности, будем считать граф G связным. Граф S — е1 имеет ровно две области связности; пусть это будут А и В. Поскольку граф Т связен, то в нем существует ребро е2, один из концов которого входит в A, а другой — в B. Граф H = S — е1+ е2 связен и число ребер в нем такое же, как и дерево S. Следовательно, он сам является деревом. Итак, Н — остов графа G. ◄

Очевидно, что дна предыдущих утверждения об остовах (13.7 и 13.8) сохраняются для произвольного псевдографа.

Докажем еще следующую теорему.

Теорема 13.9. Центр любого дерева состоит из одной или из двух смежных вершин.

► Очевидно, что концевые вершины дерена Т являются центральными только для Т = К1 или Т = К2.

Пусть Т — дерево порядка n > 2. Удалив из Т все концевые вершины, получим дерево Т’. Очевидно, что эксцентриситет Т’ на единицу меньше эксцентриситета дерева T и что центры деревьев Т и Т’ совпадают. Далее доказательство легко проводится индукцией по числу вершин. ◄

 

§ 14. Матричная теорема Кирхгофа

 

Как уже отмечалось, в каждом графе имеется остов.
В общем случае остов определен неоднозначно. Естественно возникает вопрос: как много остовов в графе? Очевидно, что при ответе на этот вопрос достаточно ограничиться случаем связного графа. В связном графе остовом служит любое остовное дерево, т. е. остовный подграф, являющийся деревом. Число остовов в связном графе определяется в неявной форме следующей теоремой.

Теорема Кирхгофа (1847 г.). Число остовных деревьев в связном графе G порядка n≥ 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа В (G).

Доказательство опирается на следующую лемму.

Лемма 14.1. Пусть H – (m+1, m)-граф, I — матрица инцидентности какой-либо его ориентации, М — произвольный минор порядка т матрицы I. Тогда:

1) если Н — дерево, то М = ± 1;

2) если Н не является деревом, то М = 0.

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

Пусть а — вершина, соответствующая строке матрицы I, не вошедшей в минор М. Если граф Н не является деревом, то он несвязен. Пусть К={1, 2, .., k}— его область связности, не содержащая вершины а. С помощью
подходящей перенумерации ребер графа H матрицу I приведем к клеточно-диагональному виду I = diag [I1, I2], где I1 — матрица инцидентности компоненты Н(К). Минор М содержит все первые k строк матрицы I, сумма
которых равна нулевой строке. Следовательно, М = 0.

Пусть теперь Н — дерево. Заново перенумеруем вершины и ребра графа Н следующим образом. Одной из концевых вершин v, отличных от вершины а, а также ребру, инцидентному вершине v, присвоим номер 1. Далее рассмотрим дерево Т1 = Н — v. Если его порядок больше 1, то одной из его концевых вершин u, отличных от а, а также инцидентному ей ребру присвоим номер 2. Рассмотрим дерево Т2 = Т1 — u. Итерируя этот процесс, получим новые нумерации вершин и ребер дерена H, причем вершина а будет иметь номер m+1. Матрица I при этом примет вид

092713 0950 274 Математика 27

(Здесь и в дальнейшем символом • будут обозначаться те элементы или блоки матрицы, значения которых не влияют на ход рассуждений.) Минор М, остающийся после удаления последней строки этой матрицы, равен ±1. ◄

Еще один факт, используемый при доказательстве теоремы Кирхгофа,— формула Бинэ—Копит, которую мы приведем без доказательства. Пусть А и В — n x m- и m x n-матрицы соответственно, С = АВ и n≤m. Минор порядка n матрицы В назовем соответствующим минору порядка n матрицы А, если множества номеров строк первого из них и номеров столбцов второго совпадают.

Формула Бинэ — Коши. Определитель матрицы С равен сумме произведений каждого минора порядка n матрицы A на соответствующий минор матрицы В.

►Доказательство теоремы Кирхгофа. Пусть I — матрица инцидентности какой-либо ориентации (n,m)-графа G. Согласно утверждению 6.4 верно равенство

B (G) = I IT(1)

Поскольку G — связный граф, то m ≥ n – 1. Если В — подматрица, остающаяся после удаления из В (G) последних строки и столбца, а С — подматрица, остающаяся после удаления из I последней строки, то в силу (1) В=ССT. Алгебраическое дополнение Аnn элемента, занимающего в матрице В (G) позицию (n,n), равно det В. Из формулы Бипэ — Коши теперь следует, что Аnn равно сумме квадратов всех миноров порядка n — 1 матрицы С. Согласно лемме 14.1 каждый такой минор М ранен ±1, если остовный подграф графа G, ребра которого соответствуют столбцам, вошедшим в М, является деревом, и нулю в противном случае. Следовательно, Аnn равно числу
остовных деревьев в графе G. Поскольку алгебраические
дополнения всех элементов матрицы В (G) равны (утверждение 6.2), то теорема доказана.◄

Следствие 14.2. Для числа компонент n-вершинного графа G верно равенство

k(G) = n – rank B(G)

►Если граф G связан, то в нем есть остовное дерево.
Согласно предыдущей теореме rank В(G)≥ n — 1. С другой стороны, всегда det В(G) = 0. Следовательно, rank B(G)= n – 1.

Пусть теперь граф G имеет равно k компонент. Тогда при подходящей нумерации вершин матрицей В (G) служит клеточно-диагональная матрица diag [B1, B2, …, Bk], диагональные клетки которой Bi (являются матрицами Кирхгофа соответствующих компонент. Учитывая уже доказанное, имеем rank В (G) = n — k. ◄

Следствие 14.3. При п > 1 число остовов в полном графе Кn равно nn-2.

►Рассмотрим алгебраическое дополнение А11 элемента матрицы

B(Kn) = 092713 0950 275 Математика 27

 

занимающего позицию (1, 1). Оно равно определителю

092713 0950 276 Математика 27

 

порядка n — 1. Далее имеем

 

 

A11 = 092713 0950 277 Математика 27= 092713 0950 278 Математика 27= n n-2

Очевидно, что число остовов в Kn равно числу помеченных деревьев порядка n. Поэтому предыдущее следствие можно сформулировать в виде следующей теоремы, впервые полученной А. Кэли в 1897 году.

Т е о р ем а К э л и. Число помеченных деревьев порядка n равно nn-2.

 

§ 15. Остов минимального веса

 

Рассмотрим следующую задачу: во взвешенном связном графе требуется найти остов минимального веса. Эта задача возникает при проектировании линий электропередачи, трубопроводов, дорог и т. п., когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (или, например, стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами полного графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа. Очевидно, что этот кратчайший остовный подграф должен быть деревом. Поскольку полный граф Kn содержит nn-2 различных остовных деревьев, то решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых п. Однако для ее решения имеются эффективные алгоритмы. Опишем дна из них — алгоритмы Дж. Краскала (1956 г.) и Р. Прима (1957 г.), применимые к произвольному связному графу.

Задача об остове минимального веса (о кратчайшем остове): в связном взвешенном графе (G, w) порядка n найти остов минимального веса.

Алгоритм Краскала, решающий эту задачу, заключается в следующем.

1. Строим граф Т1=On + e1, присоединяя к пустому графу на множестве вершин VG ребро е1 € ЕG минимального веса.

2. Если граф Тi, ужо построен и i<n–1, то строим граф Ti+1 = Ti + еi+1, где еi+1 — ребро графа G, имеющее минимальный вес среди ребер, не входящих в Тi и не составляющих циклов с ребрами из Тi .

Следующая теорема утверждает, что алгоритм Краскала всегда приводит к остову минимального веса.

Теорема 15.1. При i < n — 1 граф Тi+1 можно построить. Граф Тn-1 является остовом минимального веса в графе (G, w).

►Граф Тi имеет ровно i ребер и потому при i < n — 1 является несвязным. А так как граф G связен, то в нем есть по меньшей мере одно ребро, но составляющее циклов с ребрами графа Тi. Итак, нужное ребро еi+1 существует и граф Тi+1
можно построить.

Рассмотрим граф Tn-1. Поскольку Tn-1 является (n, n -1)-графом без циклов, то согласно теореме 13.1 это дерево. Остается доказать, что вес дерева Tn-1 минимален. Предположим, что это не так, и среди всех остовов
графа G минимального веса выберем такой остов Т, который имеет с деревом Tn-1 максимальное число общих ребер. Пусть еi=аb — ребро дерева Tn-1, не содержащееся в T и имеющее минимальный номер среди ребер
дерева Tn-1, не входящих в Т (напомним, что в процессе
построения дерева Tn-1 его ребра получили номера 1,2,..
…, n-1). В дереве Т есть простая (а, b)-цепь. Присоединив к ней ребро еi, получим цикл. В этом цикле есть ребро е, не входящее в дерево Tn-1. Заменив в дереве T ребро е на еi, получим новый остов T’ = Т — е + еi. Но Т—остов минимального веса, следовательно, w(T’)= w(T) + w(ei) – w(e)≥w(T), т. е.

w(ei) ≥ w(e) (1)

С другой стороны, присоединяя ребро е к Tn-1 (при i = 1 полагаем Ti-1 =On), мы не получим цикла, поскольку ребра е1, e2,…, ei-1,e входят в дерево Т, и потому, если бы вес w(еi) был больше, чем w(е), мы взяли бы при
построении дерева Ti ребро е вместо еi. Из (1) теперь
следует, что w(еi)== w(е), w(T’)= w(T).

Итак, Т’ — остов минимального веса. Число ребер, общих для деревьев Т’ и Tn-1, больше, чем число ребер, общих для Т и Tn-1, что противоречит выбору дерева T. Полученное противоречие и доказывает теорему. ◄

В качестве иллюстрации рассмотрим взвешенный граф, изображенный на рис. 15.1, а. Полагаем е1 =={1,4}, е2 = {4, 5}. Среди оставшихся ребер минимальный вес имеет, например, ребро {1, 5}. Однако оно не пригодно для
построения, поскольку составляет цикл с двумя предыдущими ребрами. Можно

 

092713 0950 279 Математика 27092713 0950 2710 Математика 27

 

 

 

 

 

Рис. 15.1

взять е3 = {2, 3}, e4= {2, 5}. Итак, ребра {1, 4}, {4, 5}, {2, 3), {2, 5) составляют остов минимального веса (рис. 15.1,6)),

Алгоритм Прима отличается от алгоритма Краскала
только тем, что на каждом этапе строится не просто ациклический граф, но дерево. Именно:

1. Выбираем ребро е1 = аb минимального веса и строим дерево T1, полагая VТ1 = {а, b}, Т1 == {е1}.

2. Если дерево Ti порядка i+1 ужо построено и i <n – 1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Ti, выбираем ребро еi+1 минимального веса. Строим дерево Ti+1, присоединяя к Ti ребро еi+1 вместе с его не входящим в Ti концом.

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

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

С задачей об остове минимального веса тесно связана задача Штейнера. Первоначально она формулировалась как следующая

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

Множеству точек U можно поставить в соответствие
полный граф K (U), вершинами которого будут элементы и, а вес каждого ребра будет равен расстоянию между соответствующими точками.

Евклидова задача Штейнера отличается от задачи построения остова минимального веса в графе K(U) тем, что в этот граф разрешается вносить новые вершины — точки Штейнера. Их можно добавлять столько, сколько
потребуется, чтобы дерево, их соединяющее, имело минимальный вес.

Если в предыдущей задаче в качестве расстояния между точками (х1, у1) и (х1, у1) взять величину |x1 — x2| ++ |y1-y2|, то получится прямоугольная задача Штейнера. Эта задача сводится к следующей широко известной
задаче.

Задача Штейнера на графах. В связном взвешенном графе G с выделенным подмножеством вершин и U 092713 0950 2711 Математика 27VG требуется найти связный подграф Т, удовлетворяющий следующим двум условиям:

1) множество VТ содержит заданное подмножество U;

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

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

Очевидно также, что задача построения дерева Штейнера эквивалентна задаче нахождения остова минимального веса в порожденных подграфах графа G, множества вершин которых содержат U.

Какие-либо эффективные алгоритмы, решающие задачу Штейнера, неизвестны.

 

УПРАЖНЕНИЯ

 

1. Нарисуйте все попарно неизоморфные деревья седьмого
порядка.

2. Найдите дерево минимального порядка n≥2 с тождественной группой автоморфизмов.

3. Докажите, что центр дерева состоит из одной вершины в
случае, когда диаметр этого дерева является четным числом, и из
двух смежных вершин, когда диаметр — число нечетное.

4. Докажите, что радиус r(G) и диаметр d(G) любого дерева
G связаны соотношением

r(G) =]d(G)/2[.

5. Верно ли, что если диаметр связного графа G равен k
(k > 2), то в G существует остовное дерево, диаметр которого также равен k?

6. (n,m)-граф называется сбалансированным, если никакой его подграф но имеет вершин степени большой, чем 2m/n. Покажите, что всякое дерево при n > 2 — несбалансированный граф.

7. Найдите остовные деревья в К5, К33 и в графе Петерсена.

8. Докажите, что подграф H графа G является в G остовом
тогда и только тогда, когда верны равенства |Н| == |G|, m(H) =
= |G| – k(G), k(H) = k(G).

9. Используя матричную теорему Кирхгофа, найдите число остовных деревьев в полном двудольном графе Km,n.

10. Докажите, что число помеченных двудольных деревьев с
числами вершин в долях m и n равно mn-1nm-1.

11. Покажите, как найти остов графа с помощью поиска в ширину.

12. Постройте такое множество и точек на плоскости, для которого вес дерева Штейнора был бы меньше веса любого остовного дерева графа К(U).

 

Глава III

Матроиды и трансверсали

 

В этой главе вводится пошли комбинаторный объект — матроид, появляющийся и результате обобщения хорошо известного читателю понятия линейной зависимости. Хотя понятие «матроид» возникло относительно давно,— в 30-е годы нашего столетия (впервые это понятие ввел
X. Уитни) — место теории матроидов в математике и, тем более, в математическом образовании первоначально не было осознано. Теперь же, когда открываются вес новые и новые классы матроидов, объединяющая роль идеи матроида, позволяющая с возрастающим успехом применять
к решению комбинаторных проблем методы алгебры, становится все более ясной.

Для нас матроиды интересны, прежде всего, по двум причинам. Первая — их связь с теорией графов. Фактически, именно соответствие между некоторыми теоретикографовыми и алгебраическими понятиями привело к созданию теории матроидов. Вторая причина состоит в том, что задачи оптимизации па матроидных структурах решаются с помощью простого, так называемого «жадного» алгоритма, который является обобщением алгоритма Краскала для нахождения остовного дерева минимального
веса в связном взвешенном графе (§ 15). «Жадный» алгоритм изучается в этой главе.

 

 

 

§ 16. Азбука теории матроидов

 

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

Матроидом М называется пара (Е, β, где Е — конечное непустое множество, а β (или β (М) — непустое множество ого подмножеств (называемых базами), удовлетворяющее следующим двум условиям (аксиомы баз}.

В.1. Никакая из баз по содержится в другой базе.

В.2. Если В1 и В2 — базы, то для любого элемента
b€B1 существует такой элемент c€B2, что (B1\b)Ụс—
также база.

Элементы множества Е называются элементами матроида М. Число |Е| называется порядком матроида М.

Понятие матроида является естественным обобщением понятия линейной независимости. А именно, если Е — конечная система векторов некоторого линейного пространства, содержащая ненулевой вектор, то в Е существует максимальная линейно независимая подсистема — база системы Е. Напомним, что все базы системы Е удовлетворяют аксиомам баз В.1 и В.2. Следовательно, всякая такая система вместе с ее базами является матроидом.
Этот матроид называется векторным.

Очевидно, что в обозначениях аксиомы В.2 либо b € В2 и тогда можно взять с = b, либо с€В2\В1, иное противоречило бы аксиоме В.1. Поэтому совокупность аксиом В.1 и В.2 равносильна совокупности аксиом В.1 и

В.2. Если В1, В2 € β и b€=B1\B2, то в В2\В1 существует такой элемент с, что (B1\b) U с€ β.

Утверждение 16.1. Все балы матроида равномощны.

►Пусть B1 и В2 — базы, |В1| ≤ |В2| и В1 = {b1, b2,…, bρ}. Согласно аксиоме В.2 в базе В2 существует такой элемент c1, что

В’ = (B1\b1)Uc1={c1,b2,…,bρ}€β

Далее, существует такой элемент с2 € В2, что

В» = ( B`\b2)Ục2={с1, c2, bз, …, bρ }€ β.

Итерируя этот процесс, получим базу В = {c1,c2, …,cp},
являющуюся подмножеством в В2 и потому совпадающую с В2 в силу В.1. Следовательно, |В2| = ρ.◄

Мощность базы матроида М назовем его рангом и обозначим через ρ (М).

Любое подмножество базы матроида называется независимым. В частности, пустое множество независимо. Совокупность всех независимых подмножеств элементов матроида М обозначим через Ĵ(М} (или просто Ĵ). Ниже множество Ĵ (М} называется набором независимых множеств матроида М.

Очевидно, что ß(М) совпадает с множеством элементов из Ĵ (М), максимальных относительно включения, так что множества ß (М) и Ĵ (М) определяют друг друга.

Теорема 16.2. Набор Ĵ (М) независимых множеств матроида удовлетворяет следующим двум условиям (аксиомы независимости).

I.1. Если Х€ Ĵ (М), Y
092713 0950 2712 Математика 27 Х, то Y € Ĵ (М).

I.2. Если X,Y€ Ĵ (М) и |Х| < |У|, то в У\Х существует такой элемент у, что Х и у € Ĵ (М}.

►Справедливость условия 1.1 очевидна; рассмотрим условие 1.2. Пусть X, Y€ Ĵ (М) и |Х|<|Y|. Пусть, далее, В€ß(M), Y092713 0950 2713 Математика 27B1. Среди баз, содержащих X, выберем такую базу В2, чтобы пересечение В1 092713 0950 2714 Математика 27 В2 содержало наибольшее число элементов. Докажем, что В2\Х092713 0950 2715 Математика 27В1. Действительно, если бы существовал элемент b092713 0950 2716 Математика 27 В2\Х, b092713 0950 2717 Математика 27В1, то по аксиоме В.2 в базе В1 нашелся бы такой
элемент z, что С=(B2\b) 092713 0950 2718 Математика 27 z092713 0950 2719 Математика 27 ß (М). Но тогда |С

092713 0950 2720 Математика 27 В1| >|В2
092713 0950 2721 Математика 27 В1|, что невозможно. Следовательно, В2\Х и Y содержатся в В1, причем |В2\Х| + |У| = =092713 0950 2722 Математика 27 (М)– |Х| + |У| >
092713 0950 2723 Математика 27 (М)= |В1|. Тем самым существует у
092713 0950 2724 Математика 27 (B2\Х)
092713 0950 2725 Математика 27У. Поскольку Х 092713 0950 2726 Математика 27 у 092713 0950 2727 Математика 27 В2, то элемент у — искомый. ◄

Очевидно, что аксиома I.2 эквивалентна следующей
аксиоме.

I`.2. Если X, Y
092713 0950 2728 Математика 27 Ĵ(M) и |X|<|Y|, то в Y существует такое подмножество Z, что Х
092713 0950 2729 Математика 27 Z
092713 0950 2730 Математика 27 Ĵ(M), |X
092713 0950 2731 Математика 27 Z| =|Y|.

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

Теорема 16.3. Пусть Е — конечное непустое множество, Ĵ — непустая совокупность его подмножеств, удовлетворяющая аксиомам независимости I.1 и 1.2, β — множество всех элементов из Ĵ, максимальных относительно
включения. Тогда β удовлетворяет аксиомам баз В.1 и В.2.

►Очевидно, что Х есть множество всех элементов из Ĵ максимальной мощности. Пусть теперь В1, В2
092713 0950 2732 Математика 27 ß, е1
092713 0950 2733 Математика 27 В1. Тогда В1\е1
092713 0950 2734 Математика 27
Ĵ, |B1\е1| = |B2| – 1. Следовательно, существует такой элемент е2

092713 0950 2735 Математика 27 В2, что

(B1\e1)
092713 0950 2736 Математика 27 e2=B3
092713 0950 2737 Математика 27
Ĵ,
|B3| = |B2|

Из последнего равенства вытекает, что B3
092713 0950 2738 Математика 27 ß. Тем самым доказано, что выполняется условие В.2. Справедливость условия В.1 очевидна. ◄

Предыдущая теорема даст основание для нового определения матроида. Матроидом назовем пару (Е, Ĵ), где Е — множество, а Ĵ — непустая совокупность его подмножеств (называемых независимыми), удовлетворяющих аксиомам независимости I.1 и I.2. Множество Y назовем набором, независимых множеств матроида. Максимальные относительно включения независимые подмножества назовем теперь базами матроида. Аксиомы баз при этом действительно будут выполняться. В этом смысле приведенные два определения матроида эквивалентны.

Определим ранговую функцию {функцию ранга) матроида М, ставящую в соответствие каждому подмножеству А 092713 0950 2739 Математика 27 Е число, равное максимальной из мощностей входящих в А независимых подмножеств и называемое
рангом множества А:

092713 0950 2740 Математика 27 (A)= max{|Х|: Х
092713 0950 2741 Математика 27 А, Х
092713 0950 2742 Математика 27 Ĵ (М)}.

Очевидно, что 092713 0950 2743 Математика 27 (Е) совпадает с определенным выше рангом 092713 0950 2744 Математика 27 (М). Очевидно также, что подмножество А 092713 0950 2745 Математика 27 Е независимо тогда и только тогда, когда 092713 0950 2746 Математика 27 (A) = |A|.

Теорема 16.4. Ранговая функция матроида удовлетворяет следующим трем условиям (аксиомы ранга):

092713 0950 2747 Математика 271. 0≤
092713 0950 2748 Математика 27(A)≤|A| для каждого А 092713 0950 2749 Математика 27 Е;

092713 0950 2750 Математика 272. 092713 0950 2751 Математика 27 (А)≤
092713 0950 2752 Математика 27 (В), если А
092713 0950 2753 Математика 27 В
092713 0950 2754 Математика 27 Е;

092713 0950 2755 Математика 273. 092713 0950 2756 Математика 27(A 092713 0950 2757 Математика 27B)+ 092713 0950 2758 Математика 27(A 092713 0950 2759 Математика 27B)≤ 092713 0950 2760 Математика 27(A) +
092713 0950 2761 Математика 27(B) для любых А,В
092713 0950 2762 Математика 27 Е.

►Первые два условия очевидны, рассмотрим третье. Пусть А,В
092713 0950 2763 Математика 27 Е, а Х — наибольшее по числу элементов независимое подмножество в A
092713 0950 2764 Математика 27В. Согласно условию I`.2 в А 092713 0950 2765 Математика 27В существует наибольшее по числу элементов независимое подмножество Y, содержащее X. Представим Y в виде Y=Х092713 0950 2766 Математика 27Y092713 0950 2767 Математика 27W, где V
092713 0950 2768 Математика 27 А\В, W
092713 0950 2769 Математика 27 В\А. Независимое подмножество Х
092713 0950 2770 Математика 27Y содержится в А, поэтому 092713 0950 2771 Математика 27 (A)≥ |Х092713 0950 2772 Математика 27V|. Аналогично 092713 0950 2773 Математика 27 (B)≥|Х
092713 0950 2774 Математика 27У|. Следовательно, 092713 0950 2775 Математика 27(А)+092713 0950 2776 Математика 27(В)≥|Х
092713 0950 2777 Математика 27 V| +|Х
092713 0950 2778 Математика 27W|. Поскольку Х
092713 0950 2779 Математика 27У=
092713 0950 2780 Математика 27У=ø, то далее имеем 092713 0950 2781 Математика 27
(A)+ 092713 0950 2782 Математика 27(B)≥|X|+(|X|+|V|+|W|). Но |Х|=
092713 0950 2783 Математика 27
092713 0950 2784 Математика 27В), |Х|+|V|+|W|= |Y|=
092713 0950 2785 Математика 27 (A 092713 0950 2786 Математика 27 B).

Итак, 092713 0950 2787 Математика 27 (А) + 092713 0950 2788 Математика 27 (В) ≥ 092713 0950 2789 Математика 27
092713 0950 2790 Математика 27 В) + 092713 0950 2791 Математика 27 (A
092713 0950 2792 Математика 27B) ◄

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

Множество циклов матроида М обозначим через ξ(М) (или просто У).

Теорема 16.5. Если М—матроид, то множество
ξ(М) удовлетворяет следующим двум условиям (аксиомы циклов).

С.1. Ни один из циклов не содержится в другом цикле.

С.2. Если С1 и С2 — несовпадающие циклы и е 092713 0950 2793 Математика 27 С1 092713 0950 2794 Математика 27С2, то множество (С1 и С2)\е также содержит цикл.

►Выполнимость условия С.1 очевидна, рассмотрим условие С.2. Пусть D=(С1 и С2) \е. Достаточно доказать, что множество D зависимо. Прибегнем к помощи ранговой функции; в ее терминах нужно доказать неравенство
092713 0950 2795 Математика 27 (D)<|D|. Но D

092713 0950 2796 Математика 27 С1 и С2, и потому 092713 0950 2797 Математика 27 (D)≤ 092713 0950 2798 Математика 27 (С1 092713 0950 2799 Математика 27С2).
Согласно аксиоме 092713 0950 27100 Математика 27.3:

092713 0950 27101 Математика 27 (С1
092713 0950 27102 Математика 27С2)≤ 092713 0950 27103 Математика 27 (С1) + 092713 0950 27104 Математика 27 (С2) – 092713 0950 27105 Математика 27 (С1
092713 0950 27106 Математика 27 С2).

Очевидно, что 092713 0950 27107 Математика 27 (С1)== |С1| — 1 для цикла С1. Так как множество С1092713 0950 27108 Математика 27С2 независимо, то 092713 0950 27109 Математика 27 (C1 092713 0950 27110 Математика 27C2) = |C1 092713 0950 27111 Математика 27C2|. Итак,

092713 0950 27112 Математика 27    (D)≤ 092713 0950 27113 Математика 27(C1 092713 0950 27114 Математика 27C2) ≤ |C1| — 1 + |C2| -1 — |C1 092713 0950 27115 Математика 27C2| =|C1 092713 0950 27116 Математика 27C2| — 2

и

|D| = |C1
092713 0950 27117 Математика 27 C2| -1

а значит, 092713 0950 27118 Математика 27 (D)< |D|.◄

Заметим, что совокупность аксиом 092713 0950 27119 Математика 27.1 — 092713 0950 27120 Математика 27.3 (как и С.1, С.2) можно использовать для еще одного определения матроида.

Следствие 16.6. Если М=(Е, Ĵ) — матроид с набором независимых множеств Ĵ, Х
092713 0950 27121 Математика 27 Y, у 092713 0950 27122 Математика 27 Е, то множество Х 092713 0950 27123 Математика 27 у содержит не более одного цикла.

►Пусть, напротив, в Х 092713 0950 27124 Математика 27у есть два несовпадающих цикла С1 и С2. Элемент у содержится в каждом из них, и, согласно предыдущей теореме, существует третий цикл С в множестве D ==(C1 092713 0950 27125 Математика 27 С2)\y. Следовательно, В—зависимое множество. Но D 092713 0950 27126 Математика 27 X и потому независимо. Полученное противоречие доказывает нужное утверждение. ◄

Очевидно, что из предыдущего следствия вытекает

Следствие 16.7. Для любой базы В матроида и любого его элемента e, не входящего в эту базу, множество В 092713 0950 27127 Математика 27 е содержит ровно один цикл.

 

§ 17. Двойственный матроид

 

Пусть М = (Е,ß) — матроид с множеством баз ß. Для
произвольного Х 092713 0950 27128 Математика 27 Е положим 092713 0950 27129 Математика 27=Е\Х. Если В 092713 0950 27130 Математика 27 ß, то множество 092713 0950 27131 Математика 27 назовем кобазой матроида М. Пусть ß* = {

092713 0950 27132 Математика 27: В 092713 0950 27133 Математика 27 ß } — множество всех кобаз.

Теорема 17.1. Множество ß* удовлетворяет аксиомам баз В.1 и В’.2.

►Справедливость условия В.1 очевидна, рассмотрим условие В’.2. Пусть 092713 0950 27134 Математика 271 и 092713 0950 27135 Математика 272 — две кобазы, х
092713 0950 27136 Математика 27
092713 0950 27137 Математика 271\

092713 0950 27138 Математика 272.

Нужно доказать существование в 092713 0950 27139 Математика 271\
092713 0950 27140 Математика 272 такого элемента у, что

А=(092713 0950 27141 Математика 271\х)
092713 0950 27142 Математика 27у092713 0950 27143 Математика 27 ß*. (1)’

Так как х 092713 0950 27144 Математика 27 В1, то согласно следствию 16.7 множество B1 092713 0950 27145 Математика 27 x содержит цикл С. Поскольку цикл не может содержаться в базе, то существует у 092713 0950 27146 Математика 27 С 092713 0950 27147 Математика 27092713 0950 27148 Математика 272. Так как x 092713 0950 27149 Математика 27 В2, то у≠х. Следовательно, у
092713 0950 27150 Математика 27 В1. Итак, у
092713 0950 27151 Математика 27
092713 0950 27152 Математика 272\092713 0950 27153 Математика 271.

Теперь докажем, что верно (1). С этой целью рассмотрим множество 092713 0950 27154 Математика 27=(B1092713 0950 27155 Математика 27x)\у. В силу следствия 16.7 С является единственным циклом, содержащимся в В1
092713 0950 27156 Математика 27х. Поэтому 092713 0950 27157 Математика 27 но содержит циклов и, следовательно, является независимым множеством. Далее |092713 0950 27158 Математика 27| =|B1|, так что 092713 0950 27159 Математика 27 — база и потому A — кобаза. ◄

Из предыдущей теоремы вытекает, что пара (Е, β*) является матроидом с множеством баз . β*. Этот матроид называется двойственным к матроиду М и обозначается через М*. Очевидно, что М** = М.

Зависимое (независимое) множество элементов матроида М* называется козависимым (конезависимым) в М. Цикл матроида М* называется коциклом матроида М. Ранговая функция матроида М* называется коранговой
функцией матроида М и обозначается через 092713 0950 27160 Математика 27*. Очевидно, что 092713 0950 27161 Математика 27*(М)== |Е| — –092713 0950 27162 Математика 27
(M).

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

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

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

Теорема 17.3. Непустое подмножество Х элементов матроида является циклом тогда и только тогда, когда оно удовлетворяет следующим двум условиям:

1) |Х 092713 0950 27163 Математика 27С| ≠ 1 для каждого коцикла С;

2) Х — минимальное относительно включения непустое подмножество, удовлетворяющее условию 1).

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

Лемма 17.4. Для любого непустого независимого подмножества Х элементов матроида существует такой коцикл С, что |Х 092713 0950 27164 Математика 27 С| = 1.

►Множество Х содержится и некоторой базе В. Пусть х 092713 0950 27165 Математика 27 X. В силу следствия 16.7 множество 092713 0950 27166 Математика 27
092713 0950 27167 Математика 27 х содержит некоторый коцикл С. Очевидно, что С 092713 0950 27168 Математика 27 В = {х} = C
092713 0950 27169 Математика 27X. ◄

Лемма 17.5. Для всякого цикла Х и любого коцикла С матроида верно соотношение |Х 092713 0950 27170 Математика 27 С| ≠ 1.

►Пусть, напротив, |Х 092713 0950 27171 Математика 27 С| = {x}. Согласно утверждению 17.2 коцикл С — минимальное подмножество в Е, имеющее непустое пересечение с каждой базой. Следовательно, 092713 0950 27172 Математика 27 — максимальное подмножество в Е, не содержащее баз, и потому 092713 0950 27173 Математика 27092713 0950 27174 Математика 27x содержит некоторую базу 092713 0950 27175 Математика 27. Множество Х\х независимо и содержится в 092713 0950 27176 Математика 27092713 0950 27177 Математика 27x. Из аксиомы 1.2 теперь получаем, что существует база D, удовлетворяющая условию Х\х092713 0950 27178 Математика 27D092713 0950 27179 Математика 27092713 0950 27180 Математика 27092713 0950 27181 Математика 27x. Но 092713 0950 27182 Математика 27 не содержит баз, поэтому х092713 0950 27183 Математика 27 D, Х092713 0950 27184 Математика 27 D. Последнее противоречит аксиоме 1.1. ◄

►Доказательство теоремы 17.3. Необходимость. Пусть Х — цикл. Тогда на основании леммы 17.5 |Х 092713 0950 27185 Математика 27 С| ≠ 1 для каждого коцикла С. Любое подмножество из Х независимо и, в силу леммы 17.4, не удовлетворяет условию 1).

Достаточность. Пусть Х — непустое подмножество элементов матроида, удовлетворяющее условиям 1) и 2). Согласно лемме 17.4 множество Х зависимо. Все его собственные подмножества не удовлетворяют условию 1) и независимы в силу леммы 17.5.◄

 

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

 

Рассмотрим некоторые примеры матроидов.

1. Пара (Е, {Е}), где Е—конечное непустое множество, является матроидом, единственной базой которого служит само множество Е. Этот матроид называется свободным (или дискретным). Циклов свободный матроид
не имеет, всякое подмножество Х г Е независимо, 092713 0950 27186 Математика 27 (Х)=|Х|.

Двойственный к свободному — тривиальный матроид (Е, (Ø)), единственной базой которого является пустое множество. Очевидно, что Ø служит единственным независимым множеством тривиального матроида; его циклы — все одноэлементные подмножества множества Е; 092713 0950 27187 Математика 27 (Х)==0 для любого X
092713 0950 27188 Математика 27 E

2. Пусть L линейное пространство над произвольным полем Р, Е 092713 0950 27189 Математика 27 L — конечное непустое подмножество, Ј — множество, элементами которого служат все линейно независимые над F системы векторов из Е и пустое множество. Тогда пара (Е, Ј) является матроидом с набором независимых множеств Ј (этот факт вытекает из известной в линейной алгебре теоремы Штейница о замене). Такой матроид называется векторным, матроидом, порожденным множеством векторов Е. Базами этого матроида служат все базы множества Е. Если же в Е нет баз, т.е. если Е = (0), то единственной базой векторного матроида является пустое множество, т. е. он тривиален. Ранг векторного матроида равен рангу множества Е, т. е. размерности подпространства, порожденного множеством Е.

В частности, взяв в качестве Е множество векторов, являющихся столбцами (строками) какой-либо матрицы А, получим матричный матроид, или матроид столбцов (строк) матрицы А. Ранг этого матроида равен рангу
матрицы А.

В качество иллюстрации рассмотрим матроид М столбцов матрицы

A =092713 0950 27190 Математика 27

Обозначив i-й столбец этой матрицы через ei (i=092713 0950 27191 Математика 27), получим Е={е1, е2, е3, е4}, 092713 0950 27192 Математика 27 (М)=rankА =3. Перебирая все максимальные линейно независимые системы столбцов матрицы А, обнаружим, что матроид М имеет ровно
3 базы: В1 = ={е1, е2, е3}, B2=={е1, е2, е4}, В3=={е1, е3, е4}.
Зависимых множеств 2: Е и {е2, е3, е4}, причем последнее
множество служит единственным циклом матроида М. Кобазы: 092713 0950 27193 Математика 271= {e4}, 092713 0950 27194 Математика 272 = ={e3}, 092713 0950 27195 Математика 27
3 ={e2} . Козависимые множества: {е1} и каждое подмножество в Е, содержащее более одного элемента. Коциклы: {e1}, {е2, е3}, {е2, е4},{е3, е4}.

3. Пусть G — произвольный граф. Определим матроид М(G)=(Е, β) на множестве Е=ЕG, объявив базами множества ребер всех остовов графа G, т. е. ß== {ЕН: Н—остов G}. Из утверждения 13.8 вытекает, что аксиомы баз в этой ситуации действительно выполняются. Поскольку каждый подграф графа G, являющийся лесом, содержится в некотором остове (утверждение 13.7), то независимыми множествами в М(G) служат множества ребер подграфов в G, являющихся лесами, и только они. Циклы матроида М(G) — это множества ребер простых циклов графа G. Если n(G), m(G), k(G)—числа вершин, ребер и компонент графа G соответственно, то

 

092713 0950 27196 Математика 27    (М(G))=n(G) – k(G)=v*(G),

092713 0950 27197 Математика 27*(М(G))=m(G}-092713 0950 27198 Математика 27(М(G))=v(G),

т. е. ранг и коранг матроида М(G) равны, соответственно, коциклическому рангу и циклическому рангу графа G.

Если В — множество всех ребер какого-либо остова графа G, то множество ЕG\В называется коостовом. Подмножество и с= ЕС называется разделяющим множеством графа G, если число компонент графа G — и больше, чем число компонент С. Минимальное относительно включения разделяющее множество насыпается разрезом. Кобазами в М(G) служат коостовы графа G. Из утверждения 17.2 непосредственно вытекает,
что козависимые множества и М (G) — это разделяющие множества графа G, а коциклы — это разрезы. Поэтому между свойствами простых циклоп и разрезов

 

092713 0950 27199 Математика 27

Рис. 18.1

 

графа существует большая аналогия. Эта аналогия и явилась одной из причин возникновения понятия «матроид».

Матроиды М (G) и М*(G) называются матроидом циклов (циклическим матроидом) и матроидом разрезов (коциклическим матроидом) графа G соответственно.

Рассмотрим, например, циклический матроид М(G) графа G, изображенного на рис. 18.1. Для этого матроида E ={е1, е2, е3, e4}. Он имеет ровно три базы: В1 ={е1, е2, e4}, В2 = {е1, е3, e4}, B3={е2, е3, e4}. Едиственным его
циклом служит множество {е1, е2, е3}. Кобазы: 092713 0950 27200 Математика 27
1 ={e3},
092713 0950 27201 Математика 272=={е2}, 092713 0950 27202 Математика 273=={е1}; коциклы: {е1, е2}, {е1, е3}, {е2, е3}, {e4}.

Очевидно, что для любого дерева Т циклический матроид М (Т) свободен, а М* (Т) тривиален.

Вернемся к произвольным графам. Применяя установленные выше утверждения о свойствах баз, независимых множеств и циклоп матроида к матроидам М(G) и М* (G), получим следующие утверждения о графах,
Каждое из них несложно доказать непосредственно, однако здесь вскрывается их общая сущность.

<

Утверждение 18.1. Пусть F и H — ациклические подграфы графа G и |EF| < |ЕН|. Тогда существует такое подмножество Х092713 0950 27203 Математика 27ЕН, что граф F’=F+Х также является ациклическим и |ЕF`| = |ЕН|.

Утверждение 18.2. Если D1 и D2 — несовпадающие разрезы в графе G, имеющие общее ребро е, то множество ребер (D1092713 0950 27204 Математика 27D2)\е является разделяющим.

Утверждение 18.3. Для любого непустого ациклического подграфа F графа G существует разрез в G, имеющий с F ровно одно общее ребро.

Утверждение 18.4. Число общих ребер любого простого цикла и любого разреза графа отлично от 1.

Замечание. Очевидно, что в формулировках утверждений 18.1—18.4 может фигурировать произвольный псевдограф, а не только простой граф.

 

§ 19. Изоморфизм матроидов

 

Пусть М1=(Е1,ß1) и М2=(Е2,ß2) — два матроида с множествами баз ß1 и ß2, 092713 0950 27205 Математика 27: Е1→Е2 — биекция. Для Х
092713 0950 27206 Математика 27Е1 положим 092713 0950 27207 Математика 27 (Х)={
092713 0950 27208 Математика 27(x) : x 092713 0950 27209 Математика 27X}. Если для любого X
092713 0950 27210 Математика 27E1 имеем 092713 0950 27211 Математика 27(Х)
092713 0950 27212 Математика 27 ß2 тогда и только тогда, когда Х
092713 0950 27213 Математика 27 ß1, то биекция 092713 0950 27214 Математика 27 называется изоморфизмом матроида М1 на матроид М2.

В этой ситуации будем писать

092713 0950 27215 Математика 27 : М1→M2 (1)

Для изоморфизма 092713 0950 27216 Математика 27 существует обратная биекция 092713 0950 27217 Математика 27-1, причем очевидно, что для любого Y
092713 0950 27218 Математика 27 E2 имеем 092713 0950 27219 Математика 27-1 (Y)
092713 0950 27220 Математика 27 ß1 тогда и только тогда, когда Y
092713 0950 27221 Математика 27 ß2. Следовательно, если (1)—изоморфизм матроидов, то и 092713 0950 27222 Математика 27-1: M2→ М1 — также изоморфизм.

Если существует изоморфизм (1), то будем называть матроиды M1 и M2 изоморфными и писать М1
092713 0950 27223 Математика 27 М2.

Утверждение 19.1. Если 092713 0950 27224 Математика 27: М1→М2 — изоморфизм матроидов, то:

1) 092713 0950 27225 Математика 27(Х) — независимое множество матроида М2 тогда и только тогда, когда Х является независимым множеством матроида М1;

2) 092713 0950 27226 Математика 27(Х) — цикл матроида М2 тогда и только тогда, когда Х является циклом матроида М1;

3) 092713 0950 27227 Математика 27(Х) — кобаза матроида М2 тогда и только тогда, когда Х является кобазой матроида М1;

4) 092713 0950 27228 Математика 27(Х) — коцикл матроида М2 тогда и только тогда, когда Х является коциклом в М1.

►1) Пусть Х—независимое множество матроида М1. Тогда Х содержится в некоторой базе В
092713 0950 27229 Математика 27 ß1. Множество 092713 0950 27230 Математика 27 (Х) содержится в базе 092713 0950 27231 Математика 27 (В) 092713 0950 27232 Математика 27ß2 и потому независимо в матроиде М2. Поскольку множество 092713 0950 27233 Математика 27 (Х) отображается на Х обратным изоморфизмом 092713 0950 27234 Математика 27-1, то из независимости множества 092713 0950 27235 Математика 27 (Х) в свою очередь следует независимость множества X.

2) Пусть Х — цикл матроида М1, т. е. минимальное относительно включения зависимое множество. Применяя уже доказанное утверждение 1), заключаем, что 092713 0950 27236 Математика 27 (Х) — минимальное относительно включения зависимое множество матроида М2.

3) Положим 092713 0950 27237 Математика 27=Е\Х. Множество Х — кобаза матроида М1 тогда и только тогда, когда 092713 0950 27238 Математика 27 — база М1, т. е. когда 092713 0950 27239 Математика 27 (Х)— база матроида М2. Последнее равносильно тому, что 092713 0950 27240 Математика 27 (Х)— кобаза в М2. Но 092713 0950 27241 Математика 27=
092713 0950 27242 Математика 27Х}.

4) Коциклы матроида — это минимальные независимые множества. Подмножество Х элементов матроида М1 козависимо тогда и только тогда, когда оно пересекается с любой базой этого матроида. Последнее равносильно
тому, что множество 092713 0950 27243 Математика 27 (Х) пересекается с любой базой матроида М2, т. е. 092713 0950 27244 Математика 27 (Х) козависимо в матроиде М2. ◄

 

092713 0950 27245 Математика 27

G

092713 0950 27246 Математика 27

H

Рис. 19.1

 

Из предыдущего утверждения непосредственно вытекает

Следствие 19.2. Если матроиды изоморфны, то двойственные матроиды также изоморфны, т. е. если 092713 0950 27247 Математика 27: М1→ М2 — изоморфизм матроидов, то 092713 0950 27248 Математика 27: М*1→ М*2 также является изоморфизмом матроидов.

Итак, изоморфные матроиды «одинаково устроены», что дает основание их но различать. Поэтому любой матроид, изоморфный векторному, также назовем векторным. Матроид назовем графическим, если оп изоморфен матроиду циклов М(G) некоторого графа G, и кографическим, если он изоморфен матроиду разрезов М*(G).

На рис. 19.1 изображены два графа G и H, циклические матроиды которых изоморфны.

 

§ 20. Представление матроида

 

Стремление понять строение тех матроидов, которые близки к векторным, т. е. если и не являются векторными, то отличаются от последних лишь незначительно, приводит к понятию представления матроида, в определенном смысле близкому к понятию изоморфизма.

Пусть М — матроид с множеством элементов Е, Fn — линейное пространство столбцов высоты n над полем F. Отображение 092713 0950 27249 Математика 27: Е → Fn называется представлением матроида М над полем F, если оно удовлетворяет следующему условию: для любого подмножества Х={е1, е2, …, еk} множества Е система векторов 092713 0950 27250 Математика 27 (e1), 092713 0950 27251 Математика 27 (е2), … , 092713 0950 27252 Математика 27 (еk) линейно независима над полем F тогда и только тогда, когда Х является независимым множеством матроида М.

Пусть 092713 0950 27253 Математика 27: Е → Fn – представление матроида М, Е={е1, e2, .., еm}. Построим n x m-матрицу

092713 0950 27254 Математика 27 (E)=[
092713 0950 27255 Математика 27(e1) 092713 0950 27256 Математика 27 (e2) … 092713 0950 27257 Математика 27 (em)],

столбцами которой являются образы элементов матроида М в представлении 092713 0950 27258 Математика 27. Эта матрица также называется представлением матроида М.

Утверждение 20.1. Пусть М — матроид с множеством элементов Е={е1, е2, …, em), А — произвольная n x m-матрица над полем F. Для того чтобы матрица А была представлением матроида М, необходимо и достаточно выполнение следующих двух условий:

1) rank A = 092713 0950 27259 Математика 27 (М);

2) система любых 092713 0950 27260 Математика 27 = 092713 0950 27261 Математика 27 (М) столбцов матрицы А с номерами i1,i2, …, ip линейно независима тогда и только тогда, когда множество [еi1 , еi2, . .., еip} является базой матроида М.

►Очевидно, что A=092713 0950 27262 Математика 27 (Е) удовлетворяет условиям 1) и 2). С другой стороны, пусть n x m-матрица А удовлетворяет этим условиям и пусть А1, А2, …, Аm — ее столбцы. Тогда, положив 092713 0950 27263 Математика 27(ei)=Ai, получим представление 092713 0950 27264 Математика 27: Е → Fn матроида М. ◄

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

Пусть М—матроид с множеством элементов Е={1, 2, 3}, базами которого служат все двухэлементные подмножества множества Е. Очевидно, что этот матроид представим пал произвольным полем, поскольку матрица

092713 0950 27265 Математика 27

служит представлением матроида М.

С другой стороны, возьмем в качестве М матроид с множеством элементов Е={1, 2, 3, 4}, базами которого, как и выше, служат вес двухэлементные подмножества множества Е. Пусть матрица А является представлением этого матроида над полем F из двух элементов. Тогда rank А = 2 и, следовательно, столбцы этой матрицы принадлежат двумерному линейному пространству над F.
Двумерное линейное пространство над полем из двух элементов — это четырехэлементное множество {а, b, а+b, 0). Следовательно, столбцами матрицы А являются а, b, а + b, 0. По поскольку любое двухэлементное подмножество множества Е является базой матроида M, то любые два столбца матрицы А должны быть линейно независимы. Полученное противоречие доказывает, что
матроид М не представим над нолем из двух элементов.

Если же F — произвольное поле, содержащее более двух элементов, то, например, матрица

092713 0950 27266 Математика 27, b
092713 0950 27267 Математика 27 F, b≠0, b≠1

является представлением матроида М над F. Итак, рассматриваемый матроид представим над любым полем, кроме поля из двух элементовю

Очевидно, что свободный матроид представлен над любым полем – его представлением служат, например, единичная матрица. Двойственный ему тривиальный матроид также представим, его представление — нулевая матрица.

Заметим, что существуют матроиды, не представление ни над каким полем.

Из определения представления вытекает, что оно действует инъективно на каждом независимом множестве элементов матроида. Однако в целом оно может оказаться и не инъективным. Рассмотрим, например, матроид М=(Е,ß) с множеством элементов Е={1, 2, 3, 4, 5} и множеством баз ß={{3, 4}, {3, 5), {4, 5}. Его циклами служат множества {1}, {2} и {3, 4, 5). Положив

092713 0950 27268 Математика 27    (E) = 092713 0950 27269 Математика 27,

получим представление 092713 0950 27270 Математика 27 матроида М над произвольным полем. Это представлено не является инъективным. Очевидно, что рассматриваемый матроид не имеет инъективных представлений ни над каким полем, поскольку


092713 0950 27271 Математика 27 (1)= 092713 0950 27272 Математика 27 (2)=0 для любого представления 092713 0950 27273 Математика 27 этого матроида.

Легко попять, что матроид, для которого существует инъективное представление, является векторным. В самом деле, для произвольного представления 092713 0950 27274 Математика 27 некоторого матроида М=(Е, ß) рассмотрим множество столбцов
{

092713 0950 27275 Математика 27 (е): е
092713 0950 27276 Математика 27 Е} Это множество порождает векторный матроид, который обозначим через 092713 0950 27277 Математика 27 (М). Если отображение 092713 0950 27278 Математика 27 инъективно, то оно естественно индуцирует изоморфизм 092713 0950 27279 Математика 27 ‘ матроидов М и 092713 0950 27280 Математика 27 (М): 092713 0950 27281 Математика 27 ‘(е)=
092713 0950 27282 Математика 27 (е) для любого элемента е матроида М. Итак, верно

Утверждение 20.2. Если представление 092713 0950 27283 Математика 27 матроида М инъективно, то М
092713 0950 27284 Математика 27
092713 0950 27285 Математика 27 (М).

С другой стороны, пусть L — n-мерное линейное пространство над произвольным полом F, Е 092713 0950 27286 Математика 27 L — конечное непустое подмножество, M-векторный матроид, порожденный множеством векторов Е. Зафиксируем в пространстве L произвольный базис. Поставив в соответствие каждому вектору из Е его координатный столбец в отмеченном базисе, получим представление Е →Fn матроида М, являющееся инъективным.

Итак, инъективные представления существуют у всех векторных матроидов и только у них.

Теорема 20.3. Если матроид представим над полем F, то двойственный ему матроид также представим над F.

►Для свободного и тривиального матроидов утверждение теоремы очевидно. Пусть М — нетривиальный матроид, не являющийся свободным, 092713 0950 27287 Математика 27 =
092713 0950 27288 Математика 27 (М), n x m-матрица А — представление над полем F матроида М. Тогда rank А = 092713 0950 27289 Математика 27, 0 < 092713 0950 27290 Математика 27 < m.

Рассмотрим однородную систему

АХ=0 (1)

линейных уравнений с матрицей А (здесь Х — столбец неизвестных x1, х2, …, xm, 0 — нулевой столбец высоты n). Пусть Y — множество всех столбцов из Fm, являющихся решениями системы (1). Как известно из алгебры, Y — подпространство пространства Fm размерности m — 092713 0950 27291 Математика 27.

Выберем какой-либо базис

Y1,Y2,…,Y m- 092713 0950 27292 Математика 27 (2)

подпространства Y и составим из столбцов (2) m x (m-
092713 0950 27293 Математика 27)-матрицу В = [Y1,Y2,…, Y m- 092713 0950 27294 Математика 27].

Теперь докажем, что транспонированная матрица ВТ является представлением матроида М*, для чего используем утверждение 20.1. Имеем

rank ВТ =rank B = m —
092713 0950 27295 Математика 27 (М*).

Далее вспомним, что базами матроида М* являются дополнения до баз матроида М. Поэтому достаточно установить следующее: система каких-либо 092713 0950 27296 Математика 27 столбцов матрицы А линейно независима тогда и только тогда, когда линейно независима дополняющая система m – 092713 0950 27297 Математика 27 столбцов матрицы ВТ (или строк матрицы ВТ). Слово «дополняющая» означает, что номера столбцов второй системы отличны от номеров столбцов первой.

Выделим какую-либо систему 092713 0950 27298 Математика 27 столбцов матрицы А. Пусть, для определенности, это первые 092713 0950 27299 Математика 27 столбцов, и пусть С—подматрица в А, составленная из взятых столбцов. Теперь рассмотрим однородную систему линейных уравнений

СZ=0 (3)

с матрицей С (Z—столбец неизвестных z1, z2, …, z092713 0950 27300 Математика 27). Если столбцы матрицы С линейно зависимы, то система (3) имеет ненулевое решение Z. Рассмотрим столбец

U=
092713 0950 27301 Математика 27

высоты m, полученный добавлением m — 092713 0950 27302 Математика 27 пулей к столбцу Z. Очевидно, что U—решение системы (1), т. е. U 092713 0950 27303 Математика 27Y. Поскольку (2)—базис пространства Y, то

U =α1Y1+ α2Y2+…+ αm-ρYm-ρ. (4)

Введем столбцы

Y`1,Y`2, … , Y`m-ρ (5)

высоты m — 092713 0950 27304 Математика 27, отбросив из каждого столбца (2) первые 092713 0950 27305 Математика 27 координат, и рассмотрим матрицу D = [Y`1,Y`2, … , Y`m-ρ], столбцами которой являются векторы (5). Это квадратная матрица, строки которой суть последние m—
092713 0950 27306 Математика 27 строк матрицы В. Из равенства (4) следует

α1Y`1+ α2Y`2+…+ αm-ρY`m-ρ = (6)

Среди коэффициентов αi в последнем равенстве есть отличные от нуля, поскольку и U≠0. Следовательно, система столбцов (5) линейно зависима.

Обратно, пусть система каких-либо, например, последних m — 092713 0950 27307 Математика 27 строк матрицы В линейно зависима. Тогда (5) — линейно зависимая система векторов, и потому верно равенство вида (6), среди коэффициентов αi которого
есть отличные от нуля. Определим столбец U формулой (4). Поскольку система векторов (2) линейно независима, то U≠0, и U—решение системы (1). Итак, система (1) имеет ненулевое решение вида U. Но тогда столбец 2, который получается из U в результате удаления последних m — 092713 0950 27308 Математика 27 координат, является ненулевым решением системы (3). Следовательно, столбцы матрицы С линейно зависимы.

Доказано, что из линейной зависимости каких-либо m — 092713 0950 27309 Математика 27 строк матрицы В вытекает линейная зависимость дополняющей системы 092713 0950 27310 Математика 27 столбцов матрицы А. Тем самым доказана теорема. ◄

 

§ 21. Бинарные матроиды

 

Рассмотрим более детально матроиды, представимые над полем из двух элементов,— бинарные матроиды.

Бинарным является, например, матроид М = (Е, ß) с множеством элементов Е = {1, 2, 3, 4}, множество ß баз которого составляют все трехэлементные подмножества в Е, содержащие 1. В самом деле, положив 092713 0950 27311 Математика 27 (1) =(1, 1, 0, 0), 092713 0950 27312 Математика 27(2)=(0, 1, 1, 0), 092713 0950 27313 Математика 27 (3)=(0,0,1,1). 092713 0950 27314 Математика 27 (4)=(0, 1, 0, 1), получим представление матроида М над полем из двух элементов 0 и 1.

Пусть F = {0, 1} = Z2; — поле классов целых чисел по модулю 2, М — матроид с множеством элементов Е, m — порядок матроида М, т. е. число элементов в Е, Zkбулеан множества Е (совокупность всех подмножеств множества Е). Превратим этот булеан в линейное пространство над ZZ, определив подходящим образом сложение подмножеств и их умножение на 0 и 1. Именно, для X. Y
092713 0950 27315 Математика 27 2k положим Х + Y = (X 092713 0950 27316 Математика 27У) \ (X 092713 0950 27317 Математика 27У) — сумма множеств по модулю 2 (симметрическая разность), 1·Х= X, 0-Х==0. Прямая проверка подтверждает, что в 2k внесена структура линейного пространства над Z2, нулевым вектором которого служит Ø.

Пусть L — подмножество пространства 2k, состоящее из пустого множества, всех циклов матроида М и объединений попарно непересекающихся циклов. Фиксируем какую-либо базу В матроида М. Согласно следствию 16.7 для любого е 092713 0950 27318 Математика 27
092713 0950 27319 Математика 27 в множестве В 092713 0950 27320 Математика 27е существует ровно один цикл. Обозначим этот цикл через Сe.

Теорема 21.1. Если исходный матроид М является
бинарным, то L — подпространство пространства 2k размерности 092713 0950 27321 Математика 27*(М), базис которого составляют все циклы из множества

{Се: е
092713 0950 27322 Математика 27
092713 0950 27323 Математика 27}, (1)

где В — произвольная база матроида М.

►Пусть n x m-матрица A является представлением
матроида М над Z2. Для произвольного непустого подмножества Х множества Е обозначим через S(Х) сумму (по модулю 2) всех столбцов матрицы А, соответствующих элементам из X.

Заметим, что непустое подмножество Х 092713 0950 27324 Математика 27 Е является элементом множества L тогда и только тогда, когда S(Х)=0. Действительно, пусть вначале Х—цикл. Тогда система столбцов, соответствующих элементам из X, линейно зависима над Z2, и потому для какого-либо подмножества Y в Х S(Y)=0. Но всякая часть рассматриваемой системы столбцов линейно независима, следовательно, Y = X. Итак, S(Х)=0 для цикла X. Очевидно, что то же верно, если Х—объединение попарно непересекающихся циклов.

Обратно, пусть Х
092713 0950 27325 Математика 27 Е и S(Х)=0. Тогда система столбцов матрицы А, соответствующих элементам подмножества X, линейно зависима над Z2 и, следовательно, Х—зависимое множество. Поэтому оно содержит цикл Х1.
Если Y=Х\Х1≠Ø, то S(Y)=0, поскольку S(Х)==S(Х1)=0 и S(Х)=S(Х1)+S(Y). Следовательно, Y содержит цикл Х2. Через несколько подобных тагов мы разобьем множество Х на непересекающиеся циклы.

Пусть Х н У—произвольные элементы множества L, Z = X 092713 0950 27326 Математика 27Y, X’ = X\Z, Y` = Y\Z. Тогда X + Y = X’ 092713 0950 27327 Математика 27 У`, Х’
092713 0950 27328 Математика 27У`=Ø, S(Х+У)=S(Х’)+S(У’). Но S(X)=0=
=S(Х’)+S(Z}, поэтому S(Х’)=S(Z)). Аналогично S(X’)=S(Z). Следовательно, S(Х+ +Y)=S(Z)+S(Z)=0.

Тем самым доказано, что L — подпространство пространства 2е.

Теперь докажем, что (1) —базис пространства L. Если бы система векторов (1) была линейно зависимой над Z2, то сумма каких-либо из них была бы равна нулевому вектору пространства 2k, т. е. пустому множеству. Но если е1, е2, …, еk — попарно различные элементы из В, то

Се1+Се2+ … + Сеk 092713 0950 27329 Математика 27 { е1, е2, …, еk }.

Следовательно, система (1) линейно независима.

Остается доказать, что произвольный элемент Х пространства L является суммой по модулю 2 каких-либо циклов из (1). Это очевидно для Х=Ø. Пусть х
092713 0950 27330 Математика 27 L и Х≠Ø. Согласно утверждению 17.2 Х
092713 0950 27331 Математика 27092713 0950 27332 Математика 27≠Ø. Если Х
092713 0950 27333 Математика 27092713 0950 27334 Математика 27 = { е1, е2, …, еk }, то

X = Се1+Се2+ … + Сеk

В самом деле, это равенство равносильно равенству

Се,+Се,+ … + Сеk +Х=0 (=Ø). (2)

Левую часть последнего обозначим через D. Так как Сеi 092713 0950 27335 Математика 27092713 0950 27336 Математика 27 = {еi} и е092713 0950 27337 Математика 27X, то D092713 0950 27338 Математика 27092713 0950 27339 Математика 27=Ø. Следовательно, D — независимое множество. С другой стороны, D
092713 0950 27340 Математика 27 L, а каждый элемент пространства L, отличный от пустого
множества, является зависимым множеством. Итак, D =Ø, т. е. верно равенство (2). ◄

Заметим, что условие бинарности в формулировке теоремы 2.1 существенно. Пусть, например, М=(Е,ß)—
матроид с множеством элементов E= {1, 2, 3, 4}, базами которого служат все двухэлементные подмножества множества Е. Тогда {1, 2, 3} и {1, 2, 4} — циклы, а {1, 2, 3}+{1, 2, 4} = {3, 4} — база. Следовательно, множество L не является в этом случае подпространством.

Возвратимся к бинарным матроидам. Пространство L
называется пространством циклов матроида М, а его базис (1) — базисом циклов этого матроида (относительно базы В).

Так как двойственный матроид М* также является бинарным (теорема 20.3), то верпа теорема, двойственная предыдущей, и возникают понятия пространства коциклов и базиса коциклов. Именно, пусть L* — подмножество булеана 2k, элементами которого служат все коциклы матроида М, объединения попарно непересекающихся коциклов и пустое множество. Фиксируем в М
базу В. Тогда для любого элемента е

092713 0950 27341 Математика 27 В множество 092713 0950 27342 Математика 27092713 0950 27343 Математика 27е содержит ровно один коцикл С*е. В этих обозначениях верно

Следствие 21.2. Множество L* является подпространством пространства 2k размерности 092713 0950 27344 Математика 27 (М). Множество коциклов

{С*е
092713 0950 27345 Математика 27 В}, (3)

где В — фиксированная база матроида М, служит базисом этого пространства.

Базисы циклов (1) и коциклов (3) легко определяются друг через друга. Верна следующая

Теорема 21.3. Пусть f
092713 0950 27346 Математика 27 В, {Сe1, Сe2, …, Сek} — множество всех циклов из базиса (1), содержащих f, Xf = {f, е1, е2, …, ek}. Тогда Xf == С*f.

►Согласно следствию 16.7 множество 092713 0950 27347 Математика 27
092713 0950 27348 Математика 27 f содержит ровно один коцикл. Очевидно, что Xf092713 0950 27349 Математика 27092713 0950 27350 Математика 27092713 0950 27351 Математика 27f. Поэтому достаточно доказать, что Xf является коциклом. По теореме 17.3 множество Xf— коцикл, если выполняются следующие условия:

1) |Хf 092713 0950 27352 Математика 27С| ≠ 1 для каждого цикла С;

2) Xf — минимальное непустое множество, удовлетворяющее условию 1).

Пусть С—цикл, D=С092713 0950 27353 Математика 27Xf. Так как (1) — базис пространства циклов, то С однозначно представляется в виде суммы циклов из (1):

С=Сei1+…+Сeit (4)

Если f 092713 0950 27354 Математика 27 С, то f принадлежит хотя бы одному слагаемому в (4), например, f
092713 0950 27355 Математика 27 Сei1. Тогда

ei1
092713 0950 27356 Математика 27Xf, {j,ei1} 092713 0950 27357 Математика 27 D, |D| > 1.

Пусть f092713 0950 27358 Математика 27С. Тогда либо f не входит ни в одно из слагаемых (4), либо f входит по меньшей мере в два из этих слагаемых. В первом случае D = Ø. Во втором пусть, например,

f
092713 0950 27359 Математика 27 Сei1, f
092713 0950 27360 Математика 27 Сei2

Тогда {ei1,ei2} 092713 0950 27361 Математика 27 D, |D| > 1. Тем самым доказано, что выполняется условие 1).

Пусть теперь Y 092713 0950 27362 Математика 27 Xf. Если f092713 0950 27363 Математика 27Y, то Y содержится в кобазе и потому конезависимо. Согласно лемме 17.4 существует такой цикл С, что |Y092713 0950 27364 Математика 27C|=1. Если же f
092713 0950 27365 Математика 27 Y, но, например, ei092713 0950 27366 Математика 27Y, то |Y092713 0950 27367 Математика 27Cei| == 1. Том самым доказано, что X, — коцикл. ◄

Ниже окажется полезным следующее

Утверждение 21.4. Если 092713 0950 27368 Математика 27 —изоморфизм бинарного матроида М1 на матроид М2, а (1)—базис циклов матроида М\ относительно базы В, то система

{
092713 0950 27369 Математика 27 (Ce) : e 092713 0950 27370 Математика 27 B}(5)

является базисом циклов матроида М2 относительно базы 092713 0950 27371 Математика 27 (В).

►По определению изоморфизма матроидов множество 092713 0950 27372 Математика 27 (D) является базой матроида М2. Для любого цикла С матроида М1 множество 092713 0950 27373 Математика 27 (С) — цикл матроида М2. Если теперь е — элемент матроида М1 и е092713 0950 27374 Математика 27В, то 092713 0950 27375 Математика 27 (е)
092713 0950 27376 Математика 27092713 0950 27377 Математика 27 (D).
Согласно следствию 17.7 множество S=092713 0950 27378 Математика 27(В)092713 0950 27379 Математика 27092713 0950 27380 Математика 27(е) содержит ровно один цикл. Этот цикл совпадает с 092713 0950 27381 Математика 27 (Сe), поскольку Сe092713 0950 27382 Математика 27Ве и, следовательно, 092713 0950 27383 Математика 27 (Сe)

092713 0950 27384 Математика 27 S. Итак, доказано, что (5)—базис циклов матроида М2 относительно базы 092713 0950 27385 Математика 27 (В). ◄

Теперь обратимся к графам. Графический и, следовательно, кографический матроиды бинарны, о чем свидетельствует

 

Теорема 21.5. Для любого непустого графа G матрица инцидентности I=I(G) является представлением циклического матроида М(G) над Z2.

►Для произвольного подмножества ребер Х обозначим через I(Х) подматрицу матрицы I, составленную из столбцов, соответствующих ребрам, входящим в X. Достаточно доказать, что rankI(X)<|Х| тогда и только тогда, когда подграф G(Х), порожденный множеством ребер X, содержит цикл. Но I (Х)— матрица инцидентности графа G(Х). При изменении нумерации вершин или ребер ранг этой матрицы, понятно, не изменится. Пусть граф G(Х) содержит цикл С. Перенумеруем вершины и ребра графа G(Х) так, чтобы элементы, входящие в цикл С, имели меньшие номера. Теперь матрица I(Х) принимает вид

I(X) =092713 0950 27386 Математика 27,

где А — матрица инцидентности графа С. В каждом столбце матрицы A ровно две единицы, поэтому сумма ее строк по модулю 2 равна нулевой строке. Следовательно, det A =0, и столбцы матрицы А, а вместе с ними и столбцы матрицы 1(Х) линейно зависимы.

Пусть теперь граф G(Х) — ациклический. Очевидно, что достаточно считать его дереном. Снова изменим нумерацию вершин и ребер графа G(Х). Одной из концевых вершин дерева G(Х) и инцидентному ей ребру припишем номер 1. Теперь обратимся к дереву G(Х)—1. Одной из его концевых вершин и инцидентному ей ребру припишем номер 2 и т. д. В этой нумерации матрица
инцидентности примет вид

I(X) = 092713 0950 27387 Математика 27 ;

ранг ее равен числу столбцов. ◄

Обратимся еще раз к представлениям циклического матроида М(G) над Z2. Пусть ЕG = Е и 092713 0950 27388 Математика 27: Е→Zn2 —представление. Поскольку длина цикла в графе не менее трех, то все двухэлементные множества ребер независимы. В этой ситуации, как отмечалось выше, представление 092713 0950 27389 Математика 27 индуцирует изоморфизм матроидов. Поэтому из предыдущей теоремы непосредственно вытекает

Следствие 21.6. Циклический матроид М(G) непустого графа G изоморфен векторному матроиду над Z2, порожденному столбцами матрицы инцидентности I(G).

К бинарному матроиду М(G) применима также теорема 21.1, т. е. верно

Следствие 21.7. Все циклы графа G, объединения циклов, не имеющих общих ребер, и пустое множество относительно сложения по модулю 2 и умножения на числа по формулам 1 • Х = X, 0·Х=0 составляют линейное пространство над Z2 — пространство циклов графа G, размерность которого равна циклическому рангу v(G).Аналогичное утверждение верно для разрезов.

Базисы циклов и коциклов матроида М(G) называются базисами циклов и, соответственно, разрезов графа G.

Следствие 21.8. Каждый цикл графа однозначно представляется в виде суммы по модулю 2 циклов, взятых из какого-либо фиксированного базиса циклов. Аналогичное утверждение верно для разрезов.

Следствие 21.9. Любой граф G содержит не более чем 2v(G) — 1 циклов.

Как правило, число циклоп в графе значительно меньше, чем число, указанное в предыдущем следствии. Однако приведенная оценка точна в том смысле, что существуют графы, число циклов в которых равно 2v(G) — 1.
Таковы, например, все леса и граф, изображенный на рис. 21.1.

Следствие 21.10. Любой граф имеет не болев чем 2v*(G) — 1 разрезов.

Следствие 21.11. Пусть G — граф, H — его остов, f092713 0950 27390 Математика 27 ЕН, [Се1, Ce2, …,Cek} — множество всех циклов, входящих в базис циклов относительно Н и

092713 0950 27391 Математика 27092713 0950 27392 Математика 27

 

Рис. 21.1 Рис. 21.2

 

 

содержащих f, Cf* = {f, e1, е2 …, еk}. Тогда { Cf* : f
092713 0950 27393 Математика 27 ЕН} — базис разрезов графа G относительно остова Н.

Рассмотрим примеры.

1. Пусть G—граф, изображенный па рис. 21.2. Множество ребер {1, 2, 6, 8} порождает в G остов. Базис циклон относительно этого остова: С3=G(2, 3, 8), С4=G(1, 2, 4), C5=G(1, 5, 6), С7=G(2, 1, 6, 7), С9=G(6, 1, 2, 8, 9). Каждый другой цикл однозначно разлагается в сумму каких-либо из этих пяти. Например,
G(3, 5, 9)=С3+С5+С9. Множество {С*1,С*2, С*6, С*8}, где C*1 ={1,4, 5, 7, 9}, С*2 = ={2, 3, 4, 7, 9}, С*6 = {6, 5, 7, 9}, С*8 == {8, 3, 9}, является базисом разрезов графа D.

2. Найдем базис циклов графа G, заданного своей матрицей инцидентности I. Пусть

 

I= 092713 0950 27394 Математика 27.

Этот граф изображен на рис. 21.3, однако при отыскании базиса циклов рисунок использоваться не будет.

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

1) Пусть А’—матрица, полученная из матрицы А в результате элементарных преобразований строк. Если какой-либо столбец матрицы А линейно выражается через другие ее столбцы, то точно такое же соотношение (с теми же коэффициентами и номерами столбцов) верно и для столбцов матрицы А’.

2) Всякую невырожденную матрицу с помощью элементарных преобразований строк можно превратить в единичную.

 

 

092713 0950 27395 Математика 27

 

Превратим базисную подматрицу матрицы I (т. е. подматрицу максимального порядка с отличным от пуля определителем) в единичную, после чего совсем просто будет найти в графе G остов и базис циклов. Прибавляя
(по модулю 2) поочередно ко второй строке первую, к третьей — вторую, к пятой — третью и четвертую, получим

092713 0950 27396 Математика 27

 

Итак, rank I == 4, первые четыре столбца составляют базу системы столбцов. Соответствующие им ребра е1, е2, e3, е4 порождают в графе G остов.

Далее к первой строке прибавляем третью и четвертую, ко второй — третью, к третьей — четвертую:

092713 0950 27397 Математика 27

Линейные соотношения между столбцами последней матрицы те же, что и между столбцами исходной матрицы I. Если Аk (k=092713 0950 27398 Математика 27)—столбцы матрицы I, то А5=А2+А4, А6 =А1+А3+А4, столбцы А2, А4, А3 линейно зависимы над Z2, причем это — единственная минимальная линейно зависимая система столбцов, содержащаяся в {А1, А2, А3, А4, А5). Аналогично {А1,A3, А4, А6) — единственная
минимальная линейно зависимая система столбцов, содержащаяся в {А1, А2, А3, А4, А6). Ребра графа G, соответствующие столбцам матрицы I, входящим в эти минимальные линейно зависимые системы, образуют в G простые циклы, составляющие базис системы циклов:

Сe5 = G (е2, e4, e5), Се6= G (е1, e3, e4, е6)

(см. рис. 21.3).

 

§ 22. Трансверсали

 

Пусть Е — конечное непустое множество, а S = (S1, S2, …, Sm) — m-членное семейство его подмножеств, т. е. последовательность длины т, составленная из непустых (не обязательно различных) подмножеств множества Е. Подмножество Т 092713 0950 27399 Математика 27 Е называется трансверсалью (или системой различных представителей) семейства S, если существует биективное отображение 092713 0950 27400 Математика 27: Т→{1,2,…
…,m}, при котором для каждого t092713 0950 27401 Математика 27Т выполняется условие t092713 0950 27402 Математика 27Sφ(t). Это означает, другими словами, что существует такая нумерация элементов множества T, при
которой t092713 0950 27403 Математика 27Si (i = 092713 0950 27404 Математика 27).

Подмножество Т 092713 0950 27405 Математика 27 Е называется частичной трансверсалью семейства S, если существует инъективное отображение 092713 0950 27406 Математика 27: T→{1,2,…,m}, при котором для каждого t
092713 0950 27407 Математика 27Т выполняется условие t
092713 0950 27408 Математика 27 Sφ(t). Тем самым, частичные трансверсали семейства S — это трансверсали его подсемейств.

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

Например, если есть четверо юношей x1, x2, x3, x4 и пять девушек у1, у2, у3, y4, y5, а отношение знакомства между ними задается таблицей 22.1, то возможно следующее решение: х1 женится на у4, х2—на у1, х3—на у3, х4—на у2. Если теперь Е={y1, у2, y3, y4, y5}, то рассмотренной таблице соответствует семейство подмножеств S = (S1, S2, S3, S4) множества E, где Si — множество девушек, с которыми знаком юноша хi, т. о. S1= {у1, у4, y5}, S2= {у1}, S3= {у2, у3, y4}, S4= {у2, у4}. Задача о свадьбах имеет решение, когда для соответствующего семейства подмножеств 8 существует трансверсаль.

Таблица 22.1

Юноша 

Девушки, с которыми знаком юноша 

х1

у1, у4, y5

х2

у1

х3

у2, у3, y4

х4

у2, у4

 

В нашей ситуации трансверсалью служит, например, множество {y1, у2, y3, y4}, при этом y4092713 0950 27409 Математика 27 S1, y1 092713 0950 27410 Математика 27S2, y3092713 0950 27411 Математика 27 S3, y2092713 0950 27412 Математика 27 S4.

Трансверсали семейства множеств может и не существовать. Пусть, например, S= (S1,S2, S3, S4), S1 ={1,2}, S1 ={1, 2, 3}, S3={2, 3}, S4={1, 3}. Тогда |092713 0950 27413 Математика 27Si| =3, а в трансверсали должно быть четыре элемента. Следовательно, трансверсали нет.

Задача о существовании трансверсали решена . Холлом.

Теорема Холла (1935г.). Пусть Е—непустое конечное множество, S=(S1,S2,S3,S4),—семейство его подмножеств. Для существования трансверсали семейства S необходимо и достаточно, чтобы для каждого k=092713 0950 27414 Математика 27
объединение Si1092713 0950 27415 Математика 27Si2092713 0950 27416 Математика 27….092713 0950 27417 Математика 27Sik, любых k подмножеств Si, содержало не менее k различных элементов.

Теорема Холла является отправным моментом теории
трансверсалей. Известно несколько доказательств этой теоремы. Ниже приводится доказательство более общей теоремы, принадлежащей Г. Гадо.

Часто возникает ситуация, когда вместе с семейством
подмножеств S на множестве Е определена структура матроида М, и нужно решить вопрос о существовании трансверсали семейства Ы, независимой относительно матроида М, т. е. являющейся независимым подмножеством элементов этого матроида. На этот вопрос отвечает следующая

Теорема Радо (1942 г.). Пусть М — матроид с множеством элементов Е, S=(S1,S2,…,Sm)— семейство непустых подмножеств множества Е. Для существования трансверсали семейства S, независимой относительно матроида М, необходимо и достаточно, чтобы для каждого k= 092713 0950 27418 Математика 27, т объединение любых подмножеств Si , имело ранг, не меньший чем k.

Теоремы Холла — частный случай теоремы Радо. Действительно, если М — свободный матроид, то ранг любого подмножества Х
092713 0950 27419 Математика 27 Е равен |Х|.

►Доказательство теоремы Радо. Необходимость условия теоремы очевидна; если существует независимая трансверсаль семейства S, то ее пересечение с объединением любых k подмножеств Si содержит k-элементное независимое подмножество. Следовательно, ранг этого объединения не менее Н.

Достаточность. Вначале докажем, что при выполнении условий теоремы ни одно из множеств Si не может содержать более одного такого элемента, удаление которого нарушает условие теоремы. Пусть, напротив, множество S1 содержит два таких элемента х и у. Это значит, что существуют такие множества индексов А и В в {2, …, m}, что

092713 0950 27420 Математика 27

где 092713 0950 27421 Математика 27 — ранговая функция матроида М. Положив

092713 0950 27422 Математика 27
092713 0950 27423 Математика 27

имеем


092713 0950 27424 Математика 27

(см. аксиому 092713 0950 27425 Математика 27.З). Но

092713 0950 27426 Математика 27

Поэтому

092713 0950 27427 Математика 27

В то же время по условию теоремы

092713 0950 27428 Математика 27

Итак, |А| + |В| ≥ |А092713 0950 27429 Математика 27В| + 1 + |А092713 0950 27430 Математика 27В|=|A| +|В|+1.

Последнее противоречие доказывает нужное утверждение.

Пусть теперь какое-либо из подмножеств Si содержит более одного элемента. Тогда из Si, можно удалить некоторый элемент, не нарушив справедливости условия теоремы. Итерируя этот процесс, придем к ситуации, в которой |Si|= 1 (i =
092713 0950 27431 Математика 27) и выполняются условия теоремы. По тогда вес Si, попарно различны и их объединение и есть нужная трансверсаль. ◄

Понятие трансверсали можно обобщить следующим образом. Пусть Е—коночное непустое множество, S= (S1, S2, . . ., Sm) — семейство его непустых подмножеств, (k1,k2,…,km)—последовательность целых положительных чисел. Семейство Р = (P1, Р2, …, Рm) подмножеств из Е назовем (k1, k2, …, km) — трансверсалью семейства S, если

1) Рi
092713 0950 27432 Математика 27 Si, i = 092713 0950 27433 Математика 27;

2) |Рi|=ki, i=
092713 0950 27434 Математика 27;

3) Рi
092713 0950 27435 Математика 27 Р1=Ø при i≠j.

Очевидно, что введенная выше трансверсаль является
(1, …, 1)-трансверсалью. Поэтому задача о свадьбах (о существовании трансверсали) естественным образом обобщается теперь в виде задачи о гаремах. Решение этой задачи, т. е. условия существования (k1,k2,…,km)- трансверсали, легко получить непосредственно из теоремы Холла. Заменим семейство S другим семейством

S`=(S11,S12,…,S1k1,S21,S22,…,S2k2,…,Sm1,Sm2,…,Smkm)

где Sij = Si(i=092713 0950 27436 Математика 27,j=
092713 0950 27437 Математика 27,t=
092713 0950 27438 Математика 27). Очевидно, что семейство S имеет (k1, k2, …, km)-трансверсаль тогда и только тогда, когда существует трансверсаль семейства
S’. Таким образом, верно

Следствие 22.1. Для существования (k1, k2, …, km) трансверсали семейства S=(S1,S2,…Sm) необходимо и достаточно, чтобы для любого I092713 0950 27439 Математика 27{1, 2, …, m} выполнялось неравенство

092713 0950 27440 Математика 27

Аналогично из теоремы Радо можно получить критерий существования независимой (k1, k2, …, km))-трансверсали.

Из теоремы Радо вытекает также следующий критерий существования независимой частичной трансверсали фиксированной мощности.

Следствие 22.2. В обозначениях теоремы Радо семейство S имеет независимую частичную трансверсаль мощности t≤m тогда и только тогда, когда для каждого k=092713 0950 27441 Математика 27, ранг объединения любых k подмножеств Si не меньше, чем k + t-m.

►Пусть D —такое множество, что |D|=m—t и D092713 0950 27442 Математика 27Е = Ø. Построим новый матроид М’ на множестве Е092713 0950 27443 Математика 27D, объявив его базами все подмножества В092713 0950 27444 Математика 27D, где
В — база матроида М (очевидно, что аксиомы баз действительно выполняются), и рассмотрим семейство

Т = (Т1,Т2,…,Тm), Ti = Si092713 0950 27445 Математика 27D, i = 092713 0950 27446 Математика 27

Очевидно, что исходное семейство S имеет независимую частичную трансверсаль мощности t тогда и только тогда, когда семейство Т имеет трансверсаль, независимую относительно матроида М’. Согласно предыдущему следствию, для существования такой трансверсали необходимо и достаточно, чтобы объединение любых k подмножеств Ti содержало независимое относительно матроида М’ подмножество мощности k. По последнее условно равносильно условию следствия. ◄

Взяв в качестве М свободный матроид, получим

Следствие 22.3. Семейство подмножеств S имеет частичную трансверсаль мощности t≤m тогда и только тогда, когда для каждого k = 092713 0950 27447 Математика 27 объединение любых k подмножеств Si, имеет мощность не меньше, чем k+t—m.

Произвольное семейство S=(S1, S2, …, Sm) непустых подмножеств множества Е определяет на Е структуру матроида, независимыми множествами которого являются частичные трансверсали этого семейства и пустое множество. Об этом свидетельствует следующая

Теорема 22.4 (Дж. Эдмопдс, Д. Фалкерсоп, 1965г.). Множество Ј, элементами которого служат все частичные трансверсали семейства подмножеств S и пустое множество, удовлетворяет аксиомам I.1 и I.2.

►В доказательстве нуждается только справедливость условия I.2. Произвольную частичную трансверсаль Х= {х1, х2, …, хk} семейства S, представляющую подсемейство (Si1,Si2, …, Sik), т. е. такую, что xр092713 0950 27448 Математика 27Sip, запишем в виде

{(x1, i1), (x2, i2), …, (xk,ik)}. (2)

Пусть

{(y1,j1), (y2, j2), …, (yt, j1)} (3)

— еще одна частичная трансверсаль и l >k. Нужно доказать существование среди y1,y2,…,yl такого у, что X092713 0950 27449 Математика 27y092713 0950 27450 Математика 27
J.

Если в (3) есть такая пара {у,j), что у не совпадает ни с одним из x в (2), а j — ни с одним из i, то, очевидно, что Х U у 092713 0950 27451 Математика 27J.

Пусть теперь и (3) лет такой пары. Но так как l > k, то существует j, пусть это j1, отличный от всех индексов i в (2). При зтом уi совпадает с каким-либо
из х, например, у1 = х1. Теперь можно написать

{(x1,j1), (x2,i2),…,(xk,ik)

т. е. трансверсаль Х представляет и подсемейство (Sj1, Sj2, …,Sjk), при этом х11. Среди индексов j2,…,jl существует индекс, отличный от каждого i2, …, ik, пусть
это будет j2. Тогда y2 совпадает с каким-либо из x2,…, хk, например, y2 = х2. Теперь имеем

{(x1, j1), (x2, j2), (x3, i3), …, (xk,ik)}.

x1=y1, x2=y2

Итерируя этот процесс, получим хi = уi, (i=092713 0950 27452 Математика 27) (с точностью до перенумерации элементов уi). Следовательно, Х 092713 0950 27453 Математика 27{y1,y2,…,yl}, Х092713 0950 27454 Математика 27уk+1
J.◄

Итак, (Е, J) — матроид с набором независимых множеств J. Этот матроид называется матроидом трансверсалей семейства S. Матроид, изоморфный матроиду трансверсалей какого-либо семейства подмножеств, называется
трансверсальным.

В важном частном случае, когда исходное семейство S является разбиением множества Е, т. е. 092713 0950 27455 Математика 27Si = Е, и подмножества Si, попарно но пересекаются, матроид трансверсалей семейства S называется матроидом разбиения S. Очевидно, что подмножество Х092713 0950 27456 Математика 27E независимо относительно матроида разбиения S тогда н только тогда, когда |X 092713 0950 27457 Математика 27 Si| ≤ (i = 092713 0950 27458 Математика 27).

 

§ 23. Жадный алгоритм

 

Рассмотрим следующую задачу дискретной оптимизации. Пусть Е—непустое конечное множество, w: Е → R+ — функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное
число w(е)—вес элемента е. Для Х092713 0950 27459 Математика 27Е вес w(Х) определим как сумму весов всех элементов множества X:

w(X) = 092713 0950 27460 Математика 27

Пусть, далее, J — некоторый набор подмножеств множества Е, т. е. J
092713 0950 27461 Математика 27 2E. Задача состоит в выборе в J подмножества максимального веса.

Оказывается, что в случае, когда J является набором независимых множеств матроида, эта оптимизационная задача решается с помощью следующего простого алгоритма.

Жадный (градиентный) алгоритм.

1-й шаг. Находим такой элемент е1092713 0950 27462 Математика 27 Е, что

092713 0950 27463 Математика 27

k-й шаг (k≥2). Находим такой элемент еk092713 0950 27464 Математика 27Е, что

092713 0950 27465 Математика 27

Если такого элемента нет, то конец.

Примером жадного алгоритма служит алгоритм Краскала нахождения остова максимального веса во взвешенном графе (см. § 15).

Очевидно, что выходом жадного алгоритма всегда является элемент множества J, максимальный относительно включения. Однако он может оказаться не максимального веса. Чтобы убедиться в этом, рассмотрим пример: E={1, 2, 3}, J={{1}{1, 2}, {2, 3}}, w(1)=3, w(2)=2, w(3)=4. Наш алгоритм найдет множество {1, 2}, хотя множество {2, 3} имеет больший вес.

Возникает вопрос: когда же можно гарантировать получение подмножества максимального носа, решая задачу с помощью жадного алгоритма? На этот вопрос отвечает следующая

Теорема 23.1. Если J—набор независимых множеств матроида М=(Е, J), элементам которого приписаны неотрицательные веса, то жадный алгоритм находит в J множество максимального веса.

►Очевидно, что жадный алгоритм строит базу; пусть
это база

Во={е1, е2, …, еρ), w(е1)≥ w(e2) ≥…≥w(еρ).

Остается показать, что вес базы Во максимален. Пусть это не так. Среди всех баз максимального веса выберем такую базу В, которая имеет наибольшее число общих элементов с Во. Так как В ≠ Во и |B| = |Bо|, то Во\В≠Ø. Выберем в Во\В элемент ei, с минимальным номером i. Множество В092713 0950 27466 Математика 27ei< содержит цикл С. Так как база матроида циклов не содержит, то существует е092713 0950 27467 Математика 27С\Во.
Пусть В’=(В\е)092713 0950 27468 Математика 27ei. Множество В’ не содержит циклов, поскольку С — единственный цикл в В092713 0950 27469 Математика 27ei (следствие 16.7). Кроме того, |В’|= |B|. Следовательно, В’ является базой. Далее имеем

В’092713 0950 27470 Математика 27Во=(В092713 0950 27471 Математика 27Во)
092713 0950 27472 Математика 27еi, |В’092713 0950 27473 Математика 27Во|>|В092713 0950 27474 Математика 27Во|.

Поэтому

w(В’)<w(В), (1)

иное противоречило бы выбору базы В.

С другой стороны, w(В’)= w(В)— w (е) + w (еi), поэтому из (1) вытекает, что w(е)> w(еi). Но последнее неравенство неверно, поскольку на i-м шаге алгоритм выбрал еi, а не е. Полученное противоречие доказывает теорему. ◄

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

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

Заметим, что приведенное здесь доказательство предыдущей теоремы буквально то же, что и доказательство теоремы 15.1, обосновывающей алгоритм Краскала.

Оказывается, верна теорема, в некотором смысле обратная предыдущей.

Теорема 23.2. Пусть F — набор подмножеств конечного множества E, обладающий тем свойством, что если Х092713 0950 27475 Математика 27F, Y092713 0950 27476 Математика 27X, то Y092713 0950 27477 Математика 27F. Тогда, если F не. является набором независимых множеств матроида, то применение к
F жадного алгоритма не гарантирует получения подмножества максимального веса.

►Пусть для набора F не выполняется аксиома I.2, т. е. в F есть такие Х={x1, х2, …, хk+1}, Y=={у1, у2, ……, уk}, что не существует xi
092713 0950 27478 Математика 27Х\уi, для которого Y092713 0950 27479 Математика 27 хi092713 0950 27480 Математика 27
F. Покажем, что в этом случае можно так подобрать, что жадный алгоритм построит множество не максимального веса.

Пусть w(уi)=1 (i=092713 0950 27481 Математика 27), w(xi)=t, если xi092713 0950 27482 Математика 27Х\Y,
где 0<t<1, w(e) =0, если е092713 0950 27483 Математика 27Е\(Х092713 0950 27484 Математика 27У). Тогда жадный алгоритм построит сперва множество Y. Так как отсутствует такой элемент xi, что Y092713 0950 27485 Математика 27xi092713 0950 27486 Математика 27F, то далее алгоритм выберет элементы из Е\(X092713 0950 27487 Математика 27У) и закончит работу, получив в результате множество Хо, вес которого равен весу множества Y.

Пусть |Х092713 0950 27488 Математика 27Y|=р. Тогда w(Х) =p-(k+1-р)t. Поэтому, учитывая, что w((Хо)=k, можно выбрать 0<t<1 таким, чтобы было w(Хо) < w (X). Тем самым жадный алгоритм не находит в F множества максимального веса. ◄

 

§ 24. Объединение и пересечение матроидов

 

Пусть М1 и М2 — два матроида на множестве элементов Е с наборами независимых множеств J1 и J2 соответственно. Положим

J ={Х092713 0950 27489 Математика 27Y: Х
092713 0950 27490 Математика 27
J1 , Y

092713 0950 27491 Математика 27 J2).

Как показывает прямая проверка, множество Y удовлетворяет аксиомам независимости. Следовательно, (Е, Y)—матроид, для которого Y служит набором независимых множеств. Этот матроид называется объединением матроидов М1 и М2 и обозначается через М1092713 0950 27492 Математика 27М2.

Очевидно, что операция объединения матроидов ассоциативна, и можно говорить об объединении нескольких матроидов.

Теорема 24.1. Пусть {Мi: i=092713 0950 27493 Математика 27} — семейство матроидов, определенных на одном и том же множестве Е, с ранговыми функциями ρi соответственно, k>1, М— объединение всех этих матроидов. Тогда ранговая функция ρ матроида М определяется для любого подмножества Х092713 0950 27494 Математика 27 Е равенством

ρ (X) = 092713 0950 27495 Математика 27{ ρ1 (A) + ρ2(A) + … + ρk (А) + |Х\А|}. (1)

Рассмотрим отдельно два случая.

1. ρ (Х}=|Х|. В этом случае ρ (А)=|А| для любого подмножества А 092713 0950 27496 Математика 27 X. Очевидно, что

ρ (A)≤ ρ1(A)+ ρ2(A)+…+ ρk(A),

поэтому
ρ1(А)+ ρ2(А)+…+ ρk(А)+|Х\А|≥ ρ (А)+|Х\А| = |A|+|Х\А|=|Х|= ρ (Х).

При A =Ø получаем

ρ1(А)+ ρ2(А)+…+ ρk(А)+|Х\А|=|Х|= ρ(Х).

Равенство (1) доказано.

2. ρ(Х)< |X|. Воспользуемся индукцией по k. Вначале пусть k=2. По определению р(Х)= |B|, где 5—максимальное независимое подмножество в X. Очевидно, что B=(B092713 0950 27497 Математика 27A)092713 0950 27498 Математика 27(B092713 0950 27499 Математика 27(Х\А)) для любого А092713 0950 27500 Математика 27Х. Так как

|B
092713 0950 27501 Математика 27A|≤ ρ(A)≤ ρ1(A)+ ρ2(A)

то для любого А 092713 0950 27502 Математика 27 Х

ρ (Х)=|В|=|B092713 0950 27503 Математика 27A|+|В092713 0950 27504 Математика 27 (Х\A)| ≤ ρ1(А)+ ρ2(A)+|Х\A|. (2)

Теперь получим нижнюю оценку для ρ(Х). Пусть М`2 — копия матроида M2, определенная на множестве Е’, имеющем пустое пересечение с Е. Более точно: Е = {е1, е2, . .., en}, Е’ == {е`1, е’2, …,e`n), Е092713 0950 27505 Математика 27Е’ =Ø, множество {e`i1,…,e`im} независимо относительно матроида М`2, тогда и только тогда, когда {ei1,…,eim} независимо относительно М2. Очевидно, что можно определить матроид на множестве Е 092713 0950 27506 Математика 27 Е’, объявив его независимыми множествами объединения Х092713 0950 27507 Математика 27Y, где Х092713 0950 27508 Математика 27Е независимо относительно матроида М1, Y092713 0950 27509 Математика 27Е’—относительно М`2. Обозначим этот матроид и его ранговую функцию через M1092713 0950 27510 Математика 27М`2 и ρ’ соответственно.

Пусть теперь Х — произвольное подмножество множества E. Положив Si={ei,e`i}, S=(Si: еi
092713 0950 27511 Математика 27 Х}, получим семейство S подмножеств множества Е092713 0950 27512 Математика 27Е’. Согласно следствию 22.2 для любого t≤|Х| частичная трансверсаль мощности I семейства S, независимая относительно матроида М1092713 0950 27513 Математика 27М`2 существует тогда и только тогда, когда для любых r подмножеств S, выполняется условие

ρ'(Si1
092713 0950 27514 Математика 27092713 0950 27515 Математика 27 Si1)≥г+t–|Х|, r= 092713 0950 27516 Математика 27. (3)

Объединение множеств, заключенное в скобки, представим в виде А
092713 0950 27517 Математика 27 А’, где А 092713 0950 27518 Математика 27 Е, А’ 092713 0950 27519 Математика 27 E`. Ясно, что

ρ’ (A
092713 0950 27520 Математика 27 A`)= ρ1(A) + ρ2(A), |X|-r=|x\A|

поэтому условие (3) можпо переписать так:

ρ1(A) + ρ2(A)≥t –|X\A|, (4)

С другой стороны, легко понять, что следующие два утверждения равносильны:

1) существует частичная трансверсаль мощности t семейства подмножеств S, независимая относительно матроида М1 и M`2;

2) ρ(Х)≥t.

В самом деле, пусть Т — такая трансверсаль и пусть, для определенности,

Т = {е1, .. ., ер, е`р+1, .. ., е`t}, ei 092713 0950 27521 Математика 27 Е, е`092713 0950 27522 Математика 27Е’. (5)

Тогда

1,…,ер}
092713 0950 27523 Математика 27
J1), {е`p+1,…,е`t}

092713 0950 27524 Математика 27
J(М`2),

p+1,…,еt}
092713 0950 27525 Математика 27
J2).

и, следовательно,

1,…,ер, еp+1,…,еt }092713 0950 27526 Математика 27J(M1092713 0950 27527 Математика 27M2) (6)

т. е. выполняется условие (2).

Обратно, если выполняются условия (2) и (6), причем

{{е1,…,ер}
092713 0950 27528 Математика 27
J1),

p+1,…,еt}
092713 0950 27529 Математика 27
J2).

то множество T, определяемое условиями (5), является частичной трансверсалью мощности t семейства подмножеств S, независимой относительно матроида М1092713 0950 27530 Математика 27М`2.

Равносильность утверждений 1) и 2) доказана.

Из предыдущего вытекает, что ρ(Х)≥t тогда и только тогда, когда для любого подмножества A множества Х верно неравенство (4). Следовательно, при t=ρ(Х)+1 в Х существует такое подмножество Aо, которое не удовлетворяет неравенству (4), т. о.

ρ1(Aо)+ρ2(Aо)< ρ(Х)+1 — |Х\Aо|,

откуда

ρ(Х)≥ ρ1(Aо)+ ρ2(Aо)+ |Х\Aо|. (7)

Из (7) и (2) вытекает

ρ(Х)= ρ1(Aо)+ ρ2(Aо)+ |Х\Aо|.

Последнее равенство в сочетании с неравенством (2) приводит к формуле

ρ(Х)=
092713 0950 27531 Математика 27{ρ1(A)+ ρ2(A)+ |Х\A|}.

Для k = 2 теорема доказана.

Пусть теперь k > 2 и теорема верна для объединения менее чем k матроидов. Если ρ ‘ — ранговая функция объединения М1092713 0950 27532 Математика 27М2092713 0950 27533 Математика 27….092713 0950 27534 Математика 27Mk-1, то в силу доказанного выше и индуктивного предположения имеем

ρ(Х)=
092713 0950 27535 Математика 27{ρ`(B)+ ρk(B)+ |Х\B|}=
092713 0950 27536 Математика 27{ 092713 0950 27537 Математика 27{ ρ1(A)+…+ ρk-1(A)+ |B\A|}+

k(B)+|X\B|}}

Поскольку А092713 0950 27538 Математика 27В и |В\A| + |Х\В| = |Х\A|, то рассматриваемый минимум достигается лишь при A = В, и потому получаем

ρ(Х)=
092713 0950 27539 Математика 27{ ρ1(A)+…+ ρk(A)+ |X\A|}◄

Ниже через (Е, ρ) обозначается матроид с множеством элементов Е и ранговой функцией ρ.

Следствие 24.2. Матроид (E, ρ) имеет l попарно непересекающихся баз тогда и только тогда, когда для любого A 092713 0950 27540 Математика 27 Е верно неравенство

lρ(А)+|
092713 0950 27541 Математика 27 |>lρ(Е).
(8)

►Пусть lМ — объединение l экземпляров матроида M, ρ‘ — ранговая функция этого объединения. Очевидно, что ρ‘ (lМ)≤(М) и М имеет l попарно непересекающихся баз только при условии ρ‘(1М) =(М). Теперь
нужное утверждение непосредственно вытекает из предыдущей теоремы. ◄

Следствие 24.3. Для представимости множества Е в виде объединения не более чем l независимых подмножеств матроида М=(Е,ρ) необходимо и достаточно, что-бы любое подмножество A
092713 0950 27542 Математика 27Е удовлетворяло условию

|А|≤ ρl(A). (9)

►Множество Е представимо в виде указанного объединения только тогда, когда ρ‘(lМ)=|Е|. Согласно теореме 24.1 последнее равносильно неравенству |Е|≤ρl(A)|
092713 0950 27543 Математика 27|, в свою очередь равносильному неравенству (9).◄

Применим два предыдущих следствия к циклическому матроиду М(G) непустого графа G. В рассматриваемой ситуации независимыми множествами матроида служат множества ребер ациклических подграфов. Объединим
каждый такой подграф со всеми не входящими в него вершинами G и будем считать подграф остовным. Для любого остовного подграфа Н верно равенство ρ (М(H))=n(G)—k(H). Если H—остовный подграф с множеством ребер А, то неравенства (8) и (9) превращаются в неравенства

m(G)-m(H)≥l(k(H) –k(G)) (10)

и, соответственно,

m(H)≤ l(n(G)-k(H)) (11)

Поэтому верны следующие два утверждения.

Следствие 24.4. В непустом графе G имеется l
реберно непересекающихся остовов тогда и только тогда, когда любой его остовный подграф удовлетворяет неравенству (10).

Следствие 24.5. Для того чтобы, непустой граф G был объединением не более чем l своих остовов, не имеющих общих ребер, необходимо и достаточно выполнение условия (11) для любого его остова Н.

Аналогично введенному выше понятию объединения матроидов можно ввести понятие их пересечения. Пусть Мj=(Е, Jj) (j=092713 0950 27544 Математика 27)—k матроидов на множестве элементов Е с наборами независимых множеств Jj. Пару
М=(Е, J), где J=
092713 0950 27545 Математика 27 J
j назовем пересечением матроидов Мj (j =

092713 0950 27546 Математика 27) и обозначим М =
092713 0950 27547 Математика 27Мj

Разумеется, пересечение матроидов также может оказаться матроидом. Например, пересечение тривиального матроида и любого матроида с тем же множеством элементов есть тривиальный матроид. Но, как правило, пересечение матроидов М не является матроидом с набором независимых множеств J, поскольку J может не удовлетворять аксиоме независимости 1.2. Например, пересечение двух матроидов М1=(Е,J1) и М2=(Е,J2), где Е = {1, 2, 3, 4), J1= {Ø, {1}, {2}, {3}, {4}, {1, 3), {1, 4}, {2, 3}, {2, 4}}, J2={{Ø, {1}, {2}, {3}, {4}, {1, 2}, {1, 4},
{2, 3}, {3, 4}}, не есть матроид, так как множество J1

092713 0950 27548 Математика 27J2={Ø, {1}, {2}, {3), {4}, {1, 4}, {2, 3}} не удовлетворяет условию I.2.

В § 28 читатель столкнется со следующей задачей:

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

Пусть, например, заданы два графа G и H, причем |ЕG| = |ЕН| = m. Пусть ребра этих графов занумерованы с помощью одних и тех же моток: ЕG=ЕH={1, 2, ……, m}. Очевидно, что задача нахождения в Е наибольшего по числу элементов подмножества, не содержащего циклов ни первого, ни второго графов, и есть задача о пересечении двух графических матроидов М(G) и М(Н).

Задача о пересечении лишь двух матроидов стоит особняком: она эффективно решается методом чередующихся последовательностей (см., например, [25]). Идея этого метода демонстрируется и § 77.

При k > 2 задача о пересечении k матроидов становится очень трудоемкой. Даже для решения со простейшего варианта — задачи о пересечении трех матроидов разбиений — не найдено, и скорой всего по существует, эффективных алгоритмов.

УПРАЖНЕНИЯ

1. Пусть М – матроид порядка га. Покажите, что число его баз
не превосходит 092713 0950 27549 Математика 27, а число его циклов не превосходит 092713 0950 27550 Математика 27

2. Пусть М = (Е, J) — матроид с набором независимых множеств J, Ø≠A092713 0950 27551 Математика 27E. Пусть, далее, J= {X
092713 0950 27552 Математика 27J: Х 092713 0950 27553 Математика 27 А = Ø}. Докажите, что М’ = (Е, J) — матроид с набором независимых множеств J ». Матроид М« называется сужением матроида М посредством А.

3. Пусть в обозначениях предыдущего упражнения J» = {X
092713 0950 27554 Математика 27 A: Х
092713 0950 27555 Математика 27 У}. Докажите, что М» = (Е, J«‘) —матроид с набором независимых множеств J«. Матроид М» называется ограничением матроида, М на А.

4. Пусть Е—непустое конечное множество, k≤|Е|. Докажите, что множество ß всех k-элементных подмножеств множества Е удовлетворяет аксиомам баз и, следовательно, (E, ß) – матроид. Его называют однородным матроидом ранга k.

5. Пусть G — ориентированный граф, и пусть Е и Y — два непересекающихся подмножества его вершин. Подмножество А092713 0950 27556 Математика 27Е
называется независимым, если существует |A| вершина непересекающихся простых орцепей из А в Y. Докажите, что эти независимые множества задают некоторый матроид.

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

ρ *(A) = |A|+р(092713 0950 27557 Математика 27)-ρ (М),

где ρ * — коранговая функция матроида М.

7. Для каких k и n существуют однородные матроиды порядка n и ранга k, являющиеся матроидами циклов некоторого графа?

8. Исследуйте циклические матроиды М{К5} и M/K3,3. Докажите, что они не являются кографическими.

9. Покажите, что с точностью до изоморфизма число матроидов порядка n не превосходит 22n .

10. Охарактеризуйте графы, матроиды циклов и разрезов которых изоморфны.

11. Покажите, что с точностью до изоморфизма существует
ровно 4 матроида порядка 2 и 8 матроидов порядка 3. Сколько среди них представимых над каким-либо полем?

12. Пусть М1 и М2 — матроиды на множестве Е с ранговыми
функциями ρ1 и ρ2. Докажите, что М1 и М2, имеют общее независимое множество мощности А тогда и только тогда, когда ρ1(A) + ρ2 (092713 0950 27558 Математика 27)≥k для любого A 092713 0950 27559 Математика 27 Е.

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

14. Докажите, что трансверсальные матроиды и только они представимы в виде объединений матроидов ранга 1.

15. Докажите, что циклический матроид М(К4) не является
трансверсальным.

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

17. Докажите, что с точностью до изоморфизма число трансверсальных матроидов порядка n по превосходит 22n.

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

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

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

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

092713 0950 27560 Математика 27

где ß— множество баз матроида М, 092713 0950 27561 Математика 27 * — множество коциклов матроида М.

<

Комментирование закрыто.

WordPress: 22.95MB | MySQL:124 | 3,225sec