Основные понятия теории графов Теорема 1 icon

Основные понятия теории графов Теорема 1



НазваниеОсновные понятия теории графов Теорема 1
Дата конвертации16.05.2013
Размер78.25 Kb.
ТипДокументы
скачать >>>

Основные понятия теории графов

Теорема 1.1. Пусть в графе G p вершин и q ребер. Пусть deg vi - степень вершины vi. Тогда


Доказательство. Когда мы считаем степень одной вершины, мы считаем все ребра, выходящие из нее. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу ребер.

Лемма 1.1. Из любого пути, идущего из v0 в vn, где v0  vn, можно выделить подпуть из v0 в vn, являющийся простой цепью.

Доказательство. Пусть данный путь - не простая цепь. Тогда в нем повторяется некоторая вершина v, то есть он имеет вид: P1 = v0C1vC2vC3vn. Тогда он содержит подпуть P2 = v0C1vC3vn. Если в P2 повторяется некоторая вершина, то аналогично удалим еще кусок и т. д. Процесс должен закончиться, т. к. P1 - конечный путь.

Лемма 1.2. Если граф G = (V,E) связный и a  V, b  V, a  b, и (a,b)  E, то при добавлении к графу G ребра (a,b) в полученном графе будет простой цикл.

Доказательство. Так как G - связный граф, то в нем есть путь из a в b. Тогда по лемме 1.1 в G есть простая цепь C из a в b. Поэтому в полученном графе есть цикл C, (b,a), a.

Лемма 1.3. Если граф G = (V,E) связный и ребро (a,b) содержится в некотором цикле в графе G, то при выбрасывании из графа G ребра (a,b) снова получится связный граф.

Доказательство. Это утверждение следует из того, что при выбрасывании из графа G ребра (a,b) вершины a и b все равно остаются в одной связной компоненте, поскольку из a в b можно пройти по оставшейся части цикла.

Лемма 1.4. Пусть в графе G = (V,E) p вершин и q ребер. Тогда в G не менее pq связных компонент. Если при этом в G нет циклов, то G состоит ровно из pq связных компонент.

Доказательство. Пусть к некоторому графу H, содержащему вершины u, v, добавляется ребро (u,v). Тогда если u, v лежат в разных связных компонентах графа H, то число связных компонент уменьшится на 1. Если u, v лежат в одной связной компоненте графа H, то число связных компонент не изменится. В любом случае число связных компонент уменьшается не более чем на 1. Значит при добавлении q ребeр число связных компонент уменьшается не более чем на q. Так как граф G получается из графа G1 = (V,) добавлением q ребeр, то в G не менее pq связных компонент.
Пусть теперь в G нет циклов, и пусть в процессе получения G из G1 добавляется ребро (u,v). Если бы u, v лежали уже в одной связной компоненте, то в G, согласно лемме 1.2, возникал бы цикл. Следовательно, u, v лежат в разных связных компонентах и при добавлении ребра (u,v) число связных компонент уменьшается ровно на 1. Тогда G состоит ровно из pq связных компонент.

Следствие 1. Если q  p2, то любой граф с p вершинами и q ребрами не связен.

Доказательство. По лемме 1.4 число связных компонент не менее pq  2.

Если граф G с p вершинами задан матрицей смежности A, то быстрое нахождение связных компонент можно осуществить следующим образом. Рассмотрим матрицу I1 порядка p, в которой на диагонали стоят 1, I1(i,j) = 1, если a(i,j) > 0 и I1(i,j) = 0, если a(i,j) = 0. Тогда равенство I1(i,j) = 1 равносильно тому, что из вершины с номером i в вершину с номером j существует путь длины не более 1. Определим теперь матрицу Ik порядка p, в которой Ik(i,j) = 1 тогда и только тогда, когда из вершины с номером i в вершину с номером j существует путь длины не более k. Легко понять, что все матрицы Ik при k  p1 совпадают и элемент с номером (i,j) в них равен 1 тогда и только тогда, когда из вершины с номером i в вершину с номером j существует хотя бы один путь. Обозначим такую матрицу I. Рассмотрим операцию умножения матриц, которая отличается от обычного умножения только тем, что вместо сложения используется дизъюнкция. Тогда легко видеть, что Ik+1 = Ik·I1.

