Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 42
Текст из файла (страница 42)
Алгоритмы и рекурсия О12 31+О = Ц1 х 1 — 2 х 0) — 2(1 х 1 — 2 х 3) + О = = 1 — 2( — 5) = 11. Определим б, как / 1, если 1=1'; ) О, если гну. ОПРЕДЕЛЕНИЕ 5.56. Пусть 1„есть матрица )1, ) размера и х и, где 1„= б,, т.е, на диагонали матрицы 1„стоят единицы, а все остальные ее элементы равны нулю.
Матрица 1„называется единичной матрицей размера п х п, или просто единичной матрицей. Единичная матрица обладает тем свойством, что для любой матрицы А размера и х п имеет место равенство А1„= 1„А = А. ПРИМЕР 5.57. Единичными матрицами размера 2 х 2 и 3 х 3 являются 1з = О 1 и 1з = ОПРЕДЕЛЕНИЕ 5.56. Пусть А — матрица размера п х и. Мультипликатив- но обратной, или просто обратной к матрице А называется матрица А обладающая (если она существует) тем свойством, что АА ' = А 'А = 1„. 51 3 — 51 Матрица [ 1 3 ~ является обратной к ~ 2 ~, т.к.
3 — 1 2 — 1 2 1 3 О 1 ' Г) ПРИМЕР 5.59 является обратной к Матрица ПРИМЕР 5.60 поскольку [ — 1 2 2] Π— 1 2 1 2 — 4 — 1 — 2 5 Π— 1 2 1 2 — 4 — 1 — 2 5 2 1 Π— 1 2 2 О 1 1 Π— 1 2 1 2 — 4 — 1 — 2 5 РАЗДЕЛ Б.д Дальнейшее изучение матриц 241 Ниже приводится алгоритм нахождения матрицы, обратной к матрице А размера и х и; 1. Найти бе1(А). Если он равен нулю, обратная матрица не существует. 2. Для каждого А;, найти алгебраическое дополнение С„и сформировать матрицу С = [С, ), называемую матрицей алгебраических дополнений.
3. Найти матрицу С', транспонированную к матрице С, так что С,' = С с. Матрица С' называется сопряженной к матрице А и обозначается аЩА). 4. Разделить каждый элемент сопряженной матрицы ас))(А) на с1ес(А). 5. А ' = а<Ц(А). 1 с$ес(А) Га Ь) Следовательно, если В = ~ о ~, то ~ с д — Ь с1ес(В) с1ес(В) В с1ес(В) бес(В) где с1ес(В) = ас1 — Ьс. Путем прямых вычислений можно показать, что ВВ В 'В = Хз. Аналогично, для нахождения матрицы, обратной к матрице А, где Аы Асз Асз Агс Азз Азз 4зс Азз Азз А= [ Аза Азз [ Агз Асз Азг Азз [ Азг Азз Агг Агз Азз Азз А '= 1 с1ес(А) Асц Агз Азг Азз Аы Асз Аз с Азз Аы Асз Ащ Азз Агс Азг Аз с Азз Аы Аю Азг Азз Аы Асз Ащ Агг ПРИМЕР 5.61.
Пусть А = ~ . Тогда оес(А) = 1. Матрицей алгебраиче- 3 — 5) ских дополнений для матрицы А будет — ( — 5) 3 5 3 определяем матрицу алгебраических дополнений С = [С,з[, где С;, — детерми- нанты матриц, полученных из А = [А,з[ удалением строки и столбца, содержащих Ас„умноженные на соответствующий знак, а именно, ( — 1)'+з. Наконец, для по- лучения А ' матрица С транспонируется и делится на бес(А), после чего 242 ГЛЯЯЛ 5. Алгоритмы и рекурсця Матрицей, сопряженной к матрице А, будет аб1(А) =С = З Обратной к матрице А будет матрица З 1 З ПРИМЕР 5.Б2. Пусть А = Π— 1 2 1 2 -4 — 1 — 2 5 Тогда оет(А) = О. 2 — 4 1 2 — 1 -2 1 — 4 — ( — 1) .
— 1 5 +2 = 0+1+0 = 1. Матрицей алгебраических дополнений для матрицы А будет ! 2 — 4 1 — 4 1 — 2 5 — 1 5 — 1 2 — 2 — 2 5 — 1 5 — 1 — 1 — 2 — 1 2 2 — 4 О 2 О 1 — 4 1 к А, будет — 1 2 2 Таким образом, матрицей, сопряженной а41(А) = С' = а обратной 2 1 Π— 1 2 2 О 1 1 А 2 — 1 О 1 2 1 О 2 1 2 1 Π— 1 2 2 О 1 1 РАЗб1ЕЛ 5.а.,б)вльнвйшвв иэученив мал)рии 243 ° УПРАЖНЕНИЯ Вычислите детерминанты матриц 2 6~ 2. Выч а) ислите ~ 2 6 детерминанты матриц ~ — 4 6)7 ! — 2 — 1 1 2 Π— 3 в) Вычислите детерминант матрицы И!!!1 Найдите А ', если А = — 4 71' б) в) г) 6.
6. Понятие матрицы перестановок было дано в определении 4.52. Докажите, что если А — матрица перестановок, то А ' = А'. В предположении, что если А и  — матрицы, то б1ес(АВ) = б)ет(А) б1ес(В), а) докажите, что детерминант единичной матрицы равен 1; б) докажите, что если матрица А имеет обратную матрицу, то 1 ЙеФ(А) ' в) докажите, что матрица А имеет обратную тогда и только тогда, когда бег(А) ф О. б) ~ 6) — 4 6)' 6 — 4 — 5 1 — 11 2 3 — 1 1 Рлэ77ел блб Графы 245 Рис.
б.г Рис. 4.2 ПРИМЕР 6.4. Граф, у которого Ъ' = (а, Ь,с,с~,е7 и Е = ((а, Ь), (а, е), (Ь, е~т, (Ь,сЦ, (Ь, с~, (с,а)), может быть изображен диаграммой, показанной на рис. 6.3. Во многих книгах по математике графы, определенные выше, называют простыми графами. Тем не менее, в теории графов чаше всего используются структуры именно такого типа. Ограничение на существование только одного ребра между двумя вершинами дает возможность представлять любое ребро как множество из двух элементов, а именно, вершин ребра. Перечислим теперь основные типы графов, которые будут использоваться в других главах. Заметим, что многие теоремы этой главы будут справедливы для графов более обшего вида.
Ребро, которое соединяет вершину саму с собой, называется петлей. Если в графе допускается наличие петель, то он называется графом с петлями, Если в графе допускается наличие более одного ребра между двумя вершинами, то он называется мулыпиграфом. Если каждая вершина графа отмечена, то граф называется размеченным. Если же допускается как наличие петель, так и существование более одного ребра между двумя вершинами, то мы будем называть такой объект псевдографом. Теория графов берет начало с решения знаменитым математиком Эйлером задачи о кенигсбергских мостах в 1736 году.
Существуют две внешне различные версии этой задачи. Задача возникла в прусском городке Кенигсберг на реке Прегал. Жителям Кенигсберга нравилось гулять по дорожке, которая включала семь мостов через реку Прегал. Люди интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реки.
Различие между двумя версиями задачи — чисто географическое. Согласно первой версии на реке Прегал был остров Кнайпхоф и участок суши, возникший в результате разветвления реки Прегал на рукава. Этот район и семь мостов показаны на рис. 6.4. 246 ГйАНА 6. Графы, ориентированные графы и деревья ид Рис.
6.4 Согласно второй версии на реке Прегал было два острова, один из которых— остров Кнайпхоф. Эта ситуация изображена на рис. 6.5. Рис. 6.6 Точная версия авторам не известна. К тому же это не имеет значения для математической формулировки задачи. Эйлер построил мультиграф, показанный на рис. 6.6, который пригоден для каждого из этих случаев. В этом мультиграфе участки суши Эйлер изобразил как вершины, а дорожки через мосты — как ребра. В таком случае задача приобретает следующую формулировку; начиная с любой вершины, проходя по каждому ребру только один раз, вернуться в исходную вершину.
Далее будет показано, как на основе понятия мультиграфа Эйлер решил эту задачу. Приведенный пример иллюстрирует полезность математических абстракций, по крайней мере, в двух аспектах. Во-первых, абстракция устраняет в содержании проблемы несущественные детали и концентрирует внимание на тех понятиях, которые действительно важны.
Во-вторых, абстракция часто выявляет кажущееся различие задач, совпадающих по сути или, по крайней мере, имеющих сходные решения. Сказанное особо справедливо для теории графов. Решение задачи о кенигсбергских мостах будет рассмотрено в разделе 6.2. Примером другой проблемы, которую можно промоделировать на основе теории графов, является задача о снабжении трех домов тремя видами коммунальных услуг. Согласно условию задачи к каждому из трех домов необходимо подключить три вида коммунальных услуг, например, воду, газ и электричество, посредством подземных линий труб и кабелей. Вопрос состоит в том, можно ли обеспечить эти три дома коммунальными услугами без пересечения линий снабжения. Граф, моделирующий данную задачу, показан на рис.
6.7 РАздел 6.1. Графы 247 Я< вода газ электричество Р„ Аналогичная задача более практического характера возникает при создании микросхем. В них пересечение проводов на каждом уровне является нежелательным. Такого рода задачи будут рассмотрены в одной из последующих глав при изучении планарных графов. ОПРЕДЕЛЕНИЕ 6.5. Степенью вершины о, обозначается ое8(о), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной.
ПРИМЕР 6.6. В графе, показанном на рис. 6.8, вершины а и с — смежные, а ет, ез и ез — смежные ребра. У Рис. 6.8 Однако, вершины а и т смежными не являются, а ез и ез не являются смежными ребрами. Вершины Ь, с и а имеют степень 2, в то время как вершины а и Х имеют степень 3. и ТЕОРЕМА 6.7. Сумма степеней вершин графа всегда четная. ДОКАЗАТЕЛЬСТВО. Поскольку каждое ребро графа имеет два конца, степень каждого конца увеличивается на 1 за счет одного ребра. Таким образом, в сумму степеней всех вершин каждое ребро вносит 2 единицы, поэтому сумма должна в два раза превышать число ребер. Следовательно, сумма является четным числом. Теперь воспользуемся этой теоремой для доказательства следующего утверждения.
ТЕОРЕМА 6.8. В любом графе количество вершин нечетной степени четно. ДОКАЗАТЕЛЬСТВО. Доказательство проведем методом от противного: предположив, что теорема не верна, найдем противоречие, из которого будет следовать, что теорема справедлива. Если теорема не верна, то имеется нечетное количество вершин, степени которых нечетны. Но сумма степеней вершин с четными степенями четна. Сумма степеней всех вершин есть сумма степеней вершин с нечетными 248 ГЛАВА б. Графы, ориентированные графы и деревья степенями плюс сумма степеней вершин с четными степенями.
Поскольку сумма нечетного числа и четного числа есть число нечетное, сумма степеней всех вершин нечетная. Но это противоречит теореме 6.7, поэтому мы пришли к противоречию. Следовательно, делаем вывод, что теорема справедлива. ПРИМЕР 6.10. Графы, изображенные на рис. 6.9, 6.!О и 6.11, а Ь с а с Рис. б.10 Рис. 0.9 являются подграфами графа на рис. 6.12. а Ь с д е Рис. б.12 Рис. б.11 Путь (маршрут) в графе — это просто совокупность ребер, которые объединены вместе вершинами так, что вдоль них можно двигаться по графу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
