Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов
 Скачать 1.41 Mb.
|
|
Код Прюфера Упаковка дерева. Помеченные деревья порядка n переводятся в последовательность чисел по алгоритму: 1. Выбирается лист с минимальным номером. 2. Лист и инцидентное ребро удаляются из дерева, в последовательность Прюфера добавляется номер смежной удаленной вершины. 3. Если в дереве больше двух вершин, то переходим в пункт 1, иначе – выход. Распаковка дерева. Отметим, что код содержит элементов на 2 меньше количества вершин восстанавливаемого графа. 28 Обозначим P = (p 1 , p 2 , ..., p n – 2 ) – последовательность Прюфера, N = {1, 2, ..., n}. 1. Выберем минимальное число v из N, не содержащееся в P. 2. Соединяем ребром вершину с номером v и вершину, соответствующую первому числу из P. 3. Удаляем v из N, удаляем первое число из P. 4. Если в N осталось два числа – соединяем ребром соответствующие вершины, иначе – пункт 1. Кодирование Прюфера задает взаимно-однозначное соответствие между множеством помеченных деревьев порядка n и множеством числовых последовательностей, состоящих из n – 2 натуральных чисел из набора {1,...,n}. Пример Для кодирования дерева (рис. 2.20, а) применим алгоритм Прюфера, заполним последовательность P = (p 1 , p 2 , p 3 , p 4 , p 5 , p 6 , p 7 , p 8 ). Выберем лист с минимальным номером – 2, в последователь- ность Прюфера добавляем номер смежной с этим листом вершины – 1. Тогда имеем: P = (1, p 2 , p 3 , p 4 , p 5 , p 6 , p 7 , p 8 ). а б Рис. 2.20. Применение алгоритма Прюфера. Упаковка дерева Удаляем из дерева этот лист и инцидентное ребро (рис. 2.20, б). Подобным образом найдем следующий лист с минимальным номером – 5, в последовательность Прюфера добавляем 1: P = (1, 1, p 3 , p 4 , p 5 , p 6 , p 7 , p 8 ). Повторяя данную процедуру, получим последовательность (1,1,4,4,4,3,3,1). Теперь распакуем дерево. Имеем последовательность Прюфера (1,1,4,4,4,3,3,1), 29 содержащую 8 элементов, значит, восстанавливаемый граф будет содержать 10 вершин: N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Выберем минимальное число из N, не содержащееся в P, это число 2. Соединяем ребром лист с номером 2 и вершину 1, соответствующую первому числу из P (рис. 2.21, а), и удаляем из P число 1, из N – число 2. Снова выберем минимальное число из N, не содержащееся в P, это число 5. Соединяем ребром вершину с номером 5 и вершину 1, соответствующую второму числу из P (рис. 2.21, б). Повторяем данную процедуру, пока не останется в N два числа 1 и 10, соединяем их ребром и получаем исходный граф (рис. 2.21, в). а б в Рис. 2.21. Применение алгоритма Прюфера. Распаковка дерева 2.6. Планарность, раскраска графов. Сети и потоки Определение. Изображение графа плоскостной диаграммой называется укладкой графа на плоскость. Граф, изображенный на плоскости, называется плоским, если его ребра не пересекаются в точках, отличных от вершин графа. Свойство «быть плоским» может не сохраняться при переходе к изоморфному графу. Принципиальный вопрос, на который нужно отвечать при решении задач типа прокладки коммуникаций, – это имеет ли данный граф хотя бы одно плоское изображение? Определим класс графов, для которых ответ на этот вопрос положителен. Определения Граф называется планарным, если он изоморфен плоскому графу, а его укладка – плоской реализацией планарного графа. 30 Конечная область, ограниченная простым циклом в плоском графе и не содержащая внутри себя других циклов, называется внутренней гранью плоской реализации графа. Бесконечная область вне плоского графа называется внешней гранью плоской реализации графа. Множество граничных точек грани называется ее краем. Пример На рис. 2.22 показан граф с 4 гранями. Рис. 2.22. Плоский граф Формула Эйлера.Пусть G = (V, X) – связный планарный граф, n V = , m X = , тогда для любой геометрической реализации графа на плоскости справедлива формула 2 = + − r m n , где r – число граней. Если граф имеет k компонент связности: 1 + = + − k r m n Следствия 1. Формула Эйлера справедлива для геометрической реализации графа на сфере. 2. Для любого выпуклого многогранника 2 = + − r m n Теорема о связи числа ребер с длиной минимального цикла Пусть G = (V, X) – связный планарный граф, n V = , m X = , в котором нет циклов длины меньше l ( 3 ≥ l ), то ( ) ( ) 2 2 − − ≤ l n l m 31 Замечание. Если G – простой связный планарный граф, то в нем нет циклов длины меньше трех, поэтому ( ) 2 3 − ≤ n m Теорема о непланарности графов 5 K и 3 , 3 K В графе 5 K 3 , 10 , 5 = = = l m n . Если он планарен, то ( ) 2 3 − ≤ n m , т. е. 9 ≤ m – противоречие. В графе 3 , 3 K 4 , 9 , 6 = = = l m n . Если он планарен, то 8 4 2 = × ≤ m – противоречие. Определения Подразбиение ребра { } 2 1 , v v – удаление этого ребра, добавление новой вершины v к V и двух новых ребер { } v v , 1 и { } 2 , v v к множеству X. Стягивание смежных вершин – операция удаления ребра { } 2 1 , v v и замена двух вершин 1 v и 2 v одной вершиной, которая соединяется ребрами со всеми вершинами графа, с которыми были смежны вершины 1 v и 2 v Граф G называется подразбиением графа G 1 , если он может быть получен из G путем конечного числа подразбиения ребер. Из определения следует, что граф 1 G будет отличаться от графа G только вершинами степени 2. Замечание. Стягивая любые две смежные вершины планарного графа, вновь получим планарный граф. Если же дан непланарный граф, то стянув две или несколько вершин можно получить планарный граф. Определение. Два графа G и H называются гомеоморфными, если они могут быть получены друг из друга с помощью операций подразбиения ребер или стягивания вершин степени 2. Таким образом графы гомеоморфны, если существуют их подразбиения, которые изоморфны друг другу. Гомеоморфизм графов является отношением эквивалентности. Замечание. Гомеоморфными являются, в частности, любые две простые цепи, любые два простых цикла. 32 Пример На рис. 2.23 показана операция подразбиения ребра Рис. 2.23. Подразбиение ребра На рис. 2.24 показаны пары гомеоморфных графов. а б Рис. 2.24. Гомеоморфные графы Рассмотрим плоский граф G с пятью вершинами (рис. 2.25, а). Если добавить к нему ребра {1,3} и {1,5}, то полученный новый граф G (рис. 2.25, б) тоже будет плоским. К этому графу не удается добавить ни одного ребра так, чтобы новый граф тоже был плоским. а б Рис. 2.25. Гомеоморфные графы Определение. Плоский граф называется максимально плоским, если невозможно добавить к нему ни одного ребра так, чтобы полученный граф был плоским. 33 Следовательно, граф на рис. 2.25, б – максимально плоский. Каждая грань в плоском представлении максимально плоского графа имеет три вершины. Поэтому максимально плоский граф называют триангулированным. Определение. Операция добавления новых ребер, в результате которой в плоском представлении каждая грань имеет ровно три вершины, называется триангуляцией графа. Определение. Двойственный граф G' к планарному графу G – это граф, в котором вершины соответствуют граням графа G; эти вершины соединены ребром, только если соответствующие им грани графа G имеют общее ребро. Пример Двойственны друг к другу графы куба и октаэдра. Поскольку двойственный граф зависит от способа укладки, к одному и тому же планарному графу могут существовать несколько двойственных (неизоморфных). Также заметим, что каждому ребру, не входящему в цикл, в двойственном графе соответствует петля. Пример На рис. 2.26, а , б показаны графы (сплошной линией) и двойственные к ним (пунктирной линией). На рис. 2.26, б для двух изоморфных графов приведены двойственные, которые не изоморфны, поскольку верхний двойственный имеет вершину степени 6 (внешняя грань), а нижний имеет наибольшую степень 5. На рис. 2.26, в показано дерево и двойственный к нему граф, который имеет только одну вершину (так как у дерева одна грань) и петли, количество которых равно количеству ребер дерева. 34 а б в Рис. 2.26. Двойственные графы (а); неизоморфные двойственные графы (б); дерево и двойственный ему граф (в) Критерии планарности графов 1) Уитни: граф планарен, если у него есть двойственный. 2) Понтрягина–Куратовского: граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных K 5 и K 3,3 (т. е. в нем нет подграфов, полученных подразбиением ребер из K 5 и K 3,3 ). 3) Вагнера:граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к K 5 или K 3,3 Пример Рассмотрим граф Петерсена (рис. 2.27), он не содержит подграфа, изоморфного K 5 и K 3,3 , однако он непланарный, что следует из критерия Вагнера: граф приводится к графу K 5 после стягивания ребер r 1 , r 2 , r 3 , r 4 , r 5 35 Рис. 2.27. Граф Петерсена Покажем, что граф на рис. 2.28, а непланарен: для этого выделим подграф (рис. 2.28, б), который гомеоморфен графу K 3,3 (рис. 2.28, в). а б в Рис. 2.28. Пример непланарного графа Замечание. Любой конечный граф допускает геометрическую реализацию в трехмерном пространстве. Доказательство. Пусть ( ) X V G , = , { } n v v v V , , , 2 1 K = , { } m x x x X , , , 2 1 K = . Проведем в трехмерном пространстве прямую, на которой отложим точки n a a a , , , 2 1 K , через эту прямую проведем m полуплоскостей, и каждую кривую k l , соответствующую ребру k x , расположим в своей полуплоскости. Получим геометрическую реализацию графа. Раскраска графов Определение. Раскраска графа – это разбиение элементов графа на множества (называемые цветами). Обычно цвета – это числа t ,..., 1 . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения на множестве { } t ,..., 1 36 Множество объектов, окрашенных в один цвет, называется одноцветным классом Определение. Правильная раскраска вершин в t цветов – это разбиение V= V 1 ∪ V 2 ∪ …∪ V t такое, что I 1 = i i V = ∅, { } t i ,..., 1 ∈ , но каждое из V i не пусто, при этом случае никакие две смежные вершины не раскрашены в один цвет. Граф называется t-раскрашиваемым, если его можно правильно раскрасить t цветами. Наименьшее число из t при условии правильности раскраски называется хроматическим числом χ(G). Пример Граф K n – n-хроматический, любой двудольный граф, а также любое дерево – 2-хроматические. Если в графе G = (V, X) t v V v = ∈ deg max , то граф не более чем (t+1)-раскрашиваем. Любой планарный граф без петель не более чем 5-раскрашиваем. Определение. Правильная раскраска ребер в γ цветов – это разбиение множества ребер X= X 1 ∪ X 2 ∪….∪ X γ , где I 1 = i i X = ∅, { } γ ∈ ,..., 1 i и каждое X i образует паросочетание (произвольное подмножество попарно несмежных ребер графа) в G, т. е. никакие два смежных ребра не получают в ней одинакового цвета. Наименьшее из γ при условии правильности раскраски называется хроматическим индексом γ(G). Для хроматического индекса справедливы верхняя и нижняя оценки: ) ( 5 , 1 ) ( ) ( G s G G s ≤ γ ≤ , v G s V v deg max ) ( ∈ = , где v deg – степень вершины v. Раскраска, при которой окрашиваются и вершины, и ребра, а правильность означает принадлежность двух инцидентных элементов различным одноцветным классам, называется тотальной раскраской в τ цветов. Наименьшее число цветов составляет тотальный минимум 37 Раскраска называется свободной, если не все цвета из множества цветов используются. Две такие раскраски различны, если два используемых набора цветов различаются хотя бы одним цветом. Пример На рис. 2.29 показаны различные раскраски. Рис. 2.29. Раскраска графов Определение. Граф называется критическим, если ) ( ) ( G G s γ < и ) ( ) \ ( G x G γ < γ для любого x из множества X. Правильная раскраска ребер графа в ) (G γ – 1 цветов называется напряженной , если одно ребро остается не раскрашенным. Если t(G) = 2, то ) (G γ = s (G). При этом в графе существует паросочетание, охватывающее все вершины наибольшей степени. Теорема о четырех красках Данная теорема утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, т. е. стыки нескольких областей в одной точке общей границей для них не считаются. Эта теорема была сформулирована Фрэнсисом Гутри в 1852 г., однако доказать ее долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырех красок. Задача раскраски карты на плоскости эквивалентна задаче на сфере. Для простых карт достаточно и трех цветов, а четвертый цвет начинает требоваться, например, тогда, когда имеется одна область, 38 окруженная нечетным числом других, которые соприкасаются друг с другом, образуя цикл. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX в., но доказательство теоремы для случая четырех цветов столкнулось со значительными трудностями. Теорема о четырех красках была доказана в 1976 г. К. Аппелем и В. Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1 936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих 1 936 карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 г. Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 г. доказательство было проделано Д. Гонтиром с использованием специального программного обеспечения (Coq v7.3.1). |