Утверждение. Пусть p1  2m. Тогда матрицу I можно получить из матрицы I1, используя не более 2p3m операций конъюнкции и дизъюнкции.

Доказательство. Будем последовательно вычислять матрицы I2, I4, I8, ..., I2m, возводя предыдущую матрицу в квадрат. Возведение матрицы в квадрат (по обычному правилу: ``строчка на столбец'') требует не более 2p3 операций конъюнкции и дизъюнкции. Доказываемое утверждение следует из того, что I2m = I, поскольку p1  2m.

2. Деревья

Определение. Подграф G1 = (V1,E1) графа G = (V,E) называется остовным деревом, если G1 - дерево и V1 = V.

Теорема 2.1. Любой (конечный) связный граф G = (V,E) содержит хотя бы одно остовное дерево G1 = (V,E1).

Доказательство. Если в G нет циклов, то положим G1 = G. Если в G есть циклы, то удалим из G какое-нибудь ребро, входящее в цикл. Получится некоторый подграф G’ . По лемме 1.3 G’ - связный граф. Если в G’ нет циклов, то положим G1 = G’, иначе продолжим этот процесс. Процесс должен завершиться, так как E - конечное множество.

Теорема 2.2. Пусть в дереве G имеется p вершин и q ребер. Тогда q = p-1.

Доказательство. Так как G - связный граф и G не содержит циклов, то p-q = 1 по лемме 1.4. Отсюда q = p-1.

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

Теорема 2.3. Пусть G = (V,E) - неориентированный граф без петель и кратных ребер, |V| = p, |E| = q. Тогда следующие 5 условий эквивалентны:

^ 1) G - дерево;

2) G - без циклов и q = p-1;

3) G - связный и q = p-1;

4) G - связный, но при удалении любого ребра становится несвязным;

5) G - без циклов, но при добавлении любого нового ребра на тех же вершинах появляется цикл.

Доказательство. Докажем следующие переходы 1)=>2)=>3)=>4)=>5)=>1), откуда будет следовать, что из любого условия вытекает любое другое.

Переход 1)=>2) следует из теоремы 2.2. Пусть теперь выполняется 2). Тогда по лемме 1.4 в G число связных компонент равно p-q = 1, то есть G - связный граф. Отсюда следует переход 2)=>3). Переход 3)=>4) вытекает из следствия к лемме 1.4. Пусть выполняется 4). Тогда если бы в G был цикл, то при удалении любого ребра из этого цикла G остался бы связным, согласно лемме 1.3. Это противоречило бы 4). Значит G не имеет циклов. Вторая часть условия 5) вытекает, согласно лемме 1.2, из того, что G связный. Таким образом, получаем, что 4)=>5). Пусть выполняется 5). Если при этом G - не связный граф и вершины u, v лежат в разных связных компонентах графа G, то добавление к G ребра (u,v), очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что G - связный граф, то есть 5)=> 1). Теорема доказана.

Условия 4) и 5) показывают, что множество всех деревьев - это множество всех минимальных связных графов и, в то же время, множество всех максимальных графов без циклов.

Теорема 2.4. Число упорядоченных корневых деревьев с q ребрами не превосходит 4q.

Доказательство. Рассмотрим важный для приложений способ обхода упорядоченного корневого дерева, который называют «поиском в глубину». Этот обход описывается рекурсивно следующим образом. 1) Начать из корня дерева D; 2) пока есть поддеревья, перейти по ребру в корень очередного поддерева, рекурсивно обойти это поддерево “в глубину”, вернуться в корень исходного дерева. В результате обход “в глубину” проходит по каждому ребру дерева D ровно 2 раза: один раз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В соответствии с обходом “в глубину” будем строить последовательность из 0 и 1, записывая на каждом шаге 0 или 1, причем 0 будем записывать, если происходит переход в очередное поддерево, а 1, если мы возвращаемся из поддерева. Получим последовательность из 0 и 1 длины 2q, которую назовем кодом дерева D. По этому коду однозначно восстанавливается дерево D, поскольку каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных корневых деревьев с q ребрами не больше, чем последовательностей из 0 и 1 длины 2q, а их число равно 22q = 4q.

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

