Свойства деревьев

1. Граф является деревом тогда и только тогда, когда каждая пара вершин в нем соединена одной и только одной простой цепью.

2. Удаление всякое ребра в дереве приводит к увеличению числа компонент связности.

3. Дерево с p вершинами всегда имеет (p-1) ребер.

1. Если G - лес, р - вершин и к компонент связности, то G имеет р-к ребер.
2. В каждом дереве существует по крайней мере две висячие вершины.

Доказательство свойств деревьев предлагается читателю в качестве упражнений.

Определение. Для произвольного связного неориентированного графа G(V,E) каждое дерево Т(V₁,T₁), где V₁=V и Е₁ÍE, называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами.

На рисунке 29 приведен пример графа и его каркасов.

Рис. 29

На рисунке 30 представлены граф и его каркасы, построенные методами поиска в глубину и в ширину. В круглых скобках указана очередность просмотра вершин графа при соответствующем поиске.

Рис. 30

Планарные графы

Во многих случаях не имеет значения, как изобразить граф, т.к. изоморфные графы несут одну и ту же информацию. Но встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. Так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при прокладке железнодорожных и других путей, где не желательны переезды.

Определение. Плоским называется граф, изображенный на плоскости так, что никакие два ребра геометрически не пересекаются нигде, кроме инцидентных им обоим вершин.

Определение. Граф, изоморфный плоскому, называется планарным.

Граф К₄ (рис. 31) – планарен, ему соответствуют плоские графы, изображенные на рисунках 32 и 33.

Определение. Область, ограниченная ребрами в плоском графе, и не содержащая внутри себя вершин и ребер, называется гранью.

Ниже на рисунке 34 изображен граф с четырьмя гранями.

Рис. 34

Заметим, что грань 4 не ограничена, такую грань называют внешней, все остальные грани называют внутренними.

Теорема (Формула Эйлера). Пусть G - связный планарный граф. Тогда справедливо следующее p-q+r=2, где p - количество вершин, q - количество ребер, r - количество граней.

Доказательство (методом математической индукции по количеству ребер). При q=0 теорема верна. Очевидно, что если q=0, то p=1 и r=1, тогда p-q+r=2.

Пусть теорема верна для всех графов с q ребрами: p-q+r=2. Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то q1=q+1, p1=p, r1=r+1 и p1-q1+r1=p-(q+1)+r+1= p-q+r=2. Если добавляемое ребро соединяет существующую вершину с новой, то q1=q+1, p1=p+1, r1=r и p1-q1+r1=p+1-(q+1)+r= p-q+r=2.

Теорема. Если G - связный планарный граф с р вершинами и q ребрами и p>3, то q£3p-6.

Доказательство. Так как каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более двух граней, то 3r£2q. Из формылы Эйлера следует,что 2=p-q+r, тогда 2£p-q+²/₃q, следовательно 3p-3q+2q³6, тогда q£3p-6

Теорема. Граф К₅ не является планарным.

Доказательство. Предположим противное, граф планарен. Тогда p=5, q=4*5/2=10, по формуле Эйлера r=7. Тогда не выполняется условие предыдущей теоремы q£3p-6, а значит, наше предположение не верно граф не является планарным.

Теорема. Граф К_{3, 3} не является планарным.

Доказательство. Предположим противное, граф является планарным. Тогда p=6, q=9, по формуле Эйлера r=5. В данном графе нет треугольников, следовательно, если он планарен, то в его плоской укладке каждая грань ограничена по крайней мере 4 ребрами. Таким образом, 4r£2q, 2r£q. Но полученное условие для нашего графа не выполняется, а значит, наше предположение не верно граф не является планарным.

Теорема. В планарном графе существует вершина степени не больше пяти.

Доказательство. Предположим противное, степень любой вершины графа не менее шести. Тогда сумма степеней всех вершин не менее 6*р, следовательно по лемме о рукопожатиях 2q³6p, отсюда p£q/3. Так как q£3p-6, получим q£q-6. Таким образом получили противоречие, значит, наше предположение не верно, в планарном графе обязательно должна быть вершина степень которой меньше шести.

Определение. Элементарным стягиванием называется следующая процедура: берем ребро е (вместе с инцидентными ему вершинами u, v) и “стягиваем ” его, то есть удаляем е и отождествляем вершины u и v; полученная при этом вершина инцидентна тем ребрам (отличным от е), которым первоначально были инцидентны вершины u и v.

Ниже на рисунке 35 представлены два графа: до и после процедуры элементарного стягивания ребра е.

рис. 35

Определение. Граф G называется стягиваемым к графу H, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний.

Теорема Куратовского. Граф является планарным тогда и только тогда, когда в нем нет подграфов, стягиваемых к графам К₅ или К_3,3.

Раскрашивание графов

Определение. Произвольная функция f:V®{1,2,...,k}, где k принадлежит множеству натуральных чисел, называется вершинной k-раскраской графа G(V,E).

Определение. Раскраска называется правильной, если f(u)¹f(v), для любых смежных вершин u и v.

Определение. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым.

Определение. Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом графа и обозначается c(G).

рис. 36

Для графа на рисунке 36 c(G)=3. Меньшим количеством цветов граф правильно раскрасить нельзя из-за наличия подграфов К₃. Рядом с вершинами графа - указаны номера цветов.

Дата добавления: 2014-12-29