В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 14
Текст из файла (страница 14)
е. минимальное относительно включения зависимое множество. Применяя уже доказаььпое утверждение 1), заключаем, что ьр(Х)— минимальное относительно включения зависимое множество матроида Мз. 3) Положим Х =Е1Х. Мпояьество Х вЂ” кобаза матроида М~ тогда и только тогда, когда Х вЂ” база ЛХь, т. е. когда 9ь(Х) — база матроида ЛХм Последнее равносильно тому, что с~(Х) — кобаза в Мз.
Но ьр(Х)= ьр(Х). 4) Коциклы матрояда — это минимальные козависимые множества. Подмножество Х элементов матроида М~ козависимо тогда и только тогда, когда оно пересекается 1Л Рве. 19.1 с любой базой этого матроида. Последнее равносильно тому, что множество ьр(Х) пересекается с любой базой матроида Мм т.
е. ф(Х) козависимо в матроиде Мз Из предыдущего утверждения непосредственно вытекает С л е д с т в и е 19.2. Если матроиды изоморфны, то двойственььые матроиды также игоморфньь, т. е. если ьр: Мь — М« — изоморфигм льатроидов, то ьр: Мь -~ЛХ» такиее является изоморфизльом матроидов. Итак, изоморфные матроиды «одинаково устроены», что дает основание пх не различать. Поэтому любой матроид, нзоморфпый векторному, такяье назовем векторным.
Матроид назовем графическим, если он изоморфеп матронду циклов М(6) некоторого графа 6, и кографическиль, если оп изоморфен матроиду разрезов М*(6). На рпс. 19.1 изображены два графа 6 и Н, циклические матронды которых изоморфпы. й 20. Представление матроида Стремлессссе попить строение тех матроидов, которые близки к векторным, т. е. если и пе являются векторны- мн, то отличаются от последних лишь незначительно, приводит к понятию представления матроида, в опреде- ленном смысле близкому к понятию изоморфизма. Пусть М вЂ” матроид с множеством элементов Е, Р"— линейное пространство столбцов высоты и над полем Р. Отображение ср: Е- Р называется представлением мат- роида М над полем Р, если опо удовлетворяет следующе- му условию: для любого подмножества Х=(ес, ег, ..., е,1 множества Е система векторов ср(ес), ср(ег), ...
..., ср(е„) линейно независима над полем Р тогда и толь- ко тогда, когда Х является независимым мссожеством матроида М. Пусть ср: à — Р" — продставлевие матронда М, Е = (сс, ег, ..., е,„1. Построим пХ т-матрссцу ср(Е) =- [ср(ес) ср(ег) . ср(е ) [, столбцами которой являются образы элементов матрои- да ЛХ в представлении ср. Эта матрица такнсе называется представленссем лсатроида ЛХ. Утверждение 20.1. Пусть М' — лсатроид с мно- жестволс глелсе>стев Е = (еп ег, ..., е 1, Л вЂ” произвольная пХ т-матрица нвд полем Р. Для того чтобы лсатрица А была представлением матроида М, необходилсо и доста- точно вьспг осенив следусощих двух условий: 1) гап!сЛ = р(ЛХ); 2) система л>обых р = р(ЛХ) столбцов матрицьс Л с но- г>врал>и сс, 1ь ..., с', линейно независилса тогда и только тогда, когда лсссогсгество [ес, вс,..., в; [ является базой с' с' ' ' ' 'Р лсатроида ЛХ.
1> Очевидно, что .1 = ср(Е) удовлетворяет условиям 1) и 2). С другой стороны, пусть пХт-матрссца Л удов- летворяет этим условиям и пусть Ас, Аг, ..., А — ее столбцы. То;да, положив ср(ес)=Аь получим представ- ление ср: Г - Р" матроида М. <1 Матропд называется првдставимылс над полем Г, если оп имеет представление пад Р. Как подтверждают сле- дующие примеры, одни матронды представимы над лю- бым полем, другие — пе пад любым. Пусть М вЂ” матроид с множеством элементов Е = (1, 2, 31, баззмн которого служат все двухэлементпые под- мноясества ьс>со>кества Е. Очевидно, что этот матроид 75 представим пад произвольным полем, поскольку матрица ~( о (~ служит представлением матроида М. С другой стороны, возьмем в качестве М матроид с множеством элементов Е= (1, 2, 3, 4), базами которого, как и выше, служат все двухэлемептпые подмножества множества Е.
Пусть матрица А является представлением этого матроида иад полем Р из двух элементов. Тогда гапкА = 2 и, следовательно, столбцы атой матрицы принадлея;ат двумерному линейному прострапству пад Р. Двумерное ликейпое пространство пад полем из двух элементов — это четырехэлемептпое множество (а, Ь, а+ Ь, О). Следовательно, столбцами матрицы А являются а, Ь, а+ Ь, О. Но поскольку любое двухэлементкое подмножество мпожества Е является базой матроида М, то любые два столбца матрицы А должны быть линейно независимы. Полученное противоречие доказывает, что матроид М не представим лад полем из двух элементов.
Если же Р— произвольпое поле, содержащее более двух элемевтов, то, наприьиер, матрица ЬяЕ, Ь~О, ЬФ1, является представлением матроида М яад Е Итак, рассматриваемый матроид представим над любым полем, кроме поля из двух элемептов. Очевидно, что свободный матроид представим кад любым полем — его представлением служит, например, единичвая матрица. Двойствеипый ему тривиальный матроид также представим, его представление — нулевая матрица. Заметим, что существуют матроиды, пе представимые ни пад каким почем. Из определения представлепия вытекает, что око действует инъективпо на каждом пезависимом множестве элементов матроида.
Однако в целом опо может оказаться и не ипъективпым. рассмотрим, например, матроид М=(Е, Я) с множеством элементов Е=(1, 2, 3, 4, 5) и множеством баз Я=((З, 4), (3, 5), (4, 5)). Его циклами служат множества (1), (2) и (3, 4, 5). Положив получим представление ср матроида М пад произвольным полем. Это представление пе является инъективным. Очевидно, что рассматриваемый матроид не имеет инъектинных представлений ни над каким полем, поскольку гр(1)= ~у(2)= О для любого представления ~р этого матроида. Легко понлть, что матроид, для которого существует инъективное представление, является векторным. В самом деле, для произвольного представления ~р некоторого матроида М = (Е, Я) рассмотрим множество столбцов (ср(е): еж Е).
Это множество порохгдает векторный матроид, который обозначим через ср(М). Коли отображение ~р илъективно, то оно естественно индуцирует изоморфизм ср' матроидов М и ср(М): ~р'(е)=~у(е) для любого элемента е матроида М. Итак, верно Утверждение 20.2, Если представление ср матроида М инъективно, то М си ср(М), С другой стороны, пусть Ь вЂ” п-мерное линейное пространство над произвольным полем Г, Е ж Š— конечное непустое подмножество, М вЂ” векторный матроид, порожденный множеством векторов Е. Зафиксируем в пространстве Е произвольный базис.
Поставив в соответствие каядому вектору из Е его координатный столбец в отмеченном базисе, получим представление Š— Г матроида М, являющееся инъективным. Итак, инъективные представления существуют у всех векторных матроидов и только у них. Теор ем а 20 З. Если матроид представим над полем Г, то двойственный ему матроид также представим над Г. > Для свободного и тривиального матроидов утверждение теоремы очевидно. Пусть М вЂ” нетривиальный матроид, не являющийся свободным, р = р (М), и Х т-матрица А — представление яад полем Г матроида М.
Тогда гал)с А = р, 0 ( р ( т. рассмотрим однородную систему АХ=О линейных уравнений с матрицей А (здесь Х вЂ” столбец неизвестных хь хю ..., х, Π— нулевой столбец высоты и). Пусть У вЂ” множество всех столбцов из Г'", являющихся решениями системы ($). Как известно из алгебры, У вЂ” надпространство пространства Г" размерности т — р, Выберем какой-либо базис У„Уг, ..., У в (2) подпространства У и составим из столбцов (2) т Х Х(пз — р)-матрицу В=[У~ Уз ... У,). Теперь докажем, что транспонированная матрица Вт является представлением матроида М*, для чего используем утверждение 20.1.
Имеем гапк В' = гап)с В = т — р = р (М*) . Далее вспомним, что базами матроида Ма являются дополнения до баэ матроида М. Поэтому достаточно установить следующее: система каких-либо р столбцов матрицы А линейно независима тогда и только тогда, когда линейно независима дополняющая система т — р столбцов матрицы В~ (или строк матрицы В). Слово «дополняющая» означает, что номера столбцов второй системы отличны от номеров столбцов первой. Выделим какую-либо систему р столбцов матрицы А.
Пусть, для определенности, это первые р столбцов, и пусть С вЂ” подматрица в А, составленная из взятых столбцов. Теперь рассмотрим однородную систему линейных уравнений (3)' с матрицей С (7 — столбец неизвестных хь хз, ..., г,). Если столбцы матрицы С линейно зависимы, то система (3) имеет ненулевое решение Я. Рассмотрим столбец высоты т, полученпьш добавлением пз — р нулей к столбцу Е. Очевидно, что С вЂ” решение системы (1), т.
е. Уш ~н У. Поскольку (2) — базис ярострапства У, то С = и! У! + пз ~ 2 +... + сз «-рУ -р. Введем столбцы Ф Ум Уз~ ..ю Уе3-е (5) высоты т — р, отбросив из каждого столбца (2)' первые р координат, н рассмотрим матрицу В = ~У, Уз ... У,з р], столбцами которой являются векторы (5). Это квадратная матрица, строки которой суть последние 73 т — р строк матрицы В. Из равенства (4) следует / а>Уг + азУ, + ... + а,„рУ . о = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
