Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 35
Текст из файла (страница 35)
а) Изобразить граф Кз,з. б) Сколько ребер пмеет граф К к? $2. Маршруты, циклы и связность Обратим сейчас вкпманпе на понятие маршрута в графе. Зкачлтельная часть теорпк графов и ее прпложевпй закпмается вопросамп существованля и свойств маршрутов. Некоторые важные свойства вытекают пз следующих определений.
Определекпе, а) Пусть С ()т, Е) — граф. Мпрнсрутом длины й в графе С ка и в и называется последовательность <и„, иь ..., и,> вершпк (кеобязательпо различных) и,ы )т талях, что ис и, и,=ю, а (и, ь и,)ыЕ для всех 1 -1, ..., й. Маршрут называется замкнутым, еслп ис и,. Маршрут называется цепью, если все его вершпны различны. Замкнутая цепь называется циклом.
Цикл называется прость и циклом, есл~ толыго иа им а остальные и, различны. б) Если существует маршрут из и в кл, и, илж 'т', то говорят, что й достилеима пз и. в) Граф без циклов называется ациклическим. Циклы и длины цпклов былл определены для случая подставовок в т 4 гл. 3. Заметкм, что понятие замкнутостп.
в сущности, соответствует своему названию. Определекие. а) Граф С (т', Е) называется связнылц если каждая пара различных вершпп может быть соедпкепа маршрутом. б) Дереволг называется связный ациклпческпй граф. в) Корневым деревол~ называется дерево с выделенкой вершиной, называемой корнем. г) Остовнылс дерееолг для С ()т, Е) называется остоввый подграф, являющийся деревом. В 2 1 мы отмотплк, что вычпслення с матрпцей смежности обкаружпвают важную пкформацпю о прпроде графа.
Следующие результаты являются прпмерамп внутренкпх связей между алгеброй и топологией в теорпи графов. В прпведепяой клже теореме п ее следствцях степеяк А* вычисляются в М'(п, Е), а не в М'(и, В). Следовательно, в А' могут возникать числа, большпе чем 1. 224 Т е о р е м а. Пусть А — матрица смежности графа С (т', Е) и )Р) к. Тогда (А")е есть число маршрутов длины к от о< к он Доказательство.
Будем использовать индукцию по )д. Для ед 1 маршрут длины 1 как раа является ребром С. Следовательно, результат теоремы прн )д-1 вытекает иа определения А. Пусть (А' ')е ив, А„ао, тогда (А")ц (Аа 'А)ц А', иматр д-а Пусть результат имеет место для ед — 1. Тогда, если и„— элементы матрицы А'-', то ич — число маршрутов длины ед — 1 от о, к о;, по определению а„— число маршрутов длины 1 от о, к оь Следовательно, ииа„— число маршрутов длины ед пз о< к о„где о, есть предпоследняя вершина маршрута. Отсюда следует, что чд ,.; и~-,ад1 д-1 есть чпсло маршрутов длины ед от о, к оь Это завершает доказательство.
у Следствие. а) Иортарут от о, к о, (ань/) в С ()т, Е) суецествует тогда и только тогда, когда (1, ))нй элемент матрицы корлдка к Х к (к ! Е! ): А+А'+,+А" ' не равен нулну. б) Если не использовать условие 1дь 1, то требуемая матрица имеет вид А + АУ+ + А"-'+ А". Доказательство. а) Пусть <о„ои ..., о,> — маршрут пз о, в о, в С. Если не существует повторяющихся вершин, то (так как ~У) к) маршрут содержит не более и — 1 ребер, и необходимое утверждеппе следует пз теоремы.
Пусть существует повторяющаяся вершина. Тогда маршрут имеет впд (ои,е ое,..., ое,...а идте аанннутыа карату 225 15 д. кун, г. ьееа Если мы удалям все такие замкнутые маршруты, то за. дача сведется к предыдущему случаю, когда вершины не повторялись. Таким образом, в одну сторону требуемый результат иолучен. В обратную сторону рассуждения очезидпы. б) Если разрешается ( ), то существоваиие маршрута из и, в и, влечет то, что существует последовательность (иь ип ..., и,>, Если не существует повторяющихся вершин (за исключеппем, возможно, случая и, и,), тогда марщруты состоят из болев чем л+ т вершин (не более я ребер).
Следователько, (г, у)-й элемент матрицы Х А' ве равен кулю. Тогда при !И л отсюда ь 1 следует А(В»(Е)) А(В(Е)) ~/ А(В»(Е)) ~/ ° ° ° ~/ А(В" (Е)) ° ~/ А(В»(Е)), А(В*(Е)) = У Ц А(В(Е)) У ... У А(В"-'(Е))- ° ~/ А(В" (Е)).У з-г Напомним, что для произвольного бинарного отношения В величина В+ определялась как В+- и В', з з к если В ж УХ У при ! И я, то отсюда следует (с учатом т 1 гл.
6), что А(В») А+(В) ~/ А (В'), а 1 Аналогячно А(В»)-А»(В)- ~/ А(В'), з-» В атом параграфе для упрощения обозначений будем теперь обозначать А(В'(Е)) через А(В'), А(В+(Е)) через А(В+), а А(В*(Е)) через А(В*). Алгоритм Уоршолла требует 4пз операций для определения А(В+), тогда как при помощи приведевяых выше соотношений требуется 4и' — 7из операций. Можно получить и другие, 22с еще болев эффективные алгорптмы для большпх значений и.
Матрицу С А(В») называют матрицей свези, свлвности или достижимости графа С ° ()т, Е). Маршрут кз о< к о, (! «»)) существует в С тогда и только тогда, когда (й 1)-й элемент из С равен 1. Граф С является связным тогда и только тогда, когда Со 1 для всех 1 ~ 1, 1 ( п. Важные свойства отношения В» могут быть сформулированы следующим образом. П р е дл о ж е н ив, В» — отношение эквивалентности на У. Доказательство. Так как по определению В» является рефлексивным замыканием В, то необходимо только проверить симметричность В», Выполнение оВ»и» влечет существование маршрута (о, он ..., о„ш> ат о кювС,т.э.
[о, о,] «а Е, [о„о«) «в Е, ..., [о„, ю) ю Е. Следовательно, [у» о»]«аЕф [о», о»-~]жЕ» ° ю [о2,'о1]»иЕ, !ои о]шЕ. Таким образом, (иФ у, о -н ° ° о«ои о> есть маршрут из и в о в С, откуда следует шВ»о. У Отношение В» определяет важный класс подграфов, который сейчас будет определен. Будут также даны некоторые сопутствующие понятия; они будут важны в дальнейшем, когда будут обсуждаться «пересечения» графа. Определение. Пусть (Рк 1<1<р) — разбиение графа, определяемое отношением В».
Тогда говорят, что р — число связности С. Подграфы (К, Е,), порожденные классами эквивалентности, называют коннонентами связности ерафа С. Лесом называется граф, в котором каждая связная компонента является деревом. Остовный лес для граФа С (У, Е) — это совокупность вершин разъелинепньж деревьев Т, ()»о Е,) таких, что т' () '»'» и Е, ~ Е для всех й (Разъединенность вершин означает, что )»,й )т, .-й~ пригн).) Рисунок 7.6 иллюстрирует вышеупомянутые понятия для графа прп р ° 2. 15» 2ЬЧ Упражнение 72, 1. Пусть С (У, Е), где У Ьь из, из, сз) и с - «иь из), [иь оз], [сз, М, 0~з, сз)1 ос ол Ослюсный лес еле врагова Рвс.
?.е Используя матрицу смежности С, определить: а) число маршрутов длины 2 иэ из в из,. б) число маршрутов длины 3 иэ и~ в сз, в) является лн С связным. 2. Изобразить остовные деревья для графов из упражненпя 7,1, 3. 3. Дать матричную характеристику ациклнчности в графе. 5 3. Пленарные графы Исторически во многих работах по теории графов рассматривают специальный класс графов, который может быть аккуратно представлен рисунком на плоскости Из. В этом параграфе мы рассмотрим три важных результата, касающихся таких графов.
3.1. 'Георемы Эйлера и Куратовсного. Определение. а) Граф С называется ялаиаряььв, если он может быть изображен ва плоскости так, что его ребра ве 228 пересекаются «). Такой рисунок называют каргой С. б) Карта С называется связкой, если С свпзеп. э' Прпмер ЗЛ. 1. С-((оп иэ, из, пе), ()из, ит), )оь оз), [оо ое), )оп оэ), )оэ, ие), )из, ие))). Иаображение и соответствующая карта С поквааны на рис, 7.7; следовательно, С-планарный граф.
ое оэ У, оэ Иэображение бс Фарта С Рис. 7.7 2. Графы, изображенные на рис. 7.8,а и о обычно обозначают через Ке и Кз,з соответственно. Позднее мы рассмотрим доказательство тога факта, что вти графы не являются планарвыми. Х Ркс. 7.8 Карта делит Вт на еобластиз; пропллюстрпруем зто в следующем примере. Пример 3.2. Рассьсотрпм карту, изображенную на рис. 7.9. Она делит Кэ ва четыре области; гь гз и гз являются ограниченными областямп, а ге-енеогранпченнаяз область. В оставшихся параграфах будем обозначать множество областей данной карты через йс, ') Такой треф, изображеииый аа плоскости, вазызаетсл ало ским ерафом.— Бримеч, ред, Тс о р е и а Э й л ер а.
Для проивволъяой свявяой ко рты !У! — 1Е1+ 1Ж1 ° 2. Докааательство. Пусть !У1 7. Тогда очевидно, что 1Е1 О и 1Я1 1. Следовательно, формула справедлива для 1У! — 1. Рассмотрим два воаможныт способа расширения данной карты. ~йоВов > ~ ройрв е /Фйао Вершина Рве. 7йо Рве. 7.9 $) Добавим новую вершину п присоединим ее к су» ществующей карте. 2) Соединим две существующие вершины.
Покажем, что вначение 1У! — !Е1+1Ж1 инвариантно относительно обоих способов расширения. В первом случае добавим новую вершину так, каь., например, вто сделано на рис. 7ЛО. Этот процесс увеличивает 1У! иа 1 и !Е1 на 1, однако !Я1 остается тем же самым, вследствие чего вначение 1У1 — 1Е1+1Ж1 не иаменяется. пе Рас. 7йт Рпс, 7ЛЗ Во втором случае соединим две вершины, как, например, на рис. 7,11, Тогда 1У! остается тем же самым, 1Е1 930 возрастает па 1, а )Я1 уменьшается на 1; следовательно, значение 1))! — 1Е1+ 1Я1 опять остается неизмевяым. Все карты могут быть получены из случая 11)1 *1 путем выполнения 1) и (нлн) 2); если необходвмо, то процедура повторяется. Следовательно, так как 1))1 — 1Е!+1Я! 2 при 1))1 1, а значение 1))1 — 1Е1+1Я1 остается инварнантвым при выполнении 1) и 2), то мы имеем 1)'! — 1Е1+ 1Я1 2 для всех связных карт.
Очевидно, что каждая область карты ограничена замкнутым маршрутом. Ниже приведены два простых результата (один касается ограничивающих замкнутых маршрутов). Этих результатов оказывается достаточно для доказательства того, что Кь и Кзз не являются плаварными. Определен не. Пусть С (1Г, Е)- планарный граф. Для карты С определим степень Ь, области г как длину замкнутого маршрута, ограннчивающего г. е Пример 3.3. Для карты, изображенной ва рис.7.12, имеем <оь оь, им оь, оз, о~> — граничный замкнутый маршрут для гн а <о~, оз, оь, о~> — граничный замкнутый маршрут для гз.
Следовательно, Л) ~ 5, Ь), 3. е Предложение. Пусть С (р; Е) — пленарный ераф. Тогда а) 2~ Ь, 21Е1 дел любой карты С; )ел б) если 11)1 >3, то 1Е)А З!')"1 — 6. Доказательство оставляем члтателю в качестве упражнения. Предложение. Графы Кь и Кьз не яеляютсл планарныли. Докааа тельство. Докажем, что Кь не является планарным. Если Кь— планарный граф, то кз предыдущего результата следует, что 1Е1а'311)! — 6.
Тогда для графа Кь с 1Е1 ° 10 и )Р1 5 цмеем 10ч*15 — 6 9, что неверно. Таким образом, предположеяве, что граф Кь пленарный, неверно. Докажем теперь, что Кь,ь по является планарным. Предполагая противное, имеем ~~ Л) 21Е1. Однако в )ест Кь,ь нпкакпе тря вершпвы не связаяы одна с другой; следовательно, Ь,Рь 4 для всех гееЯ. Из Формулы Эйлера 1Я1 2+ 1Е1 — 1))! 2+ 9- 6 5; следовательно, Х 6,~5ь4 20. Таким образом, 21Е1 ~20, откуда твз2 231 !Е[ > «О. Поскольку последвее перавевство неверно, то граф Кз.з ке явлветсн плавариым. г' Графы Кь и Кзз явтерескы тем, что оки являются существепво «едпкствепвымвз веплапариыми графамп. Все другпе пеплаваркые графы имеют подграфы «подобпыез или Кь, или Кзз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
