Шпора на экзамен по ДМ. 2 семестр - файл n1.docx

приобрести
Шпора на экзамен по ДМ. 2 семестр
скачать (88.8 kb.)
Доступные файлы (1):
n1.docx100kb.30.06.2009 21:22скачать

n1.docx

26. Определение графа. Основные характеристики графа. Виды графов. Представление графов. Пути и циклы. Связность. Лемма о рукопожатиях (с доказательством), ее следствие.

Граф-это мн-во точек, наз. вершинами и мн-во линий, наз.ребрами, кот.соединяют пары вершин или вершину саму с собой.

О1. Ненаправленный граф G- это конечное мн-во вершин V, конечное мн-во ребер Е и ф-ия F, кот. отображает Е в мн-во всех подмн-в V (F:E->P(V)), такая, что для каждого ребра Е отображение F Е есть одно- или двухэлементное подмн-ва V.

О2. 4 утверждения:

1)пары вершин v и w наз.смежными, если есть ребро е, соед. их. Так же говорят, что вершины v и w инцедентны ребру е или наоборот.

2)ребра е1,е2…еN наз. смежными, если имеют по крайней мере одну общую вершину.

3)валентностью или степенью вершины v(deg(v)) наз. число ребер,инцедентных вершине V.

4)Граф, у кот. каждая вершина имеет одинаковую валентность R, наз. правильным или R-валентным графом.

О3. 5 определений:

1)нулевым или полностью несвязанным графом наз. граф с пустым мн-ом ребер.

2)полным графом Kn наз. граф, у которого каждая пара вершин связана ровно одним ребром. Степень каждой вершины в графе Kn равна (n-1), т.к. каждая вершина связана с каждой из остальных (n-1) вершин посредством одного ребра. Всего ребер n(n-1)\2.(К3,К4,К5)

3) двудольный граф наз. граф, у кот. мн-во вершин имеет разбиение {v1,v2} такая, что каждое ребро связывает вершины v1 с вершинами из v2.(К3,3)

4)полный двудольный граф Кn,m-граф, у кот. каждая вершина из v1 связана с каждой вершиной из v2 одним ребром. |v1|=n,|v2|=m.

5) простой граф-это граф, кот не имеет петель или кратных ребер.

О4.

Пусть G-граф со мн-ом вершин {v1,v2…vn}. Мат.смежности наз. Аn*n=А(G), элементы кот. a(i,j)-числа различных ребер, соед. вершины vi и vj. Степенью вершины vi равна сумме всех эл-ов i-строки или i-столбца.

О5

Граф H наз. подграфом графа G, если

1)Vh-подмн-во Vg

2)Eh-подмн-во Eg

3)Fh(e)=Fg(e)

Пути в графе связности. Теорема о рукопожатии.

Сумма степеней всех вершин графа равна удвоенному числу ребер. Каждое ребро дает вклад равный 2 при подсчете суммы степенец всех вершин.

Следствие. В любом графе число вершин нечет.степени четно.

Пути и циклы.

О6.

1) маршрутом в графе наз.последовательность вершин и ребер.

2)цепь наз. простой если в ней нет повторяющихся вершин, кроме быть может повторяющихся концевых.

3)цикл- это замкнутая простая цепь.

Связность.

О7. Две вершины в графе связаны, если сущ-ет соед. их простая цепь.

Граф наз.связным, если для любой пары различных вершин сущ-ет соед. их путь.

Отношение связности вершин явлю эквивалентностью. Классы эквивалентности по отношению к связности наз. компонент связности графов. К(G)-число компонент связности. Граф явл. связным тогда, когда К(G)=1 и не связным если К(G)>1. Граф, имеющий n-вершин и m-ребер и k-компонент связности, обозначается (n,m,k)-граф. Вершина графа наз. точкой сочленения, если ее удаление удваивает число компонент связности.

Разрезающим мн-ом ребер графа наз. мн-во ребер, удалением кот. из графа приводит к увеличению числа компонент связности. Минимальное подключение групп разрезающее мн-во ребер наз. разрезом. Мост графа- это ребро, явл-ся одноэлементным разрезом.
27. Связность: лемма 1 и лемма 2 (с доказательством), теорема и ее следствия (с доказательством), теорема о числе

маршрутов длины k (с доказательством). Ее следствие. Вершинная связность графов.
2 вершины связаны, если существует соединяющая их простая цепь.

Лемма 1

Если для некоторых вершин в графе (u,v) существует (u,v)-маршрут, то существует и простая (u,v)-цепь.

Д-во:

Рассмотрим (u,v) маршрут наименьшей длины. Покажем что этот маршрут – простая цепь.

Если в нем имеются повторяющиеся вершины w, то заменяя часть маршрута от первого вхождения w до второго вхождения, получим более короткий маршрут.
Лемма 2

При удалении из графа моста число компонент связанности увеличивается точно на 1
Теорема

Пусть G обыкновенный (n,m,k) граф. Тогда верно неравенство n-k=
Следствие 1

Пусть G – обыкновенный (n,m) граф. Если m>(n-2)(n-1)/2 то граф связен.

Д-во: пусть к-число компонент связностей G. Если к>=2 то m=<(n-2)(n-1)/2 что невозможно -> к=1, то есть G – связен.

Следствие 2

