В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 16
Текст из файла (страница 16)
11о 1(Х) — матрица ипцидептности графа С(Х). При изменении нумерации вершин илп ребер ранг этой матрицы, понятно, пе изменится. Пусть граф С(Х) содергкит цикл С. Перенумеруем вершины и ребра графа 6(Х) так, чтобы элементы, входящие в цикл С, имели меньшие номера. Теперь матрица 1(Х) принимает вид где А — матрица ипцидентностн графа С. В каждом столбце матрицы А ровно две единицы, поэтому сумма ее строк по модулю 2 равна пулевой строке.
Следовательно, дегА = О, и столбцы матрицы А, а вместе с ними и столбцы матрицы 1(Х) линейно зависимы. бв 83 Пусть теперь граф С(Х) — ациклический. Очевидно, что достаточно считать его деревом. Снова изменим нумерацию вершин и ребер графа С(Х). Одной из концевых вершин дерева С(Х) и инцидентному ей ребру припишем номер 1. Теперь обратимся к дереву С(Х) — 1. Одной из его концевых вершин и инцидентному ей ребру припишем номер 2 и т. д, В этой нумерации матрица ипцидептности примет вид — 1О ...
О— * 1 ... О ранг ее равен числу столбцов. 4 Обратимся еще раз к представлениям циклического матроида М(С) над Хг. Пусть ЕС = Е и ~р: Š— «е.г'— представлепие. Поскольку длина цикла в графе не мепое трех, то все двухэлементные множества ребер независимы. В этой ситуации, как отмечалось выше, представление ц индуцирует изоморфизм матроидов. Поэтому из предыдущей теоремы непосредственно вытекает Следствие 21.6. Циклический матроид М(С) не- пустого графа С изоморфен векторному матроиду над Хг, порожденному столбцами матрицы инцидентности У(С).
К бинарному матроиду М(С) применима также теорема 21.1, т. е. верно С л е д с т в и е 21Л. Все циклы графа С, обьединения циклов, не имеющих общих ребер, и пустое множество относительно сложения по модулю 2 и умножения на числа по формулам 1 Х = Х, 0 Х = ~ составляют линейное пространство над ег — пространство циклов графа С, размерность которого равна циклическому рангу т(С), Аналоюсчное утверждение верно для разрезов. Базисы циклов и коциклов матроида М(С) называются базисами циклов и, соответственно, разрезов графа С. С л е д с т в н е 21.8.
Кахдый цикл графа однозначно представляется в виде гул~ ы по модулю 2 циклов, взятых из какого-либо фиксированного базиса циклов. Аналогичное утверждение верно для р зрезов. Следствие 21.9. Любой граф С содержит не более чем 2сю — 1 циклов, Как правило. число циклов в графе значительно меньше, чем число, указанное в предыдущем следствии. Од- пако приведенная оценка точна в том смысле, что существуют графы, число циклов в которых равно 2ью — 1.
Таковы, например, все леса и граф, изображенный на рис, 21.1. Следствие 21.10. Любой граф имеет не более чем 2~*1о1 — 1 разрезов. Следствие 21.11. Пусть С вЂ” граф, Н вЂ” его остов, 1е= ЬН, (Сбд С,,, ..., С,„) — множество всех циклов, 1 Рис. 21.2 Рис. 211 входящих в базис циклов относительно Н и содержащих 1', Сг = (1, е„е„..., е„). Тогда (Сг . ( ен ЕН) — базис разрезов графа С относительно остова Н. Рассмотрим примеры. 1. Пусть С вЂ” граф, изображенный на рис. 21.2. Множество ребер (1, 2, 6, 8) порождает в С остов.
Базис циклов относительно этого остова: Сг = С(2, 3, 8), С4 = =С(1, 2, 4), Сг=С(1, 5, 6), Ст=С(2, 1, 6, 7), Сг= =С(6, 1, 2, 8, 9). Каждый другой цикл однозначно разлагается в сумму каких-либо из этих пяти. Например, С(3, 5, 9) = Сз+ Сз+ Сг. Множество (С,, С."„Сг, С,), где С~=(1 45 7~9) Сг=(2 3*4,7 9) Св=(6~5~7~9) С„= (8, 3, 9), является базисом разрезов графа С. 2. Найдем базис циклов графа С, заданного своей матрицей ипцидентности Е Пусть 101000 110100 010010 000111 001001 Этот граф изображен на рис. 21.3, однако при отыскании базиса циклов рисунок использоваться не будет.
В силу следствия 21.6 базы системы столбцов этой матрицы соответствуют ребрам остовов, а минимальные линейно зависимые системы столбцов — простым циклам. Используем два следующих утверждении из линейной алгебры: М) Пусть А — матрица, полученная из матрицы Л в результате элементарных преобразований строк. Если какой-либо столбец матрицы Л линейно выражается через ез другие ее столбцы, то точно такое же 5 1 соотношение (с теми же козффициегы тами и номерами столбцов) верно и е, для столбцов матрицы А'.
2) Всякую невырожденную матрицу с помощью элементарных преобра- 2 зований строк можно превратить в единичную. 3 ег Превратим базисную подматрицу матрицы 1 (т. е. подматрицу максимального порядка с отличным от пуля определителем) в единичную, после чего совсем просто будет найти в графе 6 остов и базис циклов, 11рибавлия (по модулю 2) поочередно ко второй строке первую, к третьей — вторую, к пятой — третью и четвертуго, по- лучим 5 Рлс. 21.3 101000 101000 101000 110100 011100 011100 010010 -~ 010010 -~ 001110 000111 000111 000111 001001 001001 001001 101000 011100 -+ 001110 000111 000000 Итак, гапк 1 = 4, первые четыре столбца составляют базу системы столбцов.
Соответствующие им ребра еи ем ез, ез порождагот в графе 6 остов. Далее к первоп строке прибавляем третью и четвертую, ко второй — третью, к третьей — четвертую: 101000 011100 001110 000111 100001 010010 001001 000111 Липейные соотношения между столбцами последней матрицы те же, что и между столбцами исходной матрицы Е Если А, (й = 1, 6) — столбцы матрицы 1, то Лз = Аз+ Аи Аз=А~+Аз+Ае столбцы Аю Аэ, Лз линейно зависимы пад Хм причем это — едипственная минимальная линейно зависимая система столбцов, содержащаяся э (Аь Ап Лз Ап Аз).
Аналогично (Аь Аз, Ап Ав) — единственная мипималы1ая линейно зависимая система столбцов, содержащаяся в (Аь Аз, Аз, Ап Аз). Ребра графа С, соответствующие столбцам матрицы 1, входящим в эти минимальные линейно зависимые системы, образуют в 6 простые циклы, составляющие базис системы циклов: С, = 6(ее, ею е,), С, = 6(е„ез, ею ев) (см. рис.
21.3). 5 22. Трансверсали Пусть Š— конечное непустое множество, а Я = =(Ян Яю..., Я ) — т-членное семейство его подмножеств, т. е. последовательность длины лт, составленная иэ пепустых (не обязательно различных) подмножеств множества Е. Подмножество Т»Е называется трансверсалыо (или системой различных представителей) семейства Я, если существует биективное отображение ф: Т вЂ” (1, 2,... ..., т), при котором для каждого 1» Т выполняется условие 1»Я„н. Это означает, другими словами, что существует такая нумерация элементов множества Т, при которой й» Я~ (1 = 1, т) . Подмножество Т»Е называется частичной трансверсалью семейства Я, если существует инъективное отображение ф: Т- (1, 2, ..., и), при котором для каждого 1» Т выполняется условие 1» Я,иэ Тем самым, частичные трансверсали семейства Я вЂ” это трапсверсали его подсемейств.
Вопрос о существовании трансверсали часто возникает на практике. В шуточной форме его можно сформулировать как следующую задачу о свадьбах: известно некоторое множество юношей, каждый из которых зпаком с несколькими девушками. При каких условиях можно женить юношей так, чтобы каждый из пих жепилси на знакомой ему девушке? Например, если есть четверо юношей хь хп хз, х4 и пять девушек уь ум ум у4, уы а отношение знакомства между ними задается таблицей 22.1, то возможно сле- 87 дующее репуепне: х1 женится на уш хз — на уц хз — на уз, хл — на уз. Если теперь Е = (уц уз, уз, уо уз), то рассмотренной таблице соответствует семейство подмножеств Я =фи Ез, Кз, Ьо) множества Е, где Яс — мно",лестно девушек, с которыми знаком юноша х„т.
е. Я~ = (уь уо уз), Бз = (у~), аз = (ум уз, у4), 54 = (уз, уо). Задача о свадьбах имеет решение, когда для соответствующего семейстТаблица 223 Девушки, с которнин знаком юноша Юноша Уз У4 Уз Ус Уш Уз Уз Уз, Уя хз ва подмножеств Я существует трансверсаль. В нашей ситуации трансверсалью служит, например, мноязество (У!~ Уз Уз У4) при этом У4 Е! > У! юзг Уз ~ оз~ Уз ю4 Трансверсали семейства множеств может и не существовать. Пусть, например, Я =(Яц Яз, Яз, Яо), Я1 = (1, 2), Яз=(1, 2, 3), Яз=(2, 3), Ял =(1, 3).
Тогда () Яз = 3, а в трансверсали должно быть четыре элемента. Следовательно, трансверсали нет. Задача о существовании трансверсали решена Ф. Холлом. Теорема Холла (1935 г.). Пусть Š— непустое конечное лтожеетво, Я=(Яц Яз, ..., Я ) — семейство его подмножеств. Для существования траневереали семейства Я необходимо и достаточно, чтобьз для каждого й = 1, т объединение Яз () Я;, () ... () Я;з любьзх й подмножеств Ь'; содержало не менее й различных элементов. Теорема Холла является отправным моментом теории трансверсалей.
Известно несколько доказательств атой теоремы. Ниже приводится доказательство более общей теоремы, принадлежащей Р. Радо. Часто возникает ситуация, когда вместе с семейством подмножеств Я па множестве Е определена структура матроида М, и нужно решить вопрос о существовании трапсверсалн семейства Я, независимой относительно матроида М, т. е. являющейся независимым подмножеством элементов этого матроида. На этот вопрос отвечает сле- дующая Теорема Радо (1942 г.). Пусть М вЂ” матроид с множеством элементов Е, Я =(Я1, Ям ..., Я ) — семейство непустых подмножеств множества Е, Для существования трансверсали селгейства Я, независимой относительно мат- роида М, необходимо и достаточно, чтобы. для налсдого Й=.1, т объединение любых й подмножеств Я, имело ранг, не меньший мель й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
