35)Дать определение эйлеровых циклов и цепей,условия их существования в графе.Описать построения эйлерова цикла.

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

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

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

36)Дать определиние гамильтонова цикла и цепи.

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

Пример:

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

Условия гамильтоновости графа:

Условие 1(необходимое). Всякий гамильтонов граф двусвязен. Понятие двусвязности графа включает в себя след. Свойства : граф является связным, и минимальное число ребер,Ю которое нужно удалить для нарушения связности графа, равно 2.

Условие 2(достаточное). Пусть граф имеет больше 3 вершин. Пусть граф G имеет n больше 3 вершин. Если для всякого р, такого что р больше 1,но меньше (n - 1)/2, число вершин со степенями, не превосходящими р, меньше р, и для нечетного n, число вершин степени(n - 1)/2 не превосходит n , то G – гамильтонов граф. ЭЭто условие носит название теоремы Поша.

Условие 3(достаточное). Это условие является следствием из условия 2. Если в графе G, n больше или равно 3 вершин и для каждой пары смежных вершин х и у выполняется соотношение deg(x)+deg(y)>=n, то G – гамильтонов граф.

В частности, граф с n>=3 вершинами является гамильтоновым, если для каждой вершины х выполнено условие deg(x)>=n/2.

Существует связь между эйлеровыми и гамильтоновыми графами. Для того, чтобы её сформулировать , нам потребуется понятие реберного графа. Пусть имеется граф G. Построим по нему граф L(G) следующим образом: каждому ребру u графа G сопоставим вершину u_L графа L(G) . Вершины u_L v_L графа L(G) соединим ребром, тогда и только тогда, когда соответствующие им ребра u и v в графе G инцидентны одной и той же вершине. Полученный граф L(G) и будет называться реберным графом для графа G_Ю .

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

Теорема : Если G – эйлеров граф, то L(G) является эйлеровым и гамильтоновым. Если G – гамильтонов граф, то и L(G) гамильтонов.

38.

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

Длиной пути Р во взвешенном графе называется сумма весов всех входящих в него ребер.

Путь во взвешенном графе G из вершины v в вершину w, где v≠w, называется минимальным, если он имеет минимальную длину среди всех путей графа G.

Алгоритм Форда-Беллмана .

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

Граф представляется в виде взвешенной матрицы смежности S, причем в ней S(x,x)=0 и , для которых (y,z) не принадлежат U, причем в ней S(x,x)=0 и для которых (y,z) не принадлежат U, S(y,z)=∞. Результат формируется в массив d,в котором -искомые расстояния до вершины x. Ниже приводится индуктивное описание этого алгоритма.

Шаг 1. Рассматриваются вершины z, для которых r_x(z)=1. для них d(z)=S(x,z)

Шаг 2. Рассматриваются вершины z ранга r_x(z)=k. для них пересчет элемента d(z) осуществляется по формуле .

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

39.

Два графа G=(X,U) и L=(X',U') являются изоморфными, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг. Пример: следующие графы, приведенные на рисунке, изоморфны:

Два графа G=(X,U) и G'(Y,V) называются изоморфными, если существует такое взаимно-однозначное отображение φ: X→Y, при котором сохраняется отношение смежности между вершинами, т.е.

Так как X и Y являются конечными множествами, отображение φ, о котором идет речь, есть не что иное, как перестановка на n-элементном множестве. Матрицы смежности при этом переходят одна в другую при подходящей перестановке столбцов и строк. Перебор всех возможных перестановок всегда даст ответ, являются графы изоморфными или нет.

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

40.

Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Множество всех вершин одного цвета является назависимым и называется одноцветным классом. В n-раскраске графа G используется n цветов, и, таким образом ,эта раскраска разбивает V на n одноцветных классов. Хроматическое число χ(G) имеет n-раскраску. Граф G называется n-раскрашиваемым, если χ(G) ≤n, и n-хроматическим, если χ(G) =n.

Три раскраски графа

Поскольку граф G имеет р - раскраску и χ(G)-раскраску, он дожжен иметь также n-раскраску для любого n, удовлетворяющего неравенствам χ(G)<n<p. Граф на рис. является 2-хроматическим. На

Этом же рис приведены n-раскраски для n=2,3,4; положительные целые числа указывают цвета.

Граф яв-ся 1-хроматическим тогда и только тогда ,когда он несвязан.

Алгоритм построения раскраски графа в k+1 цветов:

Произвольной вершине v1 графа G припишем цвет 1.

