Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 32
Текст из файла (страница 32)
Множество векторов тогда и только тогда является базисом векторного пространства, когда всякий элемент этого О 1 1 О О О 1 О О О О 1 о о О 1 1 1 1 О 1 1 1 О О 1 О О О 1 1 О 1 1 1 1 1 1 О 1 1 1 1 О О 1 1 1 1 О 1 О 1 1 О 1 О О О Вт Яз 72з Ве ' Вз нв 71т С(0) = В качестве базисной системы циклов можно взять циклы В1, Ва, Вз. Можно проверить, что все остальные пиклы выражаются как их линейная комбинация по модулю 2: ВтсрВачтВз = Ве, ВттттВа = Вз! ВтслВз = Вт, В29Вз = Вв. Деревом называется связный граф, не содержащий ни одного цикла.
Остовный подграф графа — это подграф, содержащий л Ь все вершины графа. Остповом в в называется останный подграф, у л являющийся деревом. Хордой остова Р в связном графе 0 нае зывается всякое ребро графа, не принадлежащее Р. Любой подл в граф, который состоит из хорды Рнс. 3.7 и остова, имеет точно один цикл. 1(икломатическог число р(0) графа 0 равно числу хорд любого остова в ст'.
Если связный граф 0 имеет и вершин и тп ребер, то р(0) = т — и+1. (3.5) Если граф С содержит lс компонент связности, то его цикломатическое число есть (3.6) р(0) = тп — и+ ус. пространства единственным образом представим в виде линейной комбинации векторов множества. Если пространство имеет базис из п векторов, то оно называется и-мерным пространстпвом. Базис циклов графа С вЂ” это базис пространства циклов графа О, состояший из простых циклов. Вектор В зависит от простых циклов В1, Вю ..., В„, если он представим в виде линейной комбинации векторов я В=$ В;. Еч1 Любой вектор цикла графа 0 может быть представлен в виде линейной комбинации векторов базиса циклов.
Рассмотрим, например, граф, изображенный на рис. 3.7,а. Дипломатическая матрица С(С) этого графа имеет вид а Ь с ту е у па д Л Г73 13.3. Х1икломатика и коцикломааоика Гл.3. Теория графов н мографое 172 Цикломатическое число несвязного графа мажет быть определено как сумма цикломатическпх чисел его компонент связности; ь и(С) = ~ и1С;). 13.7) ог1 Цикломатическое число определяет меру связности графа. Отметим, что свойства циклов графа и его разрезов похожи. Лесом называется граф, не содержащий циклов. Иными словами, если граф состоит из нескольких компонент связности, каждая из которых является деревом, то данный граф является лесом.
Если лес С имеет п вершин и Й компонент связности, то он содержит и — Й ребер. Остовным лесом называется граф, каждая компонента которого является остовным деревом. Коциклический рана Х(С) 1раня разреза) — это число ребер в его остовном лесе: Х1С) = и Количество базисных циклов в графе С определяется цикломатическим числом 1циклическим рангом) графа и(С). Теорема 3.11 (Эйлер). Число базисных циклов графа постоянна и равно его цикломатическому числу. Базисной системой циклов для данного остовного леса ду графа С называется множество всех циклов графа С, каждый из которых содержит только одну хорду 17.
Эта система образует базис пространства циклов. В рассматриваемом примере циклы Вм Вт, Вз являются базисом е т й е Ь е у В Ь Св(С)— Хорды Остов Р Полученная матрица является базисной цикломатической матрицей относительно остова Р. Выполняя 2" — и — 1 раз операцию сложения по модулю 2 над базисиыми циклами, получаем все множество циклов этого пространства. Часто матрицу инциденций А и цикломатическую матрицу С называют первой матприцгй инциденций н второй матприцей инциденций соответственно. Теорема 3.12.
Вторая и первая матрица инциденций линейного арифа С связаны операцией матричного умножения: С1С) х А1С) = 0(топ 2). Доказательство теоремы основано на том факте, что если вершина о входит в в-й цикл С;, то точно два ребра, иы и иьэ, инцидентйые этой вершине, включены в в-й цикл. Запишем базисную систему разрезов для графа С и остовного дерева 11, изображенного на рис.
3.7, б: (а, т, й), (Ь, с), (я, Н), (д, т, с, й), (й, Ь, с), (у, т, а). Эта система получена следующим образом. Удаляется ребро остова .О. Множество вершин при этом распадается на два непересекающихся подмножества, У~ и Уэ. Множество всех ребер в С, каждое из которых соединяет вершину из У с вершиной из Уэ, является разрезом графа С. Множество всех разрезов для каждого ребра остова 11 является базисной системой разрезов для данного остова .О. Базисная система разрезов образует базис в пространстве разрезов, или пространстве коциклов. Эта система мажет быть записана в виде соответствующей базисной матрицы разрезов, или базисной коцикломатической матрицы: а Ь е в Ь у лов(С) = Остов Р Хорды Выполняя 2х — Х вЂ” 1 раз операцию сложения по модулю 2 над коциклами, порождаем все множество коциклов 1разрезов) графа.
Задавая в графе свойства циклов, можно определить класс графов. Рассмотрим, например, двудольные графы. Двудольным графом С(Ут, Уэ) называется граф, множество вершин которого разбивается на два непересекающихся подмножества, У1 и Уэ, так, что каждое ребро в С соединяет две вершины из разных подмножеств. Для того чтобы убедиться в том, что граф является двудольным, достаточно проверить его циклы. Теорема 3.13.
Графявлягтся двудольным тогда и только тогда, когда все яго циклы имеют четную длину (чегпны). Доказательство. Пусть С вЂ” двудольный граф. Тогда множество его вершин распадается на подмножества У1 и Ут. Рассмотрим любую вершину из У1.
Для того чтобы получить цикл, проходящий через эту вершину, надо пройти по одному из ребер из ' У1 в Уэ и по другому из Уэ в У1 по й раз. Таким образом, любой ципл в С имеет 27е ребер, т. е. является четным. 13.4. Дифференцирование графов и мографов 175 174 Гл.з. Теория графов и мографов Пусть теперь все простые циклы четные; докажем обратное утверждение, что 0 — двудольный граф. Предположим, что се— связный граф.
Для любой вершины тц Е Г» обозначим через У» множество вершин, состоящее из и; и всех вершин, находящихся на расстоянии четной длины от аб через Уэ обозначим множество остальных вершин, находящихся на расстоянии нечетной длины от а,. Пусть теперь имеются две вершины, о», оь Е Ут, которые соединены ребром. Поскольку между ич и о, а также между о, и иь — четное число ребер, то цикл, проходящий через ребро (о., оь) и вершину о;, нечетный, но это противоречит условию, согласно которому все циклы четные.
Следовательно, вершины Уэ не соединены между собой. Аналогичное доказательство можно провести, если с» имеет несколько компонент связности. В двудольном графе не обязательно каждая вершина из У» соединена с каждой вершиной нэ Уя, но если это так, то граф называется полным двудольным графом и обозначается К,„, где и» вЂ” число вершин Ум а и — число вершин Уэ. Граф К „имеет гп+ и вершин и гпп ребер. Полный двудальный граф К»,„называется звездным графом (звездой) и является деревом.
Заметим, что любое дерево является двудольным графом. Часта двудольный граф называют графам Кгнига. 3 3.4. Днфференцнрованне графов н мографов Понятие производной в математическом анализе характеризует степень изменения функции прн малом изменении ее аргумента; в основу понятия производной положено понятие предела. В дискретной математике отсутствует понятие предела, поэтому невозможно механически перенести понятие производной из непрерывной математики в дискретную. Для решения оптимизационных задач дискретной математики введем понятие производной, основанное на использовании понятия частоты букв в словах некоторой модели Ф. Перед формальным определением производной рассмотрим следующий пример. Пусть задан граф 0 (рис.
3.8, а), и нас интересует частота участия ребер в образовании остовов графа О. Граф 0 содержит 8 остовов (рис. 3.8, б), и искомую частоту можно характеризовать, например, числом вхождений каждого из ребер в эти остовы. Например, ребро о участвует 5 раз в образовании остовов, ребро с — 4 раза и т. д. Частота ребер будет характеризоваться более полно, если наряду с указанными выше числами вычислять числа, каждое из которых равно количеству остовов, в которых содержатся два зафиксированных ребра. Например, ребра а н 5 содержатся в двух остовах.
Еше более точно искомая частота пары ребер р; и р» определяется отношением числа остовов, которые содержат ребро р; или р., но не содержат их одновре- менно, к числу остовов, содержащих как ребро р;, так и ребро р". (у; — 2Ц+»»)/Ц, где Д, »», »»» — количества остовов графа, в которые вошли ребра р;, р, р; и р соответствейно. Ь Ь /Ь 2,З 2,З с ь Это отношение пока- а'~~е а'о а а~ге 2, зывает степень неравно- э ' з мерности участия пар ребер в образовании остовов графа. а а е в Условимся в дальнейшем исследуемый процесс называть сабы»пигм Я, происходящим при вы- а е полнении определенных условий.
В рассматривае- ьЯ мом примере событием Я является образование множеством ребер остова графа О, а условием— вхождение ребер графа в Рнс. З.з данное множество. Событие Я мажет быть задано соответствующим предикатом Р(з). В рассматриваемом примере предметной областью является множество ребер (а, 5, с, И, гу. Мощность сигнатуры остова равна 3 ОУ) — 1 = 4 — 1 = 3); следовательно, местность предиката Р(З) также равна 3: Рз(8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
