В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 34
Текст из файла (страница 34)
Толи1иной г(С) графа С называется наименьшее число сто плапарных подграфов, объединение которых дает граф С. Очевидно, что толщина плапарного графа равна 1. Для толщины связного (и, т)-графа справедливы оценки 1(С)>~ [, г(С)>[ Действительно, первое неравенство сразу вытекает из следствия 37.3, а второе следует иа первого, если учесть легко доказываемое равенство ) а/Ь [= ((а+ Ь вЂ” 1)/Ь), (1) где а, Ь вЂ” положительные целые числа. Непосредственным следствием первого неравенства является следующая оценка толщишл полного графа (ввиду того, что т = ~„) — целое число): (К ) Гв(в — 4)72+3(в 2) — 1 1 Ге+71 3 (и — 2) 6 186 Оказывается, что если и Ф 4 (той 6) и п ФО.
Известны тактгге следующие формулы для толщины (доказательство можно найти в [28) ): 4 [' где ч„— и-мерный нуб; Рз 12 (р+ о — 2) [' аа исклгоченпем, возмонгпо, тех случаев, когда р.С д, рд — нечетное и существует такое целое число 1с, что д= (2Й(р — 2)/(р — 2й)]. Из последней формулы, используя равенство (1), получаем формулу Искаженность графа. г1скаакеппостыо з)с(6) графа С называется наименьшее число ребер, удаление которых приводит к планарпому графу.
Для искаженности полного графа справедлива формула я)г (К,) — ( ) — 3п + 6, и > 3„ которая непосредственно вытекает из следствия 38.3. УПРАЖНЕНИЯ 1. При каких значениях л графы С (определение см. в упр. 14 гл. 1) планарпы7 2. Докажите, что лзобой граф можно уложить в трехмерном пространстве так, что все его ребра будут изображены прямолипойпыми отрезками. 3. Всегда ли плапарсп рсберный граф Л(С) планарпого графа 67 4.
Нарисуйте граф, изочорфный графу, изображенному на рнс. 37Л, так, чтобы впошпей стала грань а) 2; б) 3. 5. Снольким граням молгот принадлежать веригина степони д ) 1 плоского графае О. Покажито, что формула Эйлера следующим образом обобщаотся на случай посвязного плоского графа: и — т+1 = )г+ 1, где к — число связных компонент графа, а остальные символы имеют прожппй смысл. 187 7. Нарисуйте плоский граф (и ) 5), среди всршнп которого ровно 4 вершины со стапелями, пс прсвьппающими 5 8. Существуют лп б-связпыа плапарпыо графы? 9.
Доьажпта, что для связпога плоского (и, т)-графа с и ) 3, грапп которого па являгатся треугольниками, верно неравенства т:. 2и — -4. 10. Пакаллыа, что всякая плоскан триангуляция с и ) 3 вершинами имаот 2и — 4 грани. 11, Бсс ааршипы плоской триангуляции раскрашены произвольным образом в три цвета.
Грапь будем называть правильной, Рпс. У1Л если ее вершины окрашены в три различных цвета, Покажите, что число правильных граней четно. 12 Пусть в плоской триангуляции С существуют такие три вершины а, Ь, с, что граф 6 — (и, Ь, с) не является связным. Докажите, что тогда граф 6 содержит 3-цикл (а, Ь, с), пе являгощийся границей грани. 13, Для всякого связного плапарпого (и, т)-графа с и тв 3, обхват г~аторого рааап Ь тв 3, верно неравенство т(Ь вЂ” 2) < (Ь(и — 2).
Игпользуя зто соотпошоппс, докажите, что граф Петерсена псплапарап. 14. Убсдитась, чта рабсрпыа графы графов Ка и Кзз псвлапарпы, 15. 1(акис пз графов, пзобразксппглх па рвс. У1Л, являготся пленарными? 10. При каких и графы порядка 2и, изображаппые па рис. У1.2, явля~ется плапарпыми? Рпс. У 82 17. Изобразите стерсографпчсскоо проекции пяти платоновых тал. 18.
Дакажптс, что по существует плоского графа с пятью граннмя, облада~сщаго там свойством, чта любыс двс его грани имеют общее ребро. 188 И Пусть 6 — плоский двусвязпый граф. Докажите, что множество всех простых циклов, кан«дый нз которых ограничивает внутренн>ою грань графа 6 (см. теорему 37.7), образует базис циклов графа 6. 20. Плапарпый граф называется «невы>«пленарным, если < го можно уложить па плоскости так, что всс его всрппшы будут по>кать на граппцо одной грани (удобно в качестве такой грани брать внешшою грань). Докавппе, что следу>о>ц»е утверждения эквивалентны: 1] граф> 6 впспшсплапарсп; 2) гра4> 6', полученный из С добавлением позой вершины и соединением сс новыми ребрами со всеми вершинами графа 6, планареп; 3) кал«дый блок графа С внсшнепланарсн. 21.
Впешпепланарный граф называется лаксикальнь>м внешнеплапаряыл, если оп перестает быть внешнепланарпым прк добавлении любого ребра, Пусть в таком графе число вершин в ) 3 и и Рис. «'!.3 всо опи лежат па границе внешней грани. Покажите, что тогда граф имеет и — 2 впутрспнис грани. 22. Донажитс, что л>обой максимал>,пый внспшоплапарпый граф 6 с и ~ 3 всрп>янами имсот а) 2в — 3 ребра; б) по крайной море две вершины степени 2; в) к(6) = 2. 23. Какое ьшннмальноо число робор (вершин] необходимо удалить из куба 6>>, чтобы полученный граф стал пленарным? 24.
Дока кито изоморф>нз«г графов, изображенных па рис. >>1.3. Изоморфпы лп графы, гсомотрнчоски двойственные к нпм? 25. Пусть ялос>«ий гра4> 6 пе святеп. Покажите, что тогда ого «второй геометрически двопствспныйз граф 6** пс изоморфен графу 6. 28. Покажите, что граф, геометрически двойственный к колесу И>, являотся колесом. 27. Пусть плапаркый (п, т]-граф 6 таков, что двойственный к нему нзоморфен графу 6.
Показ«итс, что тогда т = 2я — 2. 28. Покажите, что планарный граф (без петель) является 2-связньгм тогда и только тогда, когда двойственный к нему 2-связеп. 29. Пайднте графы, геомстричоски двойственные к стсрсографпчсскпм проокцпям платоновых тол. 30 Воспользовавшись алгоритмом 7 укладки графа па плоскости, покажите, что граф К«пс плапарпый. 31. 6 помопрю алгоритма 7 постройте плоские укладки или установите нспланарность графов, изображенных на рис.
т'1.4. 32. «1сму равна искаженность графов К«, К«л и графа Петерсена? 33. Чему равно число с>«репцгваний графов К«, К«,« и графа Петерсена? 34. Докангпте илп опровергните утверждение; сг(6) =1 дли непланарного графа С тогда и только тогда, когда сузцествует такое ребро з, что граф С вЂ” е планарсн.
35. Позза китс чхс Г (Ка д) . ~ 2 1 ~ о) ~ З 1чзз)~~ ~ 4 33. Пайдитс толщину графов Кз, Кзл и графа Петерсена. 37. Покажите, что всякий непланарпый граф гомеоморфсн некоторому графу толщины 2. 38. Уложите куб Сз на торе. 39. Найдите род графа Петерсона. 40. Приводите пример графа рода 2. Рпс. У1.4 41. Покажптс, что род графа пе превосходит числа скрещиваний, т. е.
7(С) ( сг(6). Приведите примеры графов 6, для которых 1) 7(6) ( сг(6), 2) 7(6) = сг(6). 42. Покажите, что пс существует полпого графа рода 7. 43. 51озззпо зш уложить графы Кз и Кз,з па листе )з)ббиуса7 Глава 711 Обходы Основные положения этой главы связаны с существованием в графе эйлеровых или гамильтоповых целей и циклов. Подобные вонросы возникли в значительной мере под влиянием головоломок и игр. Тем не менее задачи, касающиеся эйлеровых и, в особенности, гамильтоновых цепей н циклов, чрезвычайно часто встречаются на практике.
Это случается, например, в ситуациях, когда качество выполнения некоторого комплекса операций (работ, мероприятий) существенно зависит от порядка, в котором ояи выполгмнотся. $ 43. Эйлеровы графы Все сказанное в этом параграфе о графах в равной степени относится к мультиграфам. Начало теории графов как раздела математики связывают с так называемая задачей о кеаигсбергских мостах. Эта знаменитая в свое время задача состоит в следующем. Семь мостов города 11бнигсберга (пыяе 11аликияград) были расположепы ва реке Прегсль гак, как изображено Ряс.
433 Рзс. 43.2 па рис. 43.1. Спрашивается„мо;кно ли, выйдя нз дома, вернуться обратно, пройдя в точности адик раз но каждому мосту? Сопоставим плану города граф С, вер|нпны которого соответствуеот четырем разделяемым рекой участкам суши А, В, С и й, а ребра — мостам, Этот граф (точнее, мультиграф) изобралтен на рис. 43.2. Таким образом, аа- 491 дачу о кепнгсбергских мостах моткпо па языке теории графов сформулировать так: есть ли в мультиграфе С цикл, содерягащий все ребра этого мультиграфа? Эйлер доказал неразрешимость задачи о кенигсбергских мостах. В своей работе, опубликованной в 1736 году, оп сформулировал и решил слодующу»о общую проблему г Рвс. 43.3 Рвс.
43.4 теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое ого ребро? Цикл в графе называется зйлеровызб если оп содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф можно нарисовать, пе отрывая карандаша от бумаги и пе повторяя линий. Папример, граф, изображенный на рис. 43.3, является эйлоровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1).
В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер. Помимо задачи о кенигсбергских мостах известен ряд других старинных занимательных задач (головоломок), решение которых сводится к выяснению вопроса «является ли граф эйлеровым?». В одной из них требуется обрисовать фигуру, именуемую саблями (знаком) Магомета (рис. 43.4), пе отрывая карандаша от бумаги и не повторяя линий. Теорема 43.1 (Л.
Эйлер, 1736 г.). Связный граф является зйлеровым тогда и только тогда, когда степени всех его вершт» четны. 9' Необходимость. Пусть С вЂ” эйлеров граф. Эйлеров цикл этого графа, проходя через кап»дую его вершину, входит в нее по одному ребру, а выходит по другому. Это озпа»ает, что кая«дая веригина инцидентна четному числу ребер эйлерова цикла, а поскольку такой цикл содержит все ребра графа С, то отс1ода следует четпость степеней всех его вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
