Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 34
Текст из файла (страница 34)
2) Доказать, что если А ю0(п), то де1А = ~ 1. 13, Докааать, что 50(2) явллется подгруппой 0(2). ГЛАВА 7 ТЕОРПЯ ГРАФОВ $1. Вводные понятия Ыногпе отношения на конечных множествах могут быть пзобра1кепы в впде рисунков (см. Э Э гл, 2), с которыми можно работать прп помощи соответствующих матриц. Перед тем как определить конструкции этих рисунков, необходимо быть уверенными в том, что это не повлечет за собой никаких двусмысленностей. Введем необходимые понятия. Пусть Р— конечное множество и 1т ((У, У): У !И т'). Положим Р )тэ'ч1т ((У У )! У ~ У ) и определим на)т' отношение эквнвалентностн следующим образом: (у! у2) (ш! и12) если (у1 у2) (ш! и'2) ИЛИ (У1, Уэ)~(Ж2! Ш1).
Важное свойство отношения с4!ормулпровано в следующем предложении. П р е д л о ж е н п е. Отпошепие является отношением эпвивп.!вптпости па )т . !Г Доказательство оставляем в качестве упражнения, Множество эквивалентных классов, определенное таким образом, обозначим через р'/ . Каждый класс эквивалентности содержит ровно два элемента, так как если (у„у,)енр', то [(у1, уэ)) ((у1, уэ), (уи у!)). Здесь [(у1, уэ)) — класс эквивалентности, содержащий (у1, уэ).
Сейчас мы в состоянии дать строгое определенпе граФа. О и р е д е л е н п е. Гра$о !! 6 называется пара С -(т', Е), где )т — пепустое конечное множество вершил, а Š— подмножество !т'/ г17 Другими словами, можпо сказать, что граф 6 есть пара 6 =(т', Е), где ]т — иепустое конечное множество вершин, а Š— множество иеупорядочеивых пар разллчиых вершин. Мвожество Е называют миожеством ребер графа, ! И обозначает число вершки 6, ]Е! — число ребер 6.
Следующий результат выражает связь между графами и классамп отношений иа конечных множествах, П р е д л о ж е и и е. а) Граф 6 (]т, Е) определяет нерефлексивное симметричное отношение на У, б) Нерефлексивное симметричное отношение на конечном множестве т' определяет граф. Доказательство. а) Пусть 6 ( т', Е) — граф. Определим отношение В(Е) яа т' следующим образом: о,В(Е)ог тогда и только тогда, когда [оь ог]ш Е.
Отиоптеиие В(Е) иерефлексивио, так как оВ(Е) и тогда и только тогда, когда [о, о]си Е, ио [о, о] Ф Е, поскольку (о, о)Ф т' . В(Е) слмметричио для о!В(Е)ог тогда и только тогда, когда [о!, ог]жЕ, однако [о!, ог] ((о!, оз), (ом и!)) [ом о!]. Следовательно, огВ(Е)ог тогда и только тогда, когда огВ(Е)о!.
б) Если  — иерефлексивиое симметричное отиошевпе па Р,тоВ=]т'. Нерефлекспвпость В означает, что (и, о) Ф В для любого паз ]т, поэтому В с 'т'. Спмметричиость В означает, что (о!, ог)!иВ тогда и только тогда, когда (от, о~)ш В. Определим Е формулой Е В/-, тогда 6=(У, Е) есть искомый граф. Графы могут быть представлены матрицами с булевыми элементами. Многие из свопств графов могут быть определены пз пх матричных представлений путем алгебраических преобразоваипй. Это станет понятным из последующего излоясекия. Определепие.
Иатрица смежпости Аы.г?(п, В) графа 6 =(]', Е), где ]И п, определяется следующим образом: если (оо о;] еи Е, Ап= [О в протпвком случае. Говорят, что вершины щ и о, являются смежными, если Ао-1. Ясно, что Ан' О (! 1,..., и) п А А'. Такпг! образом, А симметрпчиа, и в обозиачеипях $1 гл. 6 А А(В(Е)). У 2!8 Изобраькеняе графа ь> ((5, Е) получается путем располольеььил расли шыл точек па й для каждой уж 1', причем, если [у, и) >н Е, ыы проводим лпншо, соединяющую вершшьы у и ьи. О 1 1, ~У» У> 51= 1 О 1 О Матрица смежности нз»враз«виив Рлс. 7Л Пример (Л.
Пусть (. р =(Уп Уз, Уз)> Е =([Уь Уз( [Уз, ь'з!, [У1, Уз))> [(>[ 3, !Е! 3. Этот граф изображен на рпс. 7.(. 2. $' (Уп Уз, Уз, Уы Уь) Е = ( [у>, уз(> [уп уь[> [уы "з[> [Уз> Уь! > [Уз, Уь[, [из, Уь[> [Уы Уь!) [(5[ = 5, [Е[ = 7. Этот граф изображен на рнс, 7.2. У, О1ОО1 О11О Оьа О11О1 1 О 1 1 О У, или Матрица сне»и»асти иь иь я»евреи>а»ие Рас.
7.2 Графы являются скорее «топологическими», чем «гео- метрическими» объектаыи, т. е, они выражают больше от- 219 ношения между вершинами, чем расположение вершин и ребер в пространстве. Таким образом, граф ьгожот быть изображен бесконечным количеством разных, по «эквивалентных» способов. Однако изображения графов могут вводить в заблуждение. Например, иа пересечения двух ребер на рисунке не следует, что точка пересечения является вершиной (см. первую диаграмму на рпс. 7.2). Ясно, что нижней (верхней) треугольной части матрицы смежности достаточно, чтобы определить граф. 'Ь ъи ысвь аг»3ечгь а Нптзтель уже знаком с понятпяьш подструктуры и изоморфизма или же с эквивалентностью алгебраических систем. Дадим следующие определения. Определение. Говорят, что граф Н (!гь Е|) является яодгра!бом графа б (У, Е), если Р, ж У и Е1 ш Е.
Если !'~ = !г, то говорят, что Й является остовным лодграубол О. Если Р~ — непустое подмножество вершин графа (Ъ', Е), то подграф (!Уп Е~), порожденный Рь определяют как [и, и') ш Е1 «=: и, ю ш !г1 п [и, и) «и Е. э" Определение.
а) Пусть О1 (гь Е~) и Оэ (Ри Е») — графы. Будем говорить, что 0~ и ь'э эквивалентны, если существует биекцпя 1: !'1 — !гэ такая, что иЕ(Е1) иэ "ь1(о)В(Ег)Лю). б) Пусть 0 (»', Е) — произвольный граф. Определлм отображение 6: !г - Х 0 (0) следующим образом: величина 6(и) равна числу ребер, содержащих вершину я ш «'. Назовем 6(и) степенью вершины ш Следующее предложение выражает два простых, по важных факта о свойствах графов. П р е д л о ж е н и е. а) ~„зб(и) 2[Е[. ьиу 220 б) В любам ерафе число вернпис нечетной степени четпо. Доказательство. Етая.дое ребро дважды входит в сумму, откуда и следует утвержденпе.
в) Пусть»'.ы»' — мконсество вершин четной степенп, а»'ц ы»' — множество вершин нечетной степени. Заметим, что 1' — )»,0 $'ц п у, й )тц — йг; следовательно, ~ б(а)- ~д„б(а) + ~ б(о), »а» »Е»» »Е»о 2[Е[ 2Ь+ ~~~~~ б(а). ему (Ясно, что ~ б(а) = 2Ь, где Ь вЂ” некоторое целое.) Та»»я 1 » кнм образом, б(о) 2([Е[ — Ь), »а»ц т. е. четно, однако каждое б(а) в левой части почетно, поэтому ~$'ц! четно.
ту Во многих прплоя<еннях теория графов о топологии графа имеется дополнительная информацпя, относящаяся к 1', плп к Е, нлп к обоим множествам одновременно. Чтобы конкретпзпровать вышесказанное, определим понятпе помеченного графа и дадим несколько примеров. Определенпе. 1) Пусть Е» и Ев — множества меток. Пометкой пли распределением меток вра~а С (»', Е) называется пара функцпй 1' )т- Е» — распределение меток вершин, я: Š— Юв — распределенпе меток ребер. 2) Пусть граф С ()', Е) помечен с помощью функппй ( п д, а С~ =(Уь Е~) помечен с помощью ~~ и яь Графы С п С~ называются эквивалентно помеченными, если существует бпекцпя Ь: Р- )ти такая что а) С и С1 зквпвалентны как непомеченные графы; б) Г(а)=~1(Ь(а)) для всех авв)т, позтому соответствующпе вершины имеют одну н ту же пометку; в) л([а, и4) д~([Ь(а), Ь(и))) для всех а, иы»т, т. е, соответствующие ребра пмеют одну п ту же пометку.
321 Часто бывают помечеппыми только ребра или же только вершины. Вышесказанное применимо н в этом случае. Тогд» ) помечены только вершины; л = сопз1, ) 7' = сопзз, 1 помечены только ребра. Х У1 Е-ьЯю 1 Ребра нлп вершппы (или те и другие вместе) поме- ченного графа несут информацию, которая дополняет пдп заменяет обычкую идентификацию с помощью имен. Прпме р 1.2, 1. Пусть у (у1, у2, уз, уА Е ([у1е уз]~ [у22 уз]з [узь уз])ю 7: Р— (города Великобрптанпи), л1 Е- Х, Ду1) — Лондон, а([у1, уз]) 105, 1(уг) — Кардифф, а([уг, уз]) 196, 7'(уз) — Бирмннгем, л([уз, уз]) 292~ 7(из) — Эдпкбург.
Зтот граф изображен на ркс. 7.3. 2. Пусть графы уу нЕра С1 ((У1~ У22 УЗ)~ ( [У12 У2] ~ [Уь Уз], [Ум Уз])~ Сг =((1У1, шм игз) ([УУ1, шг], [1У1~ 1УЗ] [У 2> 2УЗ]) ) ингам помечены так же, как укааано на рис. 7А; С1 н Сг являются эквпвалентно помеченными графамн (вершпны не помечены). а з' п р а ж н е н н е 7.1. Построить докааательств о первого предложенпя этого параграфа.
2. Изобразпть графы, представленные следующими ыатрнцами смежности: Уа У1 йардифф Рандан Рпс. 7.3 -О 1 1 О О 1 О О О О О О О О 1 О О О О 1 О О О 1 1 1 ОО О О О О 1 О О 1 О О 1 О 1 О а) 222 3. Определить матрицы смежности графов, представленных па рпс. 7.5. пт гго 90 тю 72О из '«О и, Рас. 7,4 4. Начертить подграф, порожденный вершинами (ом оз, оо пз) графа па рпс. 7.5,а.
Рсс. 7.5 5. Пусть С =(Р, Е) — граф п !)г! = и. Какое может быть макспмально возможное аначеппе !Е(? 6. Сколько существует различных графов, нмеющпх п вершин? Остальные задачи етого параграфа требуют введения некоторых дополнптельных понятий. Определенпе.
а) Граф 6 ()г, Е) называется полных, еслп для всех иь отж У пиееи (оп га) жЕ. Полный граф с верпшнами обозначается через К . б) Граф 6=(Р, Е) называется дврдольным, если существует разбпенпе г' = (1~п Га) такое, что нпкакпе две вершины пз Ъ'~ п.п| пз )'з пе являются смежнымп. Двудольный граф называется полныш, если для любой пары щ ж 1'~ и отж Уз пмееи (иь оз)жЕ. Еслп !!'1! =т и !Ус! =и, то полный двудольпьш граф ()г, Е) обозначается через К,.. 7 223 7. Изобразить граф Км 8. Построить пример двудольпого графа. 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