Если вершины v1, v2, ...,vi раскрашены цветами 1, 2, ..., l, l<=i, то новой произвольно взятой вершине vi+1 припишем минимальный цвет, не использованный при раскраске смежных вершин.

41.Деревья

Неориентированным деревом Т будем называть связный неориентированный граф без циклов.

Ряд свойств:

• В дереве любые две вершины связаны единственной постой цепью

• Число ребер m в дереве на единицу меньше числа вершин n, т.е. n=m+1

• Добавление одного ребра между любой парой вершин дерева порождает ровно один простой цикл

• Каждое из этих свойств может рассматриваться как самостоятельное определение дерева, эквивалентное, взятому за основу.

Задача о минимальном соединении.

Решение её состоит в построении связной части Т, содержащей все вершины графа G и имеющей наименьший суммарный вес в нее ребер: .

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

1. Пусть Т – искомое дерево, X(T)- множество его вершин, U(T) –ребер. В начале X(T)=Ø и U(T)= Ø.

2. Выбираем ребро с минимальным весом и включаем его в U(T),а инцидентные ему вершины, пусть это будут x₀ и x₁, включаем в X(T).

3. затем просматриваем все ребра, инцидентные вершинам x₀ и x₁ и присоединяем ребро с наименьшим весом к U(T), а инцидентную ему вершину x₂ заносим в X(T). следим, чтоб вершины не повторялись(т.е. не возникал при этом простой цикл)

4. процедура выполняется до тех пор, пока не будут включены все вершины исходного графа в X(T).

Построение каркасного дерева в графе.

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

Каркасным деревом в графе G называется суграф G', обладающий следующими свойствами:

1)множество вершин V(G)= V(G');

2)множество ребер

3)G' является деревом.

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

На рис. Граф (а) и его каркасы обходами в глубину (б) и в ширину(в),из вершины x1.

На след. рис.(А) взвешенный граф и (Б) каркасное дерево минимальной стоимости.

42.

Ориентированным бинарным деревом называется дерево, обладающее следующими свойствами:

1) имеется ровно одна вершина, не имеющая ни одного исходящего ребра, она называется корнем;

2) каждая вершина, кроме корня, имеет не более одного входящего и не более двух исходящих ребер;

3) каждая вершина достижима из корня.

Алгоритм нумерации бинарных деревьев.

Известны три основные способа нумерации вершин бинарного дерева.

А)Нумерация вершин в прямом порядке.(рис)

Обход дерева в прямом порядке определяется в следующей рекурсией:

1. Пронумеровать корень;

2. Пронумеровать поддерево в прямом порядке;

3. Пронумеровать правое поддерево в прямом порядке.

В результате для каждого локального корня К и смежных ему вершин L(левая) и R(правая) должно выполнятся следующее отношение:

N (K) <N (L) <N (R), где N-означает номер.

Б)Нумерация вершин в обратном порядке.(рис)

1. Пронумеровать левое поддерево в обратном порядке;

2. Пронумеровать правое поддерево в обратном порядке;

3. Пронумеровать корень.

N (L) <N(R) <N (K), где N-означает номер.

В)Нумерация вершин в симметричном порядке(рис)

1. пронумеровать левое поддерево;

2. пронумеровать корень;

3. пронумеровать правое поддерево.

N (L) <N(К) <N (R), где N-означает номер.

Вычисление арифметических выражений.

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

Обход в прямом порядке даст выражение +ab, которое представляет собой префиксную форму записи суммы двух чисел a и b.

Обход в обратном порядке даст выражение ab+, которое представляет собой постфиксную форму записи суммы двух чисел a и b.

Обход в симметричном порядке даст выражение a+b, которое представляет собой префиксную форму записи суммы двух чисел a и b.

43.

Двудольный граф (биграф)- это граф, множество вершин V которого можно разбить на два подмножества V1 и V2 таким образом, что каждое ребро соединяет вершины из разных множеств. Например, на рис (А) граф можно представить как на рис (Б), чтобы показать, что этот граф двудольный.

Если граф содержит все ребра, соединяющие множества V1 и V2, этот граф называется полным двудольным.

Граф Двудольный тогда и только тогда, когда все циклы его имеют чётную длину.

Докажем это….

Здесь я долго разбиралась,но так толком ничего не поняла, поэтому только так.

Паросочетание – степени всех вершин не превышают единицу.

Будем говорить,что существует такое взаимно-однозначное соответствие между А и А', что соответствующие друг другу вершины соединены ребром.