Если G - произвольный (n,m,k) граф, то m>=(n-k)
Теорема о числе маршрутов длины k

Пусть А – матрица инцидентности графа G(V,E). |V|=n, тогда (A^k)ij есть число маршрутов длины k от vi к vj.

Следствие:

Маршрут от vi к vj (i неравно j) в графе G существует тогда и только тогда, когда (i,j) – элементы матрицы порядка n,n где n=|V|. A+A^2+…+A^(n-1) неравно 0

Вершинной связностью ? ("каппа") графа G называется наименьшее число вершин, которое нужно удалить, чтобы граф перестал быть связным. Для несвязного графа вершинная связность равна нулю. Для полносвязного графа вершинная связность полагается равной N-1 (поскольку, сколько вершин ни удалять из графа, - он всё равно не перестанет быть связным).


28. Эйлеровы графы: теорема Эйлера и ее следствие (с доказательством). Алгоритм Флёри, доказательство его корректности.
Связанный граф называется эйлеровым если в нем существует замкнутая цепь, содержащая все ребра графа (эйлеров цикл). Если снять требование замкнутости, то получим определение полуэйлерова графа и эйлеровой цепи

Теорема Эйлера

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

Следствие

Связанный граф является полуэйлеровым тогда, когда не более 2х его вершин имеют нечетную степень.

Алгоритм Флёри

Выбрать произв вершину А

Выбрать некоторое ребро U от A и присв. номер 1

Каждое пройденное ребро вычеркнуть и присвоить номер на 1 больше предыдущего вычеркнутого ребра.

Находясь в вершине Х не проходить по ребру, соед. Х с А

После того как в графе пронумерованы все ребра, образуется эйлерова цепь.

29. Циклы Гамильтона: теорема (с доказательством), ее следствие (теорема Дирака). Задача китайского почтальона. Задача коммивояжера: решение методом ветвей и границ, методом остовного обхода.
Гамильтонов цикл – это цикл, проходящий через все вершины графа. Г.ц. необязательно содержит все ребра графа. Гамильтоновым может быть только связанный граф.

Теорема

Пусть G(V,E) – связ. граф с n вершин. n>= 3 и для каждой пары различных не смежных вершин u,v из V, таких что deg(u)+deg(v)>=n граф G является гамильтоновым.

Теорема Дирака

Пусть G(V,E) – связанный граф с n вершинами, где n>= 3. Если для каждой v из V выполняется deg(v)>=n/2 то граф G имеет гамильтонов цикл.

Задача китайского почтальона

Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин njc(aj), где число nj показывает, сколько раз проходилось ребро aj, а c(aj) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда ? c(aj).
30. Изоморфизм: определение, примеры, теоремы. Принцип изоморфизма.
Изоморфные графы – графы одинаковой формы. Графы G1 = (X1, A1) и G2 = (X2, A2) изоморфны, если существует взаимно однозначное соответствие между множествами вершин X1 и X2, такое, что любые две вершины одного графа соединены тогда и только тогда, когда соответствующие вершины соединены в другом графе. Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.

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

Теорема верна также для мультиграфов, псевдографов и орграфов.

Пусть G -(n, m) - граф, VG={1, 2,..., n} EG={e1, e2,..., em}. Определим бинарную nЧm-матрицу I=I(G) условиями

Матрица I называется матрицей инцидентности графа G. В каждом ее столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G>I(G) является биекцией множества помеченных (n, m) - графов с занумерованными ребрами на множество nЧm-матриц, удовлетворяющих описанным условиям.

Принцип изоморфизма. Чтобы показать, что графы изоморфны, нужно найти изоморф из одного в другой (*crazy*). Чтобы показать что они не изоморфны, нужно найти у одного графа такие свойства, которыми не обладает другой.
31. Метрические характеристики графа: определения, теорема (с доказательством).

Пусть G– связный граф, а u и v– две его несовпадающие вершины. Длина кратчайшего (u, v) - маршрута называется расстоянием между вершинами u и v и обозначается d(u, v). Положим d(u, u) =0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

d(u, v) >= 0;

d(u, v) =0 тогда и только тогда, когда u=v;

d(u, v) =d(v, u);

d(u, v) + d(v, w) =d(u, w) (неравенство треугольника).

Для фиксированной вершины u величина e(u) =max d (uv) называется эксцентриситетом вершины u. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G). Тем самым

dG =max e(u)

Вершина v называется периферийной, если e(v) =d(G). Простая цепь длины d(G), расстояние между концами которой равно d(G), называется диаметральной цепью.

Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G).

Очевидно, что радиус графа не больше его диаметра.


Вершина v называется центральной, если e(v) =r(G). Множество всех центральных вершин графа называется его центром. Граф может иметь единственную центральную вершину или несколько центральных вершин. Наконец, центр графа может совпадать с множеством всех вершин. Например, центр простой цепи Pn при четном числе вершин n состоит ровно из двух вершин, а при нечетном – из одной; для цикла же Cn все вершины являются центральными.

Задача нахождения центральных вершин графа постоянно возникает в практической деятельности людей. Пусть, например, граф представляет сеть дорог, т.е. вершины его соответствуют отдельным населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, магазины. В подобных ситуациях критерий оптимальности часто заключается в оптимизации «наихудшего» случая, т.е. в минимизации расстояния от места обслуживания до наиболее удаленного пункта. Следовательно, местами размещения должны быть центральные вершины графа.

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


