Основы дискретной математики В.А. Осипова (552659), страница 20
Текст из файла (страница 20)
Задачи и упражнения 1. Нарисовать все графы с пятью вершинами (число таких графов — 34) . 2. Доказать, что любая замкнутая цепь нечетной длины содержит простой цикл. 3. Доказать или опровергнуть: ПО Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ а) объединение любых двух различных элементарных цепей, соединяющих две вершины, содержит простой цикл; б) объединение любых двух различных простых цепей, соединяющих две вершины, содержит простой цикл.
4. Сумма степеней вершин неориентированного графа равна удвоенному числу его ребер («лемма о рукопожатии»): ',) деди; = 2т »,еУ (поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно). 5. В любом неориентированном графе число вершин с нечетными степенями четно. 6. Доказать, что следующие графы неизоморфны. 7. Являются ли изоморфными графы: 8. Показать, что число компонент связности графа С совпадает с числом элементов фактор-множества множества вершин С по отношению связности.
9. Построить графы отношений я:— у(тод 3) и тру 4=» с=~ х+ у > 4 на множестве вершин (1, 2, 3, 4, 5, 6). 4«и Матричиое задание графа 4.2. Матричное задание графа 4.2.1. Матрицы смежности и матрицы инциденций Для задания графов обычно используют матрицы смежности и матрицы инциденций. Матричное задание графа удобно, например, при решении задач с использованием вычислительных машин. Пусть С =<»', Г > — ориентированный граф с множеством вершин»г = (иы и2, ..., и„). Квадратная матрица А = ))аО((, г, д' = 1, 2, ..., к, у которой 1, если существует дуга, исходящая из и; агд = и заходящая в и", О, в противном случае называется матрицей смежкости ориентированного графа С.
Аналогично определяется матрица смежности неориентиро- ванного графа С =< Ъ; б~ > с множеством вершин»г = (им из, ..., иа), Его матрица смежности А = Ьа; ~), г, 1 = 1, 2, ..., и задается условием 1, если вершины и; и и; смежны; О, в противном случае. Заметим, что матрица смежности неориентированного графа — симметрическая. Более информативной, чем матрица смежности является матрица икцидекчий Пусть С =< У, Г > — ориентированный граф без петель с множеством вершин г' = (иы из, ..., иа) и множеством дуг Г = (и1, и»,, и«а). Матрица В = ((ЬО)! порядка ихт у которой 1, если дуга и исходит из вершины и,, Ь," = — 1, если дуга и заходит в вершину и;, О, если дуга и не инцидентна вершине и; называется матрицей икцидекций ориентированного графа С.
Для неориентированного графа без петель С =< Ъ; Я > с множеством веРшин»г = (иы из, ..., иа) и множеством РебеР Я = (ды д2, ..., д, ) матрица инциденций В = )(Ь;з(( порядка и х т задается условием ) 1, если ребро д инцидентно вершине и;, '( О, в противном случае. 4.2. Матричное задание графа 1 0 0 1 1 — 1 — 1 1 О 0 О 1 — 1 — 1 0 0 0 О 0 — 1 10110 11000 01101 00011 Рис. 4.6. П2 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пример 4.6. Матрицы смежности графов, изображенных на рис. 4.6 равны соответственно 0 1 1 1 0111 00101010 01001101 0000 1010 Матрицы инциденций графов, изображенных на рис.
4.6 равны соответственно Приведем некоторые очевидные свойства матриц смежности и матриц инциденций: 1) Для неориентированного графа С =< У, Я > сумма элементов 4-ой строки (или 4-го столбца) матрицы смежности А равна степени вершины нь 2) Для ориентированного графа С =< 7; Г > сумма строк матрицы инцидентной В является нулевой строкой; ранг матрицы В не превосходит и — 1. Используя матрицы смежности и инциденций можно ответить на многие вопросы, связанные со свойствами графов. В качестве примера приведем оценку числа путей (цепей) с фиксированной длиной.
Обозначим й-ю степень матрицы смежности А относительно обычной операции умножения матриц через А" = ))а,,- (!. (в) Ъ'тверждение 4.2. Число всех путпей (цепей) длины й ил вершины ое в вершину и равно элементу а; матрицы А '. (1) ь Доказательство проведем индукцией по й.
При й = 1 справедливость утверждения следует из определения матрицы смежности. Предположим, что оно выполняется для всех путей (цепей) длины 14 — 1. Рассмотрим множество всех путей (цепей) длины й из вершины и; в вершину о . Обозначим его через П(в;, и;, )с), а число его элементов через (П(и1, оз, й) ~.
Тогда /П(ьо оу, Iс)! = /П(о', о1, )с — 1)! /П(о1, вд, 1)/+ + /П(о1, ог, й — 1)~ ~П(вз, од, 1)/+ + /П(о,, ва, й — 1)! !П(о„, ш, 1)!. По индуктивному предположению число путей (цепей) длины (и — 1) й — 1извершиныи1 ввершину о1 равно ай,1 = 1, 2, ..., и, т. е. (П(о,, в1, 14 — 1)~ = а,, а по определению матрицы смежности (1-1) (П(и1, и;, 1)( = а (1) " Отсюда ~П(о;, ву, )с)~ = аи ° а14 Рог азу+ ° ° +а1 ° а = а,, (ь-1) (в — 1) (ь-1) (в) 4.2.2. 4и1атрицы связности и расстояний В п.
4.1 было рассмотрено понятие связности для неориентированного графа С =< У Я > с множеством вершин И = (в1, оз, ..., в„1. Квадратная матрица Я = ((зй(( порядка и у ко- торой 1, если вершины 1Л и и; принадлежат одной з," = й компоненте связности; О, в противном случае называется матрицей связности графа С. 115 4.2. Матричное задание графа Ф~) = ))г( ) )) = А Ч Е, Е") = (~4'~~, 1=1, ...,и. 114 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Матрицу связности Я можно определить по матрице смежности А графа С.
Опишем два метода нахождения матрицы связности по матрице смежности. Заметим, что элементами матриц смежности и связности являются О или 1. Матрицы, элементами которых являются О или 1 называются булевыми. Наряду с матричными операциями, над булевыми матрицами можно проводить логические операции.
Пусть, например, С = ((с; )) и Р = ((с(с ~~ — две булевы матрицы порядка и. Тогда логической суммой этих матриц называется матрица С 'с Р = () 11 !) порядка и с элементами Д = ссдЧ дб, с, д = 1, 2, ..., и. Логиссеским произведением этих матриц называется матрица С * Р = ~~д;1(! порядка и с элементами следующей итерационной формуле: где Š— единичн я матрица порядка и, где о() оу-~) ('ф~-~)4,ЕО-И') И= И си / с Тогда Я = Я(п). д; = ~/(ссь8гс(ьд), с', 1 = 1, 2, ..., и Ь=1 Ъттверждение 4.3.
Пусть С =с К О > — неориентированный граф с и вершинами. А — лсатрица смежностпсс С. Тогда Е = Е ч А ч А'„ч " ч А",-', (4,1) где Š— единичная матрица порядка п. Справедливость этого утверждения непосредственно следует из утверждения 4.2. Если число и вершин графа С велико, то нахождение матрицы Я по формулам (4.1) требует больших вычислительных затрат.
Более эффективным для нахождения матрицы связности является алгоритм Уоршелла, основанный на следующем утверждении: Ъттверждение 4.4. Пустпь С =< (т, Я > — неориептпированНЫй гРаф С ЛСНОжЕСтВОЛС ВЕРШип Ъ' = (и1, игс ..., и„) и МатРиией смежности А, и пусть У', я(1), ..., я(а) — последовательность матриц порядка п, элементы которых въсчисляютпся по (здесь операция 0 аналогична сложению, Й аналогична умножению). Логическое произведение й сомножителей С * С е * С обозначается Сс'.
Первый метод нахождения матрицы связности по матрице смежности основан на утверждении: Докажем сначала индукцией по 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, иг, ..., ис 1). Отсюда, по О-1) О-1) индуктивному предположению, Я(1 ) = 1, Яс = 1 и значит о(1) Из справедливости доказанного утверждения для 1 = и следует, что Я(") = Я. 117 4.2. Матричное задание гр»41а 3. Положим Р(") = Р. 1 и, 116 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Число компонент связности Я графа С с матрицей связности Я можно по следующему алгоритму; Алгоритм 4.1. 1.
Положим Я(о) = 1. 2. Вычеркнем нз матрицы Я, начиная с первой строки и первого столбца, те строки, в которых 1 расположена в первом столбце, и те столбцы, в которых 1 расположена в первой строке (при этом вычеркиваются строки и столбцы с номерами, соответствующими номерам вершин из одной компоненты связности). Получим матрицу Яз. 3.
Если все строки и столбцы вычеркнуты, то заканчиваем процесс, и число компонент связности Я = Я(о). Если нет, то полагаем яО) = я(о) + 1, применяем шаг 2 к матрице яп и т. д. В п. 4.1 определено понятие расстояния е((ю,, и ) между вершинами о; и ид неориентированного графа С =< 1; Я ) с множеством вершин $' = ~им и2, ..., иа1. Матрицей расстояний называется матрица Р порядка и с элементами д«3 = е((и;, ио). Зная матрицу смежности А можно определить матрицу расстояний Р, пользуясь модифицированным алгоритмом Уоршелла: Алгоритм 4.2. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
