В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 51
Текст из файла (страница 51)
62.2, па котором отсутст- 276 вующпе ребра обозначены пунктиром) . 11о тогда 6(1, х, р, и, и) =Се, что противоречит условию. Полученное противоречие доказывает, что множество В независимо и, следовательно, С вЂ” расщепляемый граф. < Рис. 62.2 Как показывают примеры, граф, дополнительный к триангулированному, не обязательно сам является трнангулпровапным (напрнмер, граф 2К~ = С4 не является трнангулированным).
Следовательно, класс всех расщепляемых графов уже класса трнапгулированных графов. У 11 Р Д Ж Н Л 1.! И Л 1. Онрсделите хроматическно числа и хроматические индексы графов платоновых тел (рис. 1,7). 2. Приведите пример двух графов с совпадающими степенными множествами (степенными последовательностями) и различными хроматическими числами. 3. Покажите, что для множества вершин любого нспустого графа С существует такое разбиение У~ () Уз = УС, что верна равенство Х(С(У,)) + Х(С(Уз)) = д(С). 4. Опишите графы, хроматический индекс которых равен 2. 5. 1'раф называется критическим, если удаление любой из его вершин приводит к графу с мспьшвм хроматическим числом. Покажите, что К является критическим графом при и) 1, а ф— тогда и только тогда, когда и почетно.
б. Докажите, что всякий критический граф, являющийся к-хроматическим: а) свяаеп, б) пе имеет точек сочленения, в) степень каждой его вершины пе меньше чем Ь вЂ” 1. 7. Докажите, что любая последовательная раскраска полного ЬЧ1ольпо~ о графа есть й-раскраска, 8. Приведите пример графа, последовательная раскраска вершин которого пе является минимальной.
9, Докажите, что при последовательной раскраске графа используется ~го более чем 1+ шах 6 (П) цветов. Ныо 277 19. Покажите, что для раскраски нарты, получающейся при пересечении окруизностей па плоскости, достаточно двух цветов. 11. Докажите, что при любой правильной раскраске рвберно- го графа каждая вершина смежна не более чем с двуми вершина- ми одного и того же цвета.
12. Докажите, что для любого графа порядка л верны нера- венства 27и ( Х(С) + 2(С) ~( и+ 1, п( Х(С)у(С) =" (з+1)т/4. Приведите примеры графов, для которых указанные границы достижимы, 13, Покажите, что для связного графа С порядка з верно не- равенство 7(С, г) ~ 1(г 1).-ю 14. Докажите теорему 55.6. 15. Приведите пример полинома, удовлетворяющего условиям теоремы 55.6, но не являющегося хроматическим. 16. Докажите теорему 55.7. 17.
Предложите алгоритм для раскраски 2'(Кв) цветами ребер графа К„. 18. Используя упражнение 14 в главе 1У, докажите, что для любого двудольного графа С хроматический индекс т'(С) ра- вен Л(С). 19. Докажите, что всякая карта, не содержащая вершин степе- ни 2, имеет грань, граница которой содержит не более пяти ребер.
20. Докажите, что реберпый граф двудольного графа являет- ся совершенным. 21. Докажите, что теорема 56.3 о двудольных графах является следотвием теоремы 61Л. 22. Ие используя теоремы 62.5, докажите, что любой расщеп- лясмьзи граф является совершенным. 23. Докажпто, что в любом трпагулпрованпом графе есть дво симплициальные вершины, расстояние между которыми равно диаметру графа. Глава Х Ориентированные графы В приложениях часто приходится рассматривать графы с ориентированными ребрами, т.
е. ребрами, для которых указаны начало и конец. Примерами таких графов являются сети автомобильных дорог с односторонним дви>кением кли схемы программ для ЭВМ. Недостаточно простых (неориентированных) графов и для описания несимметричных отношений. Примерами подобных отношений могут служить порядок выполнения комплекса работ, задаваемый с помощью сетевого графика, или турнирная ситуация в спортивных соревнованиях.
В атой главе изучаются ориентированные графы. 5 63. Основные определения Пусть У в конечное непустое множество, Рз — его декартов квадрат. Ориентированный ераф (орвраф) — это пара (У, А), где А зз Уз. Элементы множества У называются вершинами орграфа 6 =(У, А), а элементы множества А — его дугами. Таким образом, дуга — это упорядоченная пара вершин.
Множества вершин и дуг орграфа 6 обозначаются через УС и АС соответственно. Число 1$'61 называется порядком орграфа С и обозначается через 161. Если х=(и, и) — дуга, то вершины и и и называются ее концевыми вершинами, причем и называется началом дуги х, а и — концом. Говорят, что дуга инцидентна каждой из своих концевых вершин. Говорят также, что дуга исходит из своего начала и заходит в свой конец. Дуга с совпадающими началом и концом, т. е. дуга вида (и, и), называется петлей. Можно определить ориентированные графы с несколькими дугами, имеющими общее начало и общий конец (мультиграфы).
Такие дуги называются параллельными. На рисунке дуга изображается направленной линией, идущей от начала дуги к концу. Направление линии обозначается стрелкой. Например, для графа 6, представ- гтэ ленного на рис. 83,1, рС = (, =-(хь хг, х, х, х ь 'с, хс, хб, хо., хг), причем хс п хг — параллельные дуги, а хс — петля. Воршппы орграфа назызакстся смелеиьсми, если они язлясотся концевыми для некоторой дуги. Дуги пазызаястся смежными, если онп пмосот общусо копцезусо но- шину.
зусо нор- П стьС вЂ” н у С вЂ” некоторый орграф. Ориесстировассссьслс маршрутом (или просто маршрусом) и графе С называется такая последовательность ссг о, ~=(с'о, хс, ис, хг,, х, п ) (1) тс ~ 5 его чередусощихся першин и, и б дуг х„что хс =(Ш-ь ис) (с гб о х, =1, сс). Такой маршрут назо- вем (ио, и„)-маршрутом. Верхб шины ио и п„назозем крайни- ми, а остальные вершины Рссс. 63д маршрута (1) — промежуточными (виутрешшми). с(лссссой маршрута назьспается число входящих в ного дуг. Марспрут пазьсзается и,спасо, если зсе входящие з него дуги различны, и путем, если псе зходясцие в пего першины, кроме, возможно, крайних, различны. Если и орграфе С нет параллельных дуг, то маршрут (1) моясет быть задан последозательпостью входящих в него вергпин: 5 =(ио, ис, ..., и„).
В лсобом случае марспрут можно задать последснателс,ностью входящих з него дуг: Я =(хс, хг, ..., х„). Маршрут называется ссиклсс'сеекссм, осли его первая и последняя зерспяны совпадают, 1(иклпчсскпй путь называется косстб1сом. Очеяпдпо, что лсобой (и, п)-маршрут при и Ф и еодержсет (и, и)-путо, а при и, = и — контур.
Последовательность (1) чоредусощпхся першин и дуг орграфа С, таких что т,=(в с, щ) плп хс=(иь ис с), называется полумаршрустом. Аналогично опрея лаются полссссепь, полупуть и полукоитур. Если в орграфе существует (и, и)-марспрут, то говорят, что гершнпа и достижима пз вершины и. Любая вершина считается достижимой из себя самой. Орграф называется ислысым (илп сильссосвязиым), осли лсобые дзе его вершины достижимы друг иа друга. Орграф пазызается одиосторосишм (плн одссосторо>сссесвяшсылс), если для лсобой нары его зерсппп по меньшей 280 мере одна достпноима из другой. Орграф называотсн слабььм (слабосвязным, связным), если любью две его вершины соединены полупутем.
Поскольку любая вершина графа достижима из себя, то одноворшинный граф одновременно и сальный, и односторонний, и слабый. Очевидно, что каждый сильный граф нвляотся односторонним, а каждый односторонний — слабым. Очевидно Рис. 63.2 также, что любые две песовпада|ощие вершины сильного орграфа принадленоат некоторому циклическому маршруту. На рис. 63.2, а изобраноен сильный орграф, на рис. 63.2, б — односторонний, а на рис. 63.2, в — слабый. Маршрут, содерноащий все вершины орграфа С, называется вставным. Ут в е р ж д е ни е 63Л.
Орграф является сильным тогда и только тогда, когда в нем есть остовный ииклический маршрут. С' Необходимость. Пусть С вЂ” сильный орграф н Т=(со, хн ип ..., х„, оо) — его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем впо его воршину и.
Так как С вЂ” сильный орграф, то существуют маршруты Т1 =(оо, ун ..., с), Тг=(о, гн, оо) ° Но тогда циклический маршрут Т'=(со, хь иь ..., х„, ио, ун, о, гн ..., ио) содержит большее, чем Т, число вергпин, что противорочит выбору маршрута Т. Следовательно, Т вЂ” остовный маршрут. Д о с т а т о ч н о с т ь. Пусть и и о — две произвольные воршины орграфа С, а Т=(он х, ..., о, у, ..., и, г, ..., оо) — циклический марптрут, Тогда и достинопма пз о с по- мощью маршрута (о, у, ..., и) — части маршрута Т,— а и из и — с помощью маршрута (и, г, ..., ио, х, ..., и). 4 281 Аналогично доказывается Утверждение 63.2.
Орграф является односторон ним тогда и только тогда, когда в нем есть остовный маршрут, Орграф является слабыл> тогда и только тогда, когда в нем есть остовный полумаршрут. Подграфьь и порожденные подграфы ориентированного графа определи>отея так же, как и для неориентированного. Так же определяются и операции над орграфами. Введем важное понятие сильной компоненты орграфа. Сильной (пли сильиосвягной) компонентой ориентированного графа называется любой его максимальный относитольно включения сильный лодграф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