32. Деревья: основные определения, теоремы и их следствия (с доказательствами). Кодирование деревьев. Остовные деревья. Алгоритм Прима и Краскала. Поиск в глубину и поиск в ширину.

Граф, не содержащий цикла называется ациклическим или лесом. Дерево – это связный ациклический граф, компоненты связанности леса – деревья.

Теорема 1.

Граф – это лес тогда, когда каждое ребро графа – мост.

Док-во.

Если G – лес, то в нем нет циклов, следовательно, ни одно ребро не входит в цикл, и тогда по лемме все ребра G – мосты.

Теорема 2.

Дерево с n-вершинами содержит (n-1) ребер.

Док-во.

Пусть G-дерево с n-вершинами, согласно предыдущей теореме – все ребра мосты. Будем последовательно удалять ребра G? каждый раз увеличивая число компонент связности на 1. Первоначально имелась 1 компонента связности, поскольку дерево связный граф, после удаления всех ребер останется n-изолированных вершин. След-но, n-компонент связности, т.о. в указанной процедуре удаления был (n-1) шаг, что и требовалось доказать.

Следствие 1.

Пусть в лесе n-верш ин, m-ребер, и к - компонент связности, тогда m=n-k.

Док-во.

Пусть в i-ой компоненте связности леса ni – вершин и mi-ребер. Тогда для каждого i, по теореме 2 mi=ni-1. Посчитаем общее число ребер леса. m= (ni-1)=ni-k=n-k.

Следствие 2.

Если в лесе число ребер на 1 меньше числа вершин, то этот лес – дерево.

Док-во из следствия 1.

Утверждение.

Лес – дерево тогда, когда число его ребер на 1 меньше числа вершин.

Следствие 3.

В дереве, которое содержит по меньшей мере 2 вершины, не менее двух висячих вершин.

Док-во.

Пусть в дереве n?2 вершин, тогда оно содержит m=n-1 ребер, в лемме о рукопожатиях  deg(vi)=2m=2(n-1). Будем считать, что вершины упорядочены по возрастанию степеней.

deg(v1)?deg(v2)?…?deg(vn). Покажем, что deg(v1)= deg(v2)=1. Если предположить противное, то получим противоречие. deg(v2)>1, deg(v2)?2 ; 2(n-1) = deg(v1)+…+deg(vn)?1+(n-1) deg(v2)?`1+(n-1)2;

Следствие 4.

В лесе, содержащем хотя бы 1 ребро, не менее 2 висячих вершин.

Теорема 3.

Пусть в связном графе число ребер на 1 меньше числа вершин, тогда этот граф дерево.

Док-во.

Пусть в G имеется n-вершин, и m=n-1 ребер, по теореме в простом графе m?n-к, где к-число компонент связности, для G к=1 и имеет место равенство m=n-1. Следовательно, это граф простой, т.к. в противном случае, удалив все петли и кратные ребра мы уменьшили бы m, не изменив при этом n и к, а это привело бы к нарушению неравенства. Удаление каждого ребра G приведет к нарушению неравенства m?n-к, если при этом не изменится n и к, т.о. по определению каждое ребро графа G – мост и в силу этого G – ациклический граф, поскольку при этом, по условию G-связный, то он дерево.

Теорема 4.

Граф – дерево тогда, когда любые 2 его вершины соединены одной цепью.

Док-во.

Необходимость.

Пусть G- дерево, значит это связный граф и любые 2 его вершины связаны цепью, при этом 2-х различных цепей, соединяющих 2 вершины, быть не может, т.к. вместе они дадут цикл, а в дереве циклов нет.

Достаточность.

Если в графе 2 вершины связаны цепью, то граф связный и ацикличный, от того что 2 вершины этого цикла были бы связаны по меньшей мере двумя простыми цепями, в случае наличия цикла.

Теорема 5.

Лес является деревом тогда, когда добавление любого ребра приводит к образованию ровно одного цикла.

Док-во.

Пусть ацикл. Граф связен тогда по теореме 4, любые 2 вершины u и v связаны одной простой цепью, и добавление ребра uv приводит к образованию цикла, причем только одного, т.к. если бы их образовалось хотя бы 2, то объединяя эти циклы, можно было бы получить один, не содержащий uv, а это противоречит ацикличности исходного графа.

Если при добавлении uv образуется цикл, то удаляя из него uv, получим цепь, связыв-ю u и v, а это значит u и v связанные, как и любые 2 другие вершины, т.е. граф связен и является деревом.

Теорема Кэли. О числе помеченных деревьев.

Число помеченных деревьев с n-вершинами равно .

Максимальное количество уровней – высота дерева.

Если наибольшая из степеней выхода для вершин дерева равна m, то дерево m-арное. Когда m=2 (бинарное).

В любом бинарном дереве каждый сын родителя левый или правый.

Теорема.

У каждого связного графа существует подграф, который является оставным деревом.

Кодирование деревьев.

Алгоритм кодирования.

i=1

пусть vi-висячая вершина дерева с наименьшей меткой, тогда аi –метка с смежной с ней вершиной.

Удалим vi и инцидентное ей ребро.

Если в дереве осталось больше 2-х вершин, увеличим i на 1 и перейдем к 2Ю иначе стоп.

Алгоритм декодирования дерева.

Пусть В0={1,2,..n}, bi – наименьшее число из В0, не встречающееся в наборе (а1, а2, аn-2), тогда biэто номер висячей вершины, смежной с а1 и дерево содержит ребро bi а1, набор (а2, аn-2) кодирует дерево Т1 с множеством пометок B1=B\{b1}. Т1 – получается из исходного дерева Т, удалим вершины b1 и инцидентные ребра bi а1. В качестве b2 возьмем наименьшее число из B1, не встречающееся в последовательности (а2, аn-2), дерево T1 и T должно содержать ребро b2 a2. Теперь набор (а3, аn-2)описывает Т2 с множеством пометок B2=B1\{b2} и так далее.

На к-ом шаге процедуры рассматривается дерево Tk-1, мн-во пометок Вк-1 выбирается bk не входящее в набор (ак, аn-2),после чего утверждается о наличии в дереве Т ребра а kbk, после n-2 шагов будут выявлены n-2 ребра дерева Т и множество Вn-2 ,будет содержать 2 пометки для последнего n-1 ребра.

В самом деле, убедимся в том, что получаемый после декодирования граф – дерево.

Оставные деревья.

Стягивающим или оставным деревом связного графа G называется произвольный его подграф, связывающий все его вершины и являющийся деревом.

Оставным лесом графа G явл-ся произвольный его подграф, содержащий все его вершины и являющийся лесом.

Построение остовного леса.

-последовательно удаляем ребра, входящие в циклы, до тех пор, пока не будет получен ацикличный граф.

Граф называется взвешенным, если каждому его ребру поставлено в соответствие число – вес ребра. Вес графа – это сумма весов всех его ребер.

Существуют эффективные алгоритмы нахождения стягивающего дерева минимального веса.

Алгоритм Краскала.

Пусть n –мощность мн-ва ребер |Е|. след-й шаг выполнять (n-1 )раз

Включить в Т ребро G наименьшего веса, облад-м тем свойством, что при добавлении его в Т в этом графе не образуется цикл. Исключить из G данное ребро.

(G – исходный, Т- искомый)

Алгоритм Прима.

Пусть V1={x1} – состоит из вершины x1, где x1 – принадлежит исходному G. Пусть Е1=. Следующий шаг выполнять для i=2,n. Получим дерево Si=(Vi, Ei) и с Si-1 добавлением ребра графа G наим. веса.(среди тех ребер при добавлении кот-х к Si-1 обр-ся дерево). Искл-ть из G данное ребро.

33. Планарность: определения, теоремы и леммы с доказательством, алгоритм ? ‐укладки графа на плоскость, двойственные графы.

Граф наз-ся плоским, если его вершины – это точки, лежащие на плоскости и ребра графа – непересекающиеся на плоскости линии. Планарный граф - граф, который можно перестроить в плоский. Если граф планарен, то он оказывается разделенным на части, включая внешнюю часть. Эти части – грани. Граница каждой грани – цикл. Грань планарного графа – это максимальный участок плоскости такой, что любые 2 точки могут быть соединены кривой, не пересекающей ребро графа.

Теорема Эйлера.

Если G – связный планарный граф, содержащий v(вершин), e(ребер), f(граней), то v-e+f=2

Док-во.

Используем индукцию по числу ребер. Если е=0, то имеется 1 вершина и одна грань, поэтому 1-0+1=2. Верно. Если имеется е=1, v=2, f=1, 2-1+1=2

Предположим, что теорема верна и для произвольного планарного связного графа, у которого к-ребер. Пусть имеется Gк+1 с (к+1) – ребрами. Удалим 1 ребро и получим Gк с к-ребрами и покажем, что теорема выполняется.

Пусть Gк+1 не имеет циклов, будем двигаться по пути до тех пор, пока не достигнем вершины, из которой нет другого вых-го ребра. Это возможно в случае, когда в Gк+1 нет циклов. Найденная вершина имеет степень 1, удалим вершину и ребро, инцидентное ей, число граней не изменится, граф останется связным и планарным и будет содержать к-ребер. Если в Gк+1 есть циклы, удалим из цикла ei с инцид-ми вершинами ui и vi, сами вершины оставим. Согласно теореме все еще имеется путь из ui в vi так что граф остается связ-м и планарным. Он будет иметь к-ребер. Следовательно, теорема вып-ся. Поскольку еi входит в цикл, оно разделяет 2 грани, след-но при удалении этого ребра, удалится и грань. Поэтому значение v-e+f=2 не изменилось и формула для Gк+1 справедлива.
Теорема.

Полный двудольный граф К3,3 не является планарным.

Док-во.

Используем метод приведения к абсурду. Предположим, что К3,3 планарный, если это так, то 6-9+f=2, f=5. Пусть А и В неперес-ся мн-во вершин, форм-ие мн-во v – вершин графа V= AB=. Если начать путь из А и не повторять ребра, то можно попасть в вершину из В, затем в вершину из А прежде чем завершить цикл. Любой цикл в К3,3 представляет собой путь, длина которого по меньшей мере равна 4. Поэтому каждая грань определена циклом, в котором не менее 4-х ребер, т.о. сумма ребер всех граней >4f, но каждое ребро подсчитывается не более 2-х раз, поскольку оно яв-ся границей не менее 4-х граней. Значит, сумма ребер всех граней должна быть <2е, т.о. получим 4f?2e. f?4,5 - это противоречие.
Лемма.

В произвольном связном планарном графе с количеством v?3 имеет место неравенство: 3v-e?6.

Док-во.

Если G не имеет циклов, то в нем ребер меньше чем вершин, учитывая, что v?3, 2v-6?0 получим е?v+2v-6 или 3v-e?6.

Если G содержит цикл, то просуммируем все ребра, ограниченные грани, поскольку граница каждой грани содержит не менее 3-х ребер, то сумма всех ребер всех граней должна быть больше 3f и одновременно любое ребро может быть границей не более 2 граней, кол-во ребер < 2е след-но 3f?2e. Учитывая, что v-e+f=2 получим 6=3v-3e+3f?3v-3e+2e=3v-e?6. Что и т.док-ть
Теорема.

Граф К5 не явл-ся планарным.

Док-во.

Граф К5 имеет 5 вершин и 10 ребер. След-но 3v-e=5 след-но по предыдущей лемме этот граф не планарный.

Критерий планарности.

Подразбиением ребра uv называют его замену на 2 ребра uw и wv. 2 графа гомиоморфны, если они могут быть получены из одного и того же графа подразбиением ребер. Гомиоморфные плоские графы имеют одинаковое кол-во граней.

Теорема Пантрагена и Куратовского.

Граф планарный т.и.т.т., когда он не содержит подграфа гомиоморфного К3,3 или К5.
Алгоритм гамма-укладки графа на плоскость.

Пусть построена некоторая укладка подграфа H графа G сегментом S относительно Н будем называть подграф графа G одного из следующих видов:

Ребро e=uv из EG: е не принадл. EH и v принадл. EH

Связную компоненту графа G-H дополненную всеми ребрами G инцид-ми вершинам взятой компоненты. Вершину v сегмента S назовем контактной, если v принадл. VH.

Допустимой гранью для S относит-но H наз-ся грань Г графа Н, содерж-я все контактные вершины сегмента S.

Выбрать просто цикл С графа G и уложить его на плоскости Н=С;

Найти грани G и сегменты относительно Н, если мн-во сегментов пусто, то перейти к шагу 7;

Для каждого сегмента S определить мн-во ГS . Если существует сегмент S, для которого ГS пусто, то G не планарен и конец алгоритма, а иначе идти дальше.

Если существует сегмент S для которого имеется единств. Допустимая грань Г, то перейти к шагу 6,иначе к шагу 5.

Для некоторого сегмента S: ГS>1, выбрать произвольную допустимую грань Г.

Поместить произвольную -цепь из S в грань Г. замкнуть Н на НС перейти к шагу 1.

Построена укладка графа на плоскость.
Свойства планарных графов.

Максимальное число некратных ребер плоского графа 3n-6;

Если число некратных ребер графа ?n+2, то граф заведомо плоский

Если число некратных ребер графа >3n-6, то граф не плоский.


34. Раскраска графов: определения, теоремы (с доказательством), алгоритм раскраски. Реберная раскраска графов.
О. Пусть G-граф, тогда раскрашивание графа G наз. окрашивание вершин графа такое, что нижние 2 смежные вершины не имеют один цвет. Пусть Сg(L) это кол-во способов раскрашивания графа G в L цветов, таких, что никакие 2 смежные вершины не имеют один цвет. Для фиксированного графа G Сg(L)-полепомиальная (ХЗ ЧТО ТУТ НАПИСАНО!!!!!! ) ф-я L, наз. хроматическим мн-ом графа. Хроматическое число графа- это наименьшее число цветов, используемое для раскраски графа, т.е. наименьшее положительное n: Сg(n)не = 0.

Теорема Кейнига.

Граф явл-ся 2 хроматическим(двудольным), тогда, кога он не содержит циклов нечетной длины.

Замечание. Все 2 хром. графы явл-ся двудольными. Любое дерево двудольно.

Теорема. Если максимальная степень вершин графа равна S, то хроматическое число этого графа не превышает n<=S+1.

Теорема Если граф G=G1VG2V…VGn. G1,G2,..Gn-компоненты, то Cg(L)=Cg1(L)* Cg2(L)*..*Cgn(L).

Если для раскраски графа требуется к-цветов, то и для одной из его компонент требуется для раскраски к-цветов.

Теорема. Для произвольного планарного графа G с n-вершинами, ф-я Сg(L) есть многочлен n-й степени.

Для произвольного не пустого планарного связанного графа G постоянный член Cg(L)=0.

Если граф G имеет 2 или более вершины, то сумма коэф. Cg(L)=0.

Теорема Хивуда. Произвольный планарный граф можно раскрасить используя только 5 цветов.

Док-во. Пусть граф G- связный , планарный. Используем индукцию по кол-ву вершин. Если в графе одна вершина, то граф очевидно можно раскрасить в 5 цветов.

Предположим, что при раскрашивании произвольного графа G с вершинами используется только 5 цветов. Пусть G-граф с к+1 вершиной, тогда у этого графа есть вершина степени 5 или менее. Пусть u такая вершина. Пусть G’ подграф G в котором удалена вершина v и инцидентные ей ребра. Поскольку в G’ к- вершина, то его можно раскрасить в 5 цветов. Если степень вершины v<5, то в графе она явл-ся смежной с 4-мя или менее вершинами. ЕЕ можно раскрасить цветом отличным от смежных вершин. Таким образом раскраска завершена. Предположим, что степень v=5, тогда v смежна с G с 5-ю вершинами . Для их окраски использовано 4 цвета и можно снова выбрать неиспользуемый цвет для v. v1, v2,…v5 раскрашены в различные цвета, пусть v1-1 цв. и тд.

Алгоритм раскрашивания.

1) Произвольные вершины а1 графа принимает цвет №1.

2) Если вершина а1,…аi раскрашиваем L цветами L<=i, то новый произвольно взятой вершиной а(i+1) припишем минимальный цвет, не использованный при раскраске вершин.


35. Паросочетания: определения, теорема Менгера, теорема Холла с доказательством, алгоритм поиска максимального паросочетания, венгерский алгоритм.
Подмн-во М мн-ва Е наз. паросочетанием, если никакие 2 ребра из М не имеют общие вершины, т.е. никакие 2 ребра не явл-ся инцидентными. Если {a,b}ребро в паросочетании, то вершины a,b наз паросочетанными, а само ребро паросочетающимся.

О. Паросочетание M на двудольном графе G наз. максимальным, если никакое другое паросочетание на G не содержит ребер больше, чем m.

Паросочетания М на двудольном графе G равном G=(V,E), где V=Aобьед.В наз. полным, если «а» из А и существует «b» из В, такое, что «ав» из М.

О. Для подмн-ва х мн-ва А рассмотрим мн-во R(x)={b: b из B и b смежно с вершиной из х}

R(x) наз. мн-ом значений х.

Задача о свадьбах.

Теорема. Двудольный граф G=(V,E), кот. V=AUB имеет полное паросочетание тогда, когда для каждого подмн-ва х из А выполняется |х|<=|R(x)| (Теорема Холла).

Алгоритм нахождения максимального паросочетания.

1)

в1 в2 в3 в4




а1

а2

а3

а4

0 1 [1] 0

1 0 1 [1]

[1] 0 1 1

0 0 0 1

в3

в4

в1

#



а2 а1 а2 а4




2)

в1 в2 в3 в4

а1

а2

а3

а4

0 [1] 1 0

1 0 [1] 1

[1] 0 1 1

0 0 0 [1]

Шаг1. Найдем строку, где нет [1], поставим в конец строки #, отметим эту единицу символом а4. Двигаемся вверх по столбцу до [1]. На пересечении столбца, содержащего 1 разм а2. В столбцах в1 и в3 ищем строки содержащие [1]. Затем в строке а1 ищем 1, это столбец в2 заменим а1.

Выпишем: а4->в4, а2->в3, а1->в2, а2->в1. Проходя эти шаги, заменим 1 на [1]и наоборот.

Выпишем: а1->в2, а3->в1, а2->в3, а4->в4

36. Экстремальные пути в нагруженных ориентированных графах: волновой алгоритм, алгоритм Дейкстры, Форда‐Беллмана, Флойда. Задача Штейнера.

Экстремальные пути в нагруженных ориентированных графах

Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так что дуге (xi,xj) сопоставлено некоторое число c(xi,xj) = cij, называемое длиной (или весом, или стоимостью дуги). Длиной (или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (xi,xj), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е.

l(s) = cij,

причем суммирование ведется по всем дугам (xi, xj) s.

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

Для нахождения минимального пути между двумя произвольными вершинами для случая, когда все cij і 0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана и др.

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

Алгоритм Форда – Беллмана нахождения минимального пути

Предполагается, что ориентированный граф не содержит контуров отрицательной длины.

Алгоритм 3.1 (Алгоритм Форда – Беллмана).

Основными вычисляемыми величинами этого алгоритма являются величины j(k), где i = 1, 2, … , n (n – число вершин графа); k = 1, 2, … , n – 1. Для фиксированных i и k величина j(k) равна длине минимального пути, ведущего из заданной начальной вершины х1 в вершину хi и содержащего не более k дуг.

Шаг 1. Установка начальных условий.

Ввести число вершин графа n и матрицу весов C = (cij).

Шаг 2. Положить k = 0. Положить i(0) = Ґ для всех вершин, кроме х1; положить 1(0) = 0.

Шаг 3. В цикле по k, k = 1,..., n – 1, каждой вершине xi на k-ом шаге приписать индекс i(k) по следующему правилу:

i(k) = {j(k – 1) + cji} (3.1)

для всех вершин, кроме х1, положить 1(k) = 0.

В результате работы алгоритма формируется таблица индексов i(k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1. При этом i(k) определяет длину минимального пути из первой вершины в i-ую, содержащего не более k дуг.

Шаг 5. Восстановление минимального пути.

Для любой вершины xs предшествующая ей вершина xr определяется из соотношения:

r(n – 2) + crs = s(n – 1), xrО G-1(xs), (3.2)

где G-1(xs) - прообраз вершины xs.

Для найденной вершины xr предшествующая ей вершина xq определяется из соотношения:

q(n – 3) + cqr = r(n – 2), xqО G-1(xr),

где G-1(xr) - прообраз вершины xr, и т. д.

Последовательно применяя это соотношение, начиная от последней вершины xi , найдем минимальный путь.
37. Сети: определения, пути в сетях, алгоритм ФордаФалкерсона.

Определение. Пусть задан ориентированный граф G=(x,A) с вершинами s,t такими, что . Каждой дуге а из А поставлено в соответствие число , которое называется пропускной способностью дуги. Такой граф будем называть сетью. Функцию , определённую на множестве дуг сети назовём потоком сети, если для любого а из А, , выполняется множество дуг выходящих из вершины – множество дуг заданных в вершине х : .

Определение. Назовём дугу насыщенной, если поток этой дуги равен её пропускной способности, т.е. .

Теорема 1. Пусть - путь из с в t. Если все дуги этого пути насыщенные, то можно увеличить поток сети.

Рассмотрим

Теорема 2. Если , то увеличивается поток на каждой дуге, уменьшая на мы увеличиваем поток всей сети на . Цель для которой называется насыщенной.

Поток в сети назовём полным, если любой путь, соединяющий исток со стоком (s с t) содержит по крайне мере 1 насыщенную дугу.

Теорема 3. В сети не существует цепи от s к t с , то поток нельзя больше увеличить, т.е. он максимальный.

Теорема 4.(Форда Фалкерсона) Для заданной сети макси максимальное значение потока равно минимальной пропускной способности разреза.

Алгоритм Форда Фалкерсона поиска максимального потока в сети.

Строим произвольный поток (нулевой)

Ищем полный поток. Если поток не полный, то в сети существует путь, все дуги которого не насыщены. Увеличиваем поток через эти дуги до тех пор, пока не насытится по крайней мере 1 из дуг. Таким образом, получаем новый поток . Если он не полный, то операцию повторяем.

Отыскание максимального потока.

а) Помечаем вершину S символом +.

б) Если вершина помечена, то символом + помечаем все вершины х. для которых пути не насыщены.

в) Если таким образом удалось пометить сток t, то существует цепь, идущая через помеченные вершины t. Вычисляем для этой цепи и увеличиваем его на . Процедура повторяется до тех пор, пока удаётся пометить сток t. Иначе идти к 4).

4) Конец алгоритма.

38. Фундаментальная система циклов графа.

Циклы, система фундаментальных циклов

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

Рассмотрим неориентированный мультиграф (s-граф) G, n — вершин, m — ребёр, p — связных компонент. ?(G) = n ? p — коцикломатическое число (число ребер в остовах всех p связных компонент графа). ?(G) = m ? ?(G) = m ? n + p — цикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. ?(G) — наибольшее число независимых круговых токов в электрической цепи. ?(G) — наибольшее число независимых разностей потенциалов в электрической цепи.

Далее в этом разделе разговор будет вестись о неориентированных графах. Напомним, что циклом в неориентированном графе называется цепь, у которой совпадают начало и конец. Цикл будем называть простым, если в нем нет одинаковых вершин (кроме первой и последней). Такие циклы можно представлять как множества ребёр. Рассмотрим операцию ? сложения по модулю 2 или симметрической разности над множествами ребёр:

M1 ? M2 = {e | (e ? M1 ? e ? M2) ? (e ? M1 ? e ? M2) }.

Рассмотрим ряд вспомогательных фактов:

0M = Ш

1M = M

M ? Ш = M

M ? M = Ш

M называется линейной комбинацией {Mi}, если M = ? ?iMi, где ?i ? {0, 1}.

Таким образом множество подмножеств ребёр графа оказывается линейным пространством над полем {0, 1}.

Множество циклов {Zi} называется независимым, если ?i Zi не является линейной комбинацией остальных. Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы системы называют фундаментальными.

Теорема

Рассмотрим граф G = (V, E): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных циклов в точности равно ?(G) = m ? n + 1.

Доказательство. Приведем конструктивное доказательство этого факта (оно одновременно содержит алгоритм построения фундаментальной системы циклов). Рассмотрим T(V, ET) — некоторый остов графа G, который существует ввиду связности. Этому остову соответствует кодерево T*(V, ET*), где ET* = E \ ET. Отметим, что кодерево разумеется не является деревом. Каждое ребро e ? T* из кодерева при добавлении его к остову T очевидно порождает ровно один простой цикл Ze. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро e.

Покажем, что любой цикл графа G зависит от {Ze}, где e пробегает все множество ребер кодерева T*. Понятно, что любой элемент фундаментальной системы зависит от неё же самой, поэтому далее будем считать, что Z ? Ze.

Пусть теперь некоторый цикл Z содержит ребра e1, …, ek ? T*. Такие ребра в Z обязательно есть, в противном случае Z ? T, что невозможно, так как T — дерево. Обозначим цикл, соответствующий ребру ei, как Zi. Докажем индукцией по k, что Z = Z1 ? … ? Zk.

База: пусть k = 1, тогда e1 ? T, Z \ {e1} ? T и Z = Z1, так как если бы Z ? Z1, то концы e1 были бы соединены в T двумя цепями, что невозможно.

Пусть (индукционное предположение) Z = Z1 ? … ? Zm для всех циклов Z, содержащих m < k ребер из кодерева. Далее ребра кодерева будем называть хордами. Рассмотрим цикл Z c k хордами e1, …, ek ? T*. Рассмотрим Zk. Имеем Z? := (Z \ {ek}) ? (Zk \ {ek}) — тоже цикл (возможно, не простой). Но Z? содержит только k ? 1 хорду e1, …, ek?1. По индукционному предположению Z? = Z1? … ? Zk?1. Добавим к этому циклу Zk. Имеем:

Z? ? Zk = (Z \ {ek}) ? ((Zk \ {ek}) ? Zk) = (Z \ {ek}) ? {ek} = Z.

Таким образом, {Ze}, где e ? T*, является фундаментальной системой циклов. Поскольку все фундаментальные системы содержат одинаковое число элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом T. Число ребер в ней равно числу ребер в кодереве.

|ET*| = |E| ? |ET| = m ? (n ? 1) = m ? n + 1.

Алгоритм построения фундаментальной системы циклов (для графа такого, как в условии теоремы):

Построим любое остовное дерево T исходного графа G.

Добавим к T некоторое ребро e, которое является ребром графа, но не принадлежит остову.

Очевидно, что после такого добавления образуется цикл Ze.

Все циклы {Ze} (соответствующие всем ребрам, взятым не из остова) образуют фундаментальную систему циклов.


39. Операции над графами

Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.

Объединение графов G1 и G2 , обозначаемое как G1U G2 , представляет такой граф G3 = (Х1 Х2, A1 A2), что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 .

Пересечение графов G1 и G2 представляет собой граф G4 = (Х1 Х2, A1 A2). Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2.

Кольцевая сумма двух графов G1 и G2 представляет собой граф G5, порожденный на множестве ребер A1 и A2 . Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1, либо в G2, но не в обоих одновременно.

Рассмотрим унарные операции на графе.

Удаление вершины. Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G–хi является графом, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине.

Удаление ребра или удаление дуги. Если ai -дуга графа G = = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг.

Замыкание или отождествление. Говорят, что пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хi и xj , становятся инцидентными новой вершине.

Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин.


41. Машина Тьюринга (МТ): основные определения, примеры.

основная идея Тьюринга заключалась в том, что алгоритмические процессы – это процессы, которые может совершить подходяще устроенная машина.

О. Под машиной Поста и Тьюринга понимается условная машина, состоящая из следующих частей:

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

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

3. Управляющее устройство, которое в каждый момент времени находится в некотором «состоянии». Предполагается, что управляющее устройство машины имеет конечное число состояний (внутр. сост. машины). Одно из них называется заключительным и управляет окончанием работы машины.

Машина Тьюринга может сдвинуть ленту на 1 ячейку вправо/влево, при этом не изменяя содержимое ячеек, и изменять ячейку, оставляя машину неподвижной.

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

Пусть алфавит МТ задан в виде множества А={S0, S1, …Sn}, где S0 соответствует пустой ячейки. Число состояний устройства задано в виде Q={q0q1..qm}, где q0 – заключительное состояние. Конечная совокупность символов алфавита, с которой работает машина называется внешним алфавитом, а конечная совокупность внутренним состояний устройства управления внутренним алфавитом.

Конфигурацией машины называется совокупность, образованная последовательностью состояний всех ячеек ленты и состоянием устройства управления. Если стандарт. МТ, находясь в состоянии qi и воспринимает записыв. на ленте символ Sk переходим в новое стояние qj , заменяя символ рассматриваемой ячейки на Sm и сдвигая ленту влево на ячейку. то говорят что МТ выполнят команду :

qiSnqjSm Л

Если замены не происходит, то Sm может отсутствовать.

Л – движение влево

П – движение вправо

С – остановка

обычно команды МТ задаются пятерками вида: qiSmqjSmЛ

Пример.

(Вроде как ответ на 44. Построить МТ, осуществляющую перенос нуля в двоичной последовательности.)

Пусть алфавит МТ А={0,1} , команды q11q11Л и q10q01C. Пусть на ленте есть слово 11100. В результате работы МТ это слово превратится: 1110011110. Совокупность всех команд, которые может выполнить Мт, называется ее программой. Будем считать МТ заданной если заданы ее внешние и внутренние алфавиты , начальная конфигурация и указано, какие из символов обозначают пустую ячейку изакл. состояние.

42. Машина Тьюринга как преобразователь.

Рассмотрим МТ преобразователь.

Пуст внешний алгоритм А={S0, a,b, c, d}, Q={q0,q1, q2, q3,q4, q5}

Команды :

q0 a q1 a Л

q0 b q0 b Л

q2 a q5 d П

q0 c q0 с Л

q1 d q2 c П

q3 a q4 d Л

q4 d q2 c Л

Пустая ячейка S0 заключ. состояние q5 прогу МТ представим в виде таблицы.

А/Q

q 0

q 1

q 2

q 3

q 4

q 5

S0

-

-

-

-

-

C

a

q 1

-

q 5

q 4

-

C

b

q 0 аЛ

-

-

-

q 2сЛ

C

c

q 0сЛ

-

-

-

-

C

d

-

q 2сП

-

-

-

C



Реализуем программу автомата на слове: bcadc

Пусть начальное состояние q0 : bcacd  bcaccbcdcc

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации