Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 36
Текст из файла (страница 36)
Перед тем кап уточвить наше утвари<девке, кеобходимо ввести два определения. Определение. в) Пусть С (т', Е) — граф. Элггзгнтарног стягивание С образуется путем удалекия ребра [оь о) из Е, еамекы каждого и, и о, в Е новым символом зо, удалекия о, и о, па т и добавлепия зо к т'. Графически элемектарвое стягивание С получают путем слиявпя двух смежных вершки после удалепия ребра между иимп и обозвачекпя «составпойз вершины через и~. б) Граф С называется стлгиеагмым к графу С', если С' может быть получев пз С путем последовательности элемепгэрвых стягкваппй. П р п м е р 3.4.
На ркс. 7Л 3 кзображевы графы С и С', при этом С стягивается к С', Х 0 Рве. 7.13 Теорема (Нуратовскпй). Гра4 является планарнык тогда и только тогда, когда он не содержит нодгра(дов, стягиеаемыл к Кь или Кз,з. Доказательство этой теоремы лежит ва пределамя целей ккпгп и поэтому опущопо.
г Из теоремы Куратовского заключаем, что Кь и Кз.з являются существенно едивствеввыми ие плаварвыззи графамп. Алгоритмы, осковвввые иа этой теореме, были прпдумавы для того, чтобы определить, является лп даквый граф плакаркым или иет. 3.2. Раскраска карт и графов. О и р е д е л е и и е. а) Раскраской С (т', Е) качывается задапие цвета вершккам С так, что еслп [о, и~)«вЕ, то и в ьа имеют различвые цвета. 232 б) Хроматпчески>т числом д(С) графа С пазывается минимальное число цветов, требующееся для раскрас- кпС. е Теорема. т(С) < 4 для есех планарных гра/дое С. д Эта теорема была впервые едоказанае в 1976 г.
проверкой па компьютере всех возможиых случаев е), Определение. Пусть М вЂ” карта. Определим карту М', называемую двойственной к М, следующим образо>«выберем впутрепиюю точку в кап>дай области М; еслп две области имеют общее ребро, то проведем дугу, связывающую выбрвппые виутрепкпе точки в этих областях. Этот процесс определяет М'. д Прлмер 3.5. На рис. 7.14 изображена карта М вместе с двойственной картой М'.
д х / / / / / М М Рас. 7.14 Раскраска М' соответствует раскраске областей М так, что области, имеющие общее ребро, имеют разные цвета. Следовательно, мы можем переформулировать теорему о раскрашиваиии в четыре цвета следующим образом. Теорема. Если области карты М необходимо раскрасить таким абрагом, чтобы смежные области имели различные цвета, то для этого требуется не более четырех цветов. д Уп ражиекпе 73. 1. Пусть Т (>/, Е) — дерево с )У! и. Доказать, что (Е! -п-1.
2. Проверить справедливость формулы Эйлера для графов яз упражпеиля 7.1, 1, ° ) До свх пор ает узеревкостк з том, что зта теорема ва самом деле доказана.— длинен. лед, 233 3. Пусть С (Г, Е) — планарный граф и Ь, обозначает степень области г в карте б. Доказать, что ,Я Ь, ° 2!Е!. ий 4. Пусть О (У, Е)- связный планарвый граф и ! 'г' ! > 3, Доказать, что )Е! (3! г'! — б. 5. Привести примеры, показывающие, что приведенное в задаче 4 этого упражнения неравенство неверно при ! г'! (3. В.
Определить граф 6, для которого 7(Щ 4. 7. Пусть Т-дерево. Что является вначением 7((Т)? $4. Структуры данных для представления графа Матрица смен1ности предполагает очевидный метод представления графа в машине — на языке высокого уровня мы можем использовать массив, чтобы хранить злементы матрицы. Симметричность и пулевая диагональ сокращают необходимый объем нанят~; для графа с я 1 вершинами требуется — л(л — 1) ячеек. Обычно многие элементы матрицы равны нулю и постону большая часть используемой памяти является лишной, однако, несмотря на зто, иногда матрица смежности является наиболее удобным представлением графа. Однако для многих задач предпопительиым является представление в виде списка смежности.
В этом случае мы свяжем список связей Е, с каждой вершиной иш У; Б, является списком вершин, смежных с и. 1,, Рас. 7дб Пример 41. На рпс. 7.15 даны граф и списал, которые могут быть использованы для его предстазлзавя, 4 234 Одни из путей применения зтпх сппсков-зто использование массивов Е(1', Ь), 1 -6 е < 2, и Р(!), 1 < ! < я, где Е(1, 1) хранит номера вершин, Е0, 2) хранит связь, а Р(!)- точки начала списка 1„( в Е. Пример 4.2.
Для графа из примера 4.1 мы можем иметь ситуацию, изображенную на табл. 7.1. Таблица ?.! )чо Е((, 2) и(() Если и~ не имеет смежных вершин, то установим Р(!) О. в противном случае Е(Р(!), 1) является смежной с и< и ((, Е(Р(!), 1Ц является ребром графа. Аналогично, если Е(Р((), 2)чьО, тогда Е(Е(Р(!), 2), 1) является смежной с иь Фрагмент программы, которая дает список смежных вершин к каждой вершине, выглядит следующим образом: Еог 1 < ! ~ я йо Ьея(п ттгйе 'вершины смежные с вершиной', 1 Ь -Р()) .Ы)е й" О йо Ьея)п тгг1!е Е(Ь, 1) Ь -Е(Ь, 2) епй епй Аналогичная программа может быть использована для создания матрицы смежности М графа из представления 23б с помощью спкска связей Е, Р следующим образом: [ог 1<[, у<я бо М([, у) О [ог 1<[о-: я бо Ьей[п й '- Р ([) тг[г[[е Йт.
О йо Ьей[п М([, Е(Й, 1))'-1 Ь -Е(й, 2) епй епй Чтобы соадать струьтуры Е н Р иа М, можно испольао- вать следующую программу: 1ог 1 < [ < л йо Р(!) ! 1ог 1 < ! < и йо Е ([, !) '- О 1ог 1<[я:и г[о Ьей[п Игее -! 1ог 1<у<я йо Ьей!и И М([, 1)-1 [Ьеп Йо Ьед[п Е (Игее, 1) 1' И уФя бо Ьед[п Е (Игее, 2) - Игее+ я Игее - Игее+ и епб епб епй епй Воаможно другоа представление граФов с помощью списка связей. Выбор представления во многом зависит от используемых алгоритмов.
Представленпе Ь, вершин, смежных с и, в виде списка свяаей определяет зпорядокэ ребер, выходящпх из о. рассмотрим зто последнее утверждение и списки связей, данные в начале етого параграфа, по отношению к графу. Ребра упорядочены, как показано на рис. 7.[б. Граф с упорядочиванием ребер такого сорта называют упорядоченным зра[боль Дадим формальное определение, 23с Определение. Множество Р (ин ..., и„) вершки вместе с множеством (Ь,,, Б,,,..., Ь,„1 тпорядоченных списков упорядоченных йзр Р~ вершин называют рнорлдочэнным графом. 1 7 Необходимо наложить некоторые условия на списки Ь., чтобы рассматриваь Р 2 мые структуры были графа- ' 2 Ю мв.
Этн условия следующие: а) (Р, и)ФЬ, для любого Раз (т( б) (ю, и)шЬ„~(и, ю)зз г„т шБ. э РФ Граф, изображенный на Рес. 7дс рпс. 7.(б, может быть записан в терминах упорядоченного графа следующим образом: ((Рь Рзе Рзе Рз)з (((иь Рз)е (Рь Рз)1 (Рв Рз) ) > ((Рз, Р~), (Рзэ Рз), (Рз, Р<)), ((из Р1), (Рз, Рз), (Рз, из)), ((ие Р~), (из, Рг), (Ре из)))). Упорядоченный граф определяет единственный неупорядоченный граф. Обратное утвервгдение неверно, поскольку в общем случае возможно много способов упорядочения графа. Некоторые из втих упорядочений рассматриваются в соответствии со следующим определением. Определение.
Два упорядоченных графа 6~ и бз пааываются эквивалентными, если существует биекцпя 7: Р1 - Уз между множествамн вершин и биекция сохраняет сппсковую структуру. Другими словами, если 7.-((и, ) ", (, )) есть список ребер бь то ~,н., - ((7(и), Ли,)), ..., (7(и), 7(ю„))) есть список ребер бз. э" Пример 4.3. Графы, изображенные иа рпс. 7.17, вквпвалектны, однако они не являются аквпвалентными как упорядоченные графы, э" гЗ7 Все понятия т 2 (маршруты, аамкнутые маршруты, связность, дерево) переносятся очевидным образом ва упорядоченные графы.
Ь~ пч Рв, 7,11 Упражнение 74. 1. Записать алгоритмы данного параграфа на каком- либо яаыке программирования и проверить их работу на некоторых наборах данных. 5 5. Обход графа 5.1. Введение. Во многих вадачат, включающих графы, требуется обойти граф, т. е. чтобы каждая вершина графа епосещаласы пли «обрабатывалась» только один раз. Таким образом, обход графа может быть представлен последовательностью веригин, соответствующих порядку, в котором онв обрабатываются. Если 6 ((иь сн ..., и„1, Е) и и; 5), - Я„ — перестановка, то последовательность г папп па<то ° * э па[а| определяет обход С. Так как существует я! раалвчных перестановок 5(„, то должно быть я! равлвчных способов обхода графа с в вершинами.
Другими словами, существует и! способов полного упорядочения вершин, Вершину и,п, паеывают начальной вершиной обхода, определяемого подстановкой и. Мы опишем вдесь только два метода обхода графов. Онв могут быть полезны в приложениях. Оба метода прсмсняются к упорядоченным графам и поаволяют определить перестановку (или полное упорядочение вершвн). 5.2. Обход графа по глубппе. Пусть С Цип..., и ), (1о,, ..., Сь„)) — упорядоченный граф. Выберем некоторую пачальпую вершину и, (1 ~ я < л) в положим о(1) з. Далее вершины последовательности 1 определяются 333 следующим образом: о«<з,— первая вершина (смежная с пи<>) из списка смежности Ь„«,, и„з< — первая вершина из Ь««<ю, которой нет еще в <, и т.
д., и,<м — первая вершина из Ь.«<ь <и которой нет еще в 8 (й>4). При этом, если встречается вершина и такая, что все вершины из Б„уже содержатся в Г, то процесс повторяется из вершины <аж<, где и< — последняя вершина в Ф такая, что Ь„содержит вершины, не входящие в й Обход заканчивается, когда никакая вершина из У\1 ие может быть достигнута из вершин последовательности и Если граф С связный, то описанный выше процесс определяет обход С, в противном случае — только одну пз компонент графа С (содержащую и,«>).
Если граф С не является связным, то для получения полного обхода С необходимо начинать процесс в каждой связной компоненте графа С. О помощью этого метода можно определить число связных компонент графа. Для каждого выбора начальной вершины в связном графе получеп единственный обход, так что воаможны все я обходов по глубиие упорядоченного связного графа. Если С имеет связные компоненты У< (1 «я < < р), где ~ '«'<! я<, то определены и< « яз « ... « я, обходов по глубине. С помощью следующей рекурсивной процедуры можно найти обход по глубине.
Здесь à — массив длины и <У<, все значения которого вначале разны 0; 1(и,) устанавливается равным 1 для обозначения того, что вершина и, обработана. ргосепиге 4< (о) 1(и) — 1 ргосезз тег1ех и 1ог еасЬ ж <и Ь„<)о П 1(ю) 0 Йеп <Ц<(п<) еп<( ргос Пример 5.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