Следствие. Число неизоморфных корневых деревьев с q ребрами и число неизоморфных обычных деревьев с q ребрами не превосходит 4q.

Доказательство. Выделяя в неизоморфных деревьях по одной точке, мы получим неизоморфные корневые деревья. Упорядочивая поддеревья в неизоморфных корневых деревьях, мы получим различные упорядоченные корневые деревья. Поэтому число неизоморфных деревьев с q ребрами не превосходит числа неизоморфных корневых деревьев с q ребрами, которое, в свою очередь, не превосходит числа различных упорядоченных корневых деревьев с q ребрами. Отсюда и из теоремы 2.4 получаем доказываемое следствие.

^ 3. Планарные графы

Теорема 3.1. Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

Доказательство. Возьмем в пространстве любую прямую l и разместим на ней все вершины графа G. Пусть в G имеется q ребер. Проведем q полуплоскостей через l так, чтобы прямая l была их общим ребром (типа тетрадки). После этого каждое ребро графа G можно изобразить линией в своей полуплоскости и они, очевидно, не будут пересекаться.

^ Теорема 3.2 (формула Эйлера.) Для любой планарной реализации связного планарного графа G = (V,E) с p вершинами, q ребрами и r гранями выполняется равенство: pq+r = 2.

Доказательство. При фиксированном p индукцией по q. Так как G - связный граф, то q  p1 по следствию из леммы 1.4.

а) Базис индукции: q = p1. Так как G - связный и q = p1, то по теореме 2.3 G - дерево, то есть в G нет циклов. Тогда r = 1. Отсюда pq+r = p(p1)+1 = 2.

б) Пусть для p1  q < q0 теорема справедлива. Докажем, что для q = q0 она тоже справедлива. Пусть G - связный граф с p вершинами и q0 ребрами и пусть в его планарной реализации r граней. Так как q0 > p1, то G - не дерево. Следовательно, в G есть цикл. Пусть ребро e входит в цикл. Тогда к нему с двух сторон примыкают разные грани. Удалим ребро e из G. Тогда две грани сольются в одну, а полученный граф G1 по лемме 1.3 останется связным. При этом получится планарная реализация графа G1 с p вершинами, q01 ребрами и r1 гранями. Так как q01 < q0, то, по предположению индукции, для G1 справедлива формула Эйлера, то есть p(q01)+(r1) = 2, откуда pq0+r = 2. Что и требовалось доказать.

Следствие 1. Для любого выпуклого многогранника справедливо равенство pq+r = 2, где p - число вершин, q - число ребер, r - число граней.

Доказательство. Пусть выпуклый многогранник M имеет р вершин, q ребер и r граней. Пусть O - внутренняя точка многогранника М. Рассмотрим сферу S с центром в O настолько большого радиуса, чтобы M целиком лежал внутри S. Рассмотрим центральное проектирование с центром в точке O, и спроектируем вершины и ребра M на S. Тогда на S мы получим геометрическую реализацию некоторого связного графа с р вершинами, q ребрами и r гранями. Отсюда pq+r = 2.

Teорема 3.3. Вершины любого планарного графа можно правильно раскрасить в не более чем 5 цветов.

Доказательство (индукцией по числу вершин p).

1) Базис индукции: p = 1 - очевидно.

2) Пусть для p < p0 утверждение справедливо и пусть G = (V,E) - планарный граф с V = p0. По следствию 3 из теоремы 3.5 в G есть вершина v степени не более 5. Рассмотрим укладку на плоскости графа G без пересечения ребер. Удалим из G вершину v и все инцидентные ей ребра. Получим планарный граф G1 с числом вершин p01. По предположению индукции его вершины можно правильно раскрасить в 5 цветов C1, C2, C3, C4, C5. Пусть в G вершина v смежна с v1, v2, ... , vk, (где k  5). Рассмотрим 2 варианта:

а) Среди цветов вершин v1, v2, ... , vk в G нет цвета Ci (1  i  5). Тогда вершине v припишем цвет Ci и получим правильную раскраску графа G в 5 цветов.

б) Степень вершины v равна 5 и среди вершин v1, v2, ... ,v5 в G1 есть все 5 цветов. Без ограничения общности будем считать, что в укладке графа G ребра (v, v1), (v, v2), (v, v3), (v, v4), (v, v5) выходят из v в порядке по часовой стрелке и что C(vi) = Ci, i = 1,... ,5. Пусть V1 - множество всех вершин в G1, до которых можно дойти из v1 по ребрам графа G1, используя только вершины цветов C1 и C3. Возможны 2 варианта:

б1) v3  V1. Тогда в V1 поменяем цвета C1  C3, C3 C1. Так как вершины из V1 не смежны с другими вершинами цветов C1 и C3, то останется правильная раскраска и среди v1, v2,... , v5 не будет цвета C1. Тогда вершине v припишем цвет C1.

б2) v3  V1. Это значит, что в G1 есть цепь из v1 в v3, все вершины которой имеют цвета C1 и C3. Эта цепь вместе с ребрами (v3,v) и (v, v1) образует цикл в G, причем вершины v2 и v4 лежат по разные стороны от этого цикла. Это значит, что из v2 нельзя пройти в v4 в графе G1 только по вершинам цветов C2 и C4. Пусть V2 - множество всех вершин в G1, до которых можно дойти из v2 по ребрам графа G1, используя только вершины цветов C2 и C4. Тогда v4  V2 и далее поступаем как в б1).

В любом случае вершины графа G можно правильно раскрасить в не более чем 5 цветов, и теорема доказана.




Похожие:

Основные понятия теории графов Теорема 1 iconРабочая программа дисциплины теория графов
«Информационные системы и технологии» по профилю «Геоинформационные системы» одно из важнейших мест. Методы теории графов широко...
Основные понятия теории графов Теорема 1 iconПрограмма дисциплины Теория коллективного выбора для направления 080100. 62 «Экономика» подготовки бакалавра Авторы: Ф. Т. Алескеров, А. В. Захаров, А. Н. Субочев
Ооп: курс "Теория коллективного выбора" является факультативом; для его изучения необходимо знать основные факты теории множеств,...
Основные понятия теории графов Теорема 1 iconПриложение №3 к приказу ректора №52/од от «10» 07 2007 г
Основные понятия теории управления. Классификация систем и задач теории управления
Основные понятия теории графов Теорема 1 iconБабушкин Юрий Владимирович сар 80 час. № Н лекции
Основные понятия теории управления. Классификация систем и задач теории управления
Основные понятия теории графов Теорема 1 iconВопросы к экзамену по курсу «экономика» Понятие экономики и система экономических наук. Предмет экономической теории и ее основные функции
Основные методы экономического исследования. Понятия макроэкономика и микроэкономика
Основные понятия теории графов Теорема 1 iconОсновные понятия в теории функциональных систем Анохина

Основные понятия теории графов Теорема 1 iconАксиоматический метод
Аксиоматический метод построения научной теории заключается в следующем: выделяются основные понятия, формулируются аксиомы теории,...
Основные понятия теории графов Теорема 1 iconВопросы по теории вероятностей +Основные понятия теории вероятностей: события, вероятность события, частота события, случайная величина
Основные понятия теории вероятностей: события, вероятность события, частота события, случайная величина
Основные понятия теории графов Теорема 1 iconДокументи
1. /Графы/Программа.doc
2. /Графы/Урок 1....

Основные понятия теории графов Теорема 1 iconПротокол №4 от 28. 11. 2011 г зав кафедрой Шебанова Л. П
Знать основные понятия и утверждения изученной теории, иллюстрировать их примерами
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы