Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 31
Текст из файла (страница 31)
166 13.2. Свлвностпь и сильная связность г офв 167 Гл. 3. Теория графов и могрофов Цикл называется эйлеровым, если каждое ребро графа участвует в его образовании один раз; граф, содержащий такой цикл, называется эйлеровым. Теорема З.З. Граф 0 = (1т, Щ являетпся эйлеровым тпогда и только тогда, когда он связен и степень з(ив) каждой вершины о, б Ъ' — четпное число.
Простой цикл называется гамильшоновым, если он проходит через каждую вершину графа; граф, содержащий такой цикл, называется гамильшоновым. Теорема 3.3 определяет простой критерий выявления свойства эйлеровости для каждого графа. Для определения свойства гамильтонавости графа имеется следующее достаточное условие. Теорема 3.4 (Дирак). Если граф 0 = (1т, Щ, ]1т] > 3, является связным и степень каждой вершины ит б т' естпь з(щ) > -]1т], (З.З) где (] — ближайшее целое число, шо граф является гамильтоновым. Граф, состоящий из одной вершины, называется шривиальным. Удаление вершины из нетривиального графа 0 приводит к падграфу 0 1 о, содержащему все вершины графа О, кроме о, и все ребра графа О, не инцидентные о. Аналогично, удаление ребра х приводит к подграфу, содержащему все вершины (к оставному подграфу) и ребра, за исключением ребра х, т.
е. О'1х. Минимальную степень вершин графа обозначают б(О) = пни з(о;), щ е О. Если все вершины графа имеют одинаковую степень п, та такой граф называют регулярным графом степени и. Связностью графа Л(0) называется наименьшее число вершин, удаление которых делает граф несвязным, или тривиальным. Из этого определения следует, чта для любого графа Л(0) > > О. Полный граф К„становится тривиальным, если удалить п — 1 вершин, и поэтому д(К„) = и — 1.
Если Л(0) = и, то граф 0 называют п-связным. Реберной связиостпью Л(0) графа 0 называется наименьшее количество ребер, удаление которых привалит к несвязному, илн тривиальному графу. Для несвязного, нли тривиальнага графа Л(0 = О. ля любого графа 0 связность, реберная связность и минимальная степень связаны следующим неравенством: Х(0) < Л(0) < б(0).
(3.4) Среди всех графов с п вершинами и тп ребрами наибольшая связность равна О, если тп < п-1, и равна (2т/п], если т > п-1, где скобки [] означают, что берется целая часть выражения. Простые цепи называются реберио непересекающимися, если никакие две из них не имеют общего ребра. Если же у таких цепей нет и общих вершин, то они называются вершикно непересекающимися.
Пусть 0 — связный граф, а и, о — две различные его вершины. Множество ребер Е графа 0 называется и, о-разделяющим множесшвом в О, если любая простая цепь из и в о содержит ребро из Е. Множество вершин 1т графа, не содержащее и, о, называется и, о-отдсляющим множесшвом в О, если любая простая цепь нз и в о проходит через вершину 1т. Если некоторое и, и-разделяющее множество Е содержит и ребер, то число реберно непересекающихся простых цепей из и в о не может превысить тс, поскольку иначе число ребер из Е должно принадлежать более чем одной простой цепи.
Если и, о-разделяющее множество имеет наименьшую мощность, то число реберна непересекающихся простых цепей между и и о равна к. Те о р ем а 3.5. Максимальное число реберно непересекающихся простпых цепей соединяющих две различные вершины и, и связного графа О, равно минимальному числу ребер в и, о-разделяющем множестве. Теорема 3.6. Максимальное число вершинка непересекающихся простпых цепей, соединяющих две различные несмежные вершины и, о графа О, равно минимальному числу вершин в и, иотпделяющем миожестпве.
Теорема 3.7. Граф п-связеи тогда и тполько тпогда, когда любая пара его вершин соединена по крайней мере п вершиино непересекающимися цепями. Теорема 3.8. Граф и-реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере и реберно непересекающимися цепями. Теорем а 3.9 (Менгер). Для любых двух множеств вершим 1т~, тд (1т~, 1тд ув йт, т' П1тд = Ы) наибольшее число непересекающихся цепей, соединяющих 1т и 1тд, равно наименьшему числу вершин, отделяющих 1е и 1тд. Теоремы 3 6-3.9 определяют зависимость связности графа ат числа непересекающихся цепей. Эту зависимость впервые исследовал Менгер. Разделяющим множестпвом связного графа О называется такое множество его ребер, удаление которых из 0 делает его несвязным.
Например, множества (рт, рэ, рэ, рз) на рис. 3.5, а является разделяющим, и его удаление приводит к образованию двух компонент связности. Разрезом называется такое разделяющее множества, которое ие имеет собственного разделяющего подмножества. Множества 1трт, рэ, рв, рзу не является разрезом, поскольку она содержит раз- Гл.3. Теория графов и мографое 168 169 т э е б б т а в 1о 1 8(С) = 1О Рис. З.б г э э э о т Э Э 1О абауе аЬ Ьс»Фее Ьс»Фе с»Ф сбеаЬ с»Феа с»Фе »ФеаЬ »Фельс Неа еаьс»Ф еаЬ еаьс еа »Фе,з »Фе,2 ае,1 хеуи хзуиз »Фт 4 »Фт,э »Фг,2 »Фт,» уизх уи »Фе з »Фе 2 аел зхгуи Фуи Аэе Аэ,э »Ф»е,» а»э 2 »Ф»э 2 иэхту изхФ 1О йе,з — — ЬаЬ, хеп»Ь, хеуип, »Фт 2 = уге уизь тоське »Фт,» ю пеьс, уипс, уизхр, »Фе,э = эьа, зхет, пс»Феа, де,е = псб„зхр»Ф, зхФуг, бе,э = ФтЬ, Фуип, р»Феаь, 4э 1 = ге иеь ипс»Фе, »Фее,» ю ипс, изхр, геаЬс, ае,э = йа, хгт, хр»Феа, де,е = хрН, хеуг, Ьаьс»Ф, »Фт,э = тЬ, уип, угеаЬ, ае,» = зь, пс»уе, зхр»Фе, »Ф»,» = пс, зхр, зьаьс, »Фе,т ю Фт, рбеа, Фугеа, »Фэе =р»Ф Фут Фтьау »Ф»о,э ю ип, геа»Ф, изьаь, бед = й, хр»Фе, хеуге, йэ,» =хр, Ьаьс, хстЬс »)2,2 = т, угеа, уизьа »Фт,е = уг, п»ЬС»Ф, уипс»Ф, »Фе,э = и, зьаь, зхзгпЬ цел = р»Фе, Фуге, Фуиз)е, »Фэ,» =р, Фпеьс, Фуипс, »Феэ,э = геа, изьа, изхегп, »Фее,е = г, ипсд, изхра.
деляюшее подмножество (рт, ро, рб). Это подмножество не имеет собственных разделяющих подмножеств и поэтому является разрезом. Разрез состоящий из одного ребра, называется мосгпом (см. рис. 3.5, б). Иногда разрез называют копи»слом. Рассмотрим ориентированный граф и его свойство быгпь сильно соязнььи.
ИутПСМ НаЗЫВавтея ПОСЛЕдааатЕЛЬНОСтЬ дуГ (б1, 62, .. ч б ) ВИда б; = (и;, и;+1), 2 = 1, 2,..., и. Вершины пути имеют степень, равную 1 или 2. Вершина и; со степенью, равной 1, называется концевой; при этом вершина и1, коинцидентная дуге 6~, называется начальной, вершина и„+1, коинцидентная дуге б„, — конечной. Число дуг, образующих путь, называется длиной пути.
Контуром называется путь, концевые вершины которого совпадают. Все вершины контура имеют степень л(и;) ) 2. Путь называется составным, если в нем повторяется хотя бы одна дуга. Граф называется слолсным, если в нем повторяется хотя бы одна вершина, и простнььи — в противном случае. Граф С = (У, У) называется сильно связным, если любая пара вершин соединена путем. Максимальный по включению вершин сильно связный подграф графа называется его компонентой сильной связности.
Граф называется несильно связным, если число его компонент сильной связности больше 1. 2 Рассмотрим алгоритм определения ю сильной связности графа и числа его ком- понент сильной связности. Этот алгоритм б так же, как и алгоритм определения связности графа и числа компонент связности, рассмотренный для случая неориентированного графа, основан на использовании теорем 3.1 и 3.2. $»Ф 4 Пример 3.2. Определим сильную сввэность ориентированнога графа Петерсена (рис. З.б), ма- Рис.
З.б грива сменности воторого имеет следуюший вил: б 3.2. Соленость и сильная сеязность графа Максимальная степень, в воторую необходимо возвести матрилу сменности графа Я(ФФ) для определения компонент сильной связности, на основании теоремы 3.2 равна диаметру»Ф(0) этого графа: »Ф(С) = шах яппФь(э„о ), Сз Ь где Ф(о„о ) — длина вуги от вершины щ до вершины е . В рассматриваемом случае диаметр Ы(С) графа С равен 5, Матриву лостииимасти 11(С) вычисляем вав 1 (Я(ФФ)]: ш1 П(а) = ~ ь' = б + а' + ьз + а» + а' = $3.3. 77икломаптика и коцикломаятика Гл.3. Теорш графов и мографов 170 171 Немваненте сильней связнастн в матрнле дестнинместн соответствует ледматрила малснмзльнете размера, ваидый элемеят ветарей не равен О. элементы, вевазывмошне связь менду этими ведматрнламн, метут Выла не равны О.
В давнем лрвмере имеем лве вамлененты сильней свявнести с неснтелямн сеответственне [1, 2, 3, 4, 5) н (6, 7, 8, 9, 10). Сетью называется ориентированный граф 0 = (7; У), в котором выделены два множества полюсных вершин, 1т+ и У, таких, что из каждой вершины о,+ б 1т+ дуги только исходят, в каждую вершину о, б 1т дуги только входят и каждая вершина о; б б У '1 (1т+ 0 1т ) коинцидентна как входящим, так и исходящим дугам.
Сопоставим каждой дуге положительное число, определяющее ее "пропускную способность". Тогда можно сформулировать еше один вариант теоремы Менгера для такого взвешенного по дугам ориентированного графа. Теорема 3.10. Максимальный поток через сеть равен минимальной пропускной способностпи ее разреза. Алгоритм определения максимального потока рассмотрен в 3 3.5. 33.3. 11ккломотика к коцикломаткка Для исследования циклов в графе используют цикломатпическую матприцу С(0) = [с;т): каждому циклу графа взаимно однозначно сопоставляется вектор-строка матрицы С(0); каждый элемент этой строки определяется как 1, если у-е ребро входит в 1-й цикл, О в противном случае. Множество С(С) всех векторов, каждый нз которых соответствует одному циклу графа О, образует векторное пространство, называемое пространсптвом циклов графа О.
Прн этом выполняются следующие условия: 1) для любых двух циклов В;> В; б С(С), В;Г1 В, ф 8, сушествует некоторый третий цикл (В; йт В.) е С(С), где йт означает поразрядное сложение по модулю 2; 2) сложение по модулю 2 обладает свойством коммутативности, т. е. для любых двух В;, В б С(0) В* ® Ву = Ву ® Вб 3) сложеяие по модулю 2 ассоциативно, т. е. для любых В;, В,, Вл Е С(С) (В;ЕВ1) ЕВЛ= В;Е(В1ЕВл). Базисом векторного простпранстява называется всякая система линейно независимых векторов, порождающая данное пространство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
