Шпаргалка по "Дискретная математика"

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

(1)

Если к - наименьшее натуральное число с таким свойством, будем говорить о рекуррентной последовательности порядка к. Условие (1) будем называть рекуррентным соотношением порядка к.

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

 Опр 2. Последовательность будем называть линейной рекуррентной с постоянными коэффициентами, если для любого nÎN₀

 _{Справедливо}

   (2)

 где - заданная числовая последовательность.

 Если  b_п = О, то линейную рекуррентную последовательность назовем однородной, в противном случае неоднородной.

 Замечание 1. Уравнение (2), задающее ЛРП, будем называть линейным рекуррентным уравнением (ЛРУ), оно всегда имеет решение Такое решение будем называть тривиальным.

 Приведем  примеры ЛРП.

 Пример 1. Геометрическая прогрессия

 может быть задана рекуррентным уравнением

 Это - линейное однородное рекуррентное уравнение  первого порядка.

 Пример 2. Арифметическая прогрессия

 может быть задана рекуррентным уравнением

 Это - линейное неоднородное рекуррентное уравнение первого порядка.

 Опр 3. Последовательность, заданная рекуррентным уравнением

  (3)

 называется  арифметико-геометрической прогрессией. Очевидно, при q=1 получаем  арифметическую,   а  при   геометрическую прогрессию.

 Замечание 2. Основной задачей теории рекуррентно заданных последовательностей является следующая: по рекуррентному заданию последовательности найти явную формулу общего члена.

 Теорема   Пусть дана последовательность , заданная рекуррентным уравнением

 (4) где, по определению,

 Доказательство  проводится по индукции. Формула верна  для n=n₀

Для определения  констант имеем систему уравнений  

    ■

 В частном  случае, когда

    для любого и

 получаем

  (5)

 Пример 3. На сколько частей разбивают плоскость п прямых в общем положении (любая пара прямых пересекается, никакие три прямые не пересекаются в одной точке)?

 Решение. Обозначим количество областей, образуемых п прямыми, через . Очевидно, . Прямая с номером пересекается со всеми п прямыми и делится точками пересечения на часть, каждая из которых делит какую-то часть плоскости на две, поэтому возникает новая область, отсюда Решая это уравнение по формуле (5) и используя 1+2+…+m=(m(m+1))/2, получаем

6. Асимптотические  решения рекуррентных уравнений. Свойство Пуанкаре. Теоремы Пуанкаре и Перрона.

Определение.  Пусть дано линейное рекуррентное уравнение с постоянными коэффициентами вида

(1)

тогда если решение уравнения (1) имеет вид (2)

то решение  называют стационарным;

если  решение уравнения (1) удовлетворяет условию (3) где - стационарное решение, то решение называют асимптотически стационарным;

Замечание. Точка равновесия - это стационарное решение, а приближение к точке равновесия - асимптот. стационарное решение.

  Пример 1. Уравнение

(4)

имеет стационарное решение вида

(5)

(Если то стационарного решения не существует.)

Пример  2. В формуле Бине

для последовательности чисел Фибоначчи второе слагаемое  стремится к нулю

при , поэтому

,отсюда при больших п отношение

Замечание. На то, что существует у целого класса последовательностей, обратил внимание 90-е годы XIX века А.Пуанкаре.

Определение. Пусть дано линейное рекуррентное уравнение с переменными коэффициентами вида

(5)

причем  существуют пределы 

b. Тогда будем говорить, что уравнение (5) обладает свойством Пуанкаре.

Теорема 1 (Пуанкаре, 1885). Если уравнение (5), где , обладает свойством Пуанкаре, и если корни уравнения

удовлетворяют условию

то  для каждого нетривиального решения найдется такое

, что

В 1921 году О.Перрон усилил теорему Пуанкаре.

Теорема (Перрон, 1921). Если выполнены все условия теоремы 1, при этом для любых и , то существуют к линейно независимых решений уравнения (5)

x_n+k=a₁(n)x_n+k-1+ a₂(n)x_n+k-2+…+ a_k(n)x_n+b_n

9. Топологические операции  на графах. Примеры.  Свойства. Изоморфизм  графов.

Теорема. Пусть ,

 - подграфы графа Бержа .  Тогда выполняются следующие свойства:

11. Связность и К – связность графов.

Определение. Пусть дан граф G=(X,U,M). Пусть дана послед-ть вершин и веток

(*) такая, что любая тройка вида ,

Тогда будем  говорить, что задана цепь, начинающаяся в вершине Цепь обычно обозначают

если послед - ность (*) бесконечная, и , если послед - ность (*) конечная.

 В последнем  случае будем говорить, что цепь заканчивается в вершине

Если цепь конечна  и X_k совпадает с X_1, то говорят, что цепь замкнута.

  Количество веток в цепи будем называть ее длиной.

Пример Пусть , где граф G дан на рис. 3.3.1. Тогда будет цепью, а цепью не будет, так как в последовательности

тройка

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

Замкнутые цепи называют также циклами.

Определение. Пусть в графе дана цепь . Будем говорить, что цепь простая, если все ветки в цепи встречаются ровно один раз, и элементарная, если каждая вершина в послед - ности (*), кроме, может быть, первой и последней, встречается ровно один раз.

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

Пример. 

Определение  Пусть - конечный связный граф,   |U| = m Если m = n - 1, то граф называется деревом.

Вершины дерева, инцидентные только одному ребру, (степени 1) называются листьями.

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

Определение. Пусть Связный граф

                          Конечный связный граф. Граф называется к-связным, если:

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

2.  Никакое  подмножество . не обладает таким свойством. 

Число к называется числом связности графа.

Определение. Пусть дан граф , и пусть - цепь. Если все ветки цепи - дуги

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

Очевидно, сильно связный граф будет связным, но не наоборот, даже если этот граф - диграф без петель.

Теорема. _{Пусть конечный связный граф. Для того чтобы точка x0 была точкой сочленения  Н и Д, чтобы сущ-ли вершины a и b: любая цепь их соединяющая проходила через x0} 
 
 
 
 
 
 
 
 
 
 
 
 
 

Замечание: В дереве вершины, имеющие степень 1 называются листьями.

В дереве любая вершина, не являющаяся листом будет точкой простого сочленения. 

17.Геометрическая  реализация графов  в R³.Планарные графы. Непланарность графов К_3,3, К_5,0. Теорема Потрягина-Куратовского.

Опр. Пусть G=(X,U,M) - граф. Назовем

геометрической  реализацией графа G в трехмерном евклидовом пространстве R³множество состоящее из

1.  множества  точек (эти точки называют узловыми), при этом существует взаимно однозначное соответствие (биекция) между ;

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

При этом отображения  f и h связаны между собой так, что если тройка , то точки будут концами линии

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

Предложение 3.5.2. Графы K₅ и К_3,3 не планарны.

Доказательство. 1. Рассмотрим граф К₅ - полный неорграф Бержа без петель. Здесь n=5, m=10. Пусть существует его плоская реализация K’₅тогда по формуле Эйлера f=2-n+m=7  Так как граф не имеет кратных ребер, каждый регион ограничен не менее, чем 3 ребрами, при этом каждое ребро - граница двух регионов. Поэтому просуммировав границы всех регионов, получим 2m=20≥3f=21

Это противоречие доказывает, что К₅ не планарен. 

2. Граф K_3,3 содержит 6 вершин и 9 ребер. Это двудольный граф: множество его вершин разбито на два подмножества причем каждая вершина из соединена с каждой вершиной из Аналогично случаю 1, предполагаем планарность графа и получаем из формулы Эйлера f=2-6+9=5. Заметим, что двудольный граф не может содержать циклов длины 3, поэтому каждый регион ограничен не менее, чем 4 ребрами, поэтому 2m=18≥4f=20

Это противоречие доказывает, что не планарен.

(нарисовать К₅ и К_3,3) 
 
 

Теорема  3.5.3  (К.Куратовский   Л.С.Понтрягина) Для того, чтобы конечный неорграф был планарным, необходимо и достаточно, чтобы он не содержал подграфов, редуцируемых до или

18. Формала Эйлера и ее следствие.

Теорема (Формула Эйлера).

  ПустьG=(X,U,M)

- конечный связный  планарный граф, - его плоская геометрическая реализация. Пусть │X│=n,│U│=m, количество регионов включая бесконечный, равно f. Тогда n-m+f=2,

Доказательство. ν(G)=m-n+p где р =1. По теореме 3.5.2 ν(G)=f-1, отсюда f-1=m-n+1 и n-m+f=2

Предложение 3.5.1. Каждый планарный граф может быть правильно реализован на сфере и обратно, если граф может быть правильно реализован на сфере, то он планарен.

Следствие 3.5.1. Для правильной реализации графа G на сфере справедлива формула Эйлера n-m+f=2

Определение 3.5.3. Пусть К - многогранник в . Назовем его звездным, если существует внутренняя точка многогранника x₀, такая, что для любой точки х, лежащей на поверхности многогранника, весь отрезок принадлежит К. В частности, этим свойством обладают выпуклые многогранники.

Следствие 3.5.2. Пусть дан звездный многогранник К с п вершинами, т ребрами и  f гранями. Тогда справедлива формула Эйлера n-m+f=2.

(Теорема 3.5.2. Цикломатическое число связного конечного планарного графа G=(X,U,M) равно числу внутренних регионов его плоской реализации G^’. В качестве базиса циклов можно взять циклы, отвечающие границам регионов.)

Теорема 3.4.5.. Пусть G=(X,U,M)- конечный связный граф. Для того, чтобы граф был бихром-им, н. и д., чтобы он не сод-л циклов нечетной длины.

Доказательство. Пусть граф G – бихроматический. Возьмем произвольный цикл простой.

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

Опр. Пусть G=(X,U,M) – граф связный. Граф допускает правильную раскраску вершин в р-цветов, если  любые две соседние вершины окрашены в разные цвета.

Минимальное число  цветов, в которые могут быть окрашены вершины графа, называнется хроматическим числом.

Хроматическим числом (р-хроматическим) для графа G будем называть число, которое равно числу цветов его правильной раскраски и при этом не существует правильной раскраски в (р-1) цвет. Обозначается γ(G). Если р = 2, граф называется бихроматическим. 

3 цвета прав-й раск-ки 2 цвета 

22. Ядро графа. Две  теоремы о ядре  графа.

Опр. Пусть G=(X,F) - диграф. Подмножество будем называть ядром графа G, если оно одновременно и внешне и внутренне устойчиво, то есть

Пример. Если G - граф из рис., то будет ядро.

Зам. Из определения ядра следует, что диграф, у которого в каждой вершине петля, не имеет ядра. Бывают и диграфы без петель, не имеющие ядра. С другой стороны, диграф из примера имеет два различных ядра: S₁={x₁, x₃} и S₂={x₂,x₄}.

Теорема 1. Если S₀- ядро диграфа G=(X,F), то

Док – во: Так как S₀ внутренне устойчиво, Так как S₀ внешне устойчиво, .■

24. Двудольный граф. Теорема Кёнига. Примеры.

    Граф называется двудольным, если множество его вершин разбито на два непересекающихся подмножества (доли) так, что вершины из одной доли не являются соседними. Очевидно, бихроматический граф двудольный. Таким образом, теорема (Пусть G =(X,U,M) -  конечный связный граф. Для того, чтобы граф G был бихроматическим, необходимо  и достаточно, чтобы он не содержал циклов нечетной длины.) дает необходимое и достаточное условие того, чтобы граф был двудольным. В этой формулировке теорема была доказана Д.Кёнигом в 1936 г.

   Определение: Пусть G={Х₁UX₂,U,M)-  двудольный граф. Набор веток U' С U назовем независимым паросочетанием, если ветки из U' не имеют ни одной общей вершины. Паросочетание называется максимальным, если оно не содержится ни в каком другом паросочетании. Максимальное паросочетание называется совершенным, если любая вершина графа инцидентна какой – либо из веток паросочетания.

Пример 1. Пусть G дан на рисунке. Набор U'={u₁,u_3,u₅} будет независимым паросочетанием.

Замечание. Описание максимальных независимых паросочетаний оказалось весьма полезным во многих физических, химических, биологических проблемах.. Центральное место в теории паросочетаний занимает теорема, первая версия которой была доказана в 1917 году Фробениусом. Впоследствии теорема была обобщена Ф.Холлом и Д.Кёнигом. (В некоторых книгах эта теорема называется теоремой Кёнига).

  Теорема (Ф.Фробениус, Ф.Холл, Д.Кёниг). 

Пусть G = (Х₁UX₂,U,M)  = (Х₁UX₂,F)  - связный двудольный диграф,  причем | Х₁| =| Х₂| = п  и начала всех дуг находятся в Х₁ . Для того чтобы существовало совершенное napocoчетание U' С U : |U'| = п, необходимо и достаточно, чтобы для любого

 S С Х₁  |F(S)|≥|S|.

  Замечание . Теорема (Ф.Фробениус, Ф.Холл, Д.Кёниг) известна как теорема о свадьбах.. Вариант формулировки: если есть п юношей и п девушек,

причем для  любого подмножества из к юношей, 1  ≤  k ≤ n,   количество знакомых девушек больше или равно k, тогда каждый юноша может жениться на знакомой ему девушке. Можно придумать и более серьезное применение: если n человек должны занять n должностей, причем каждая группа из k человек, 1  ≤ k ≤ n, может занять не меньше, чем k должностей, можно сопоставить каждому человеку должность, с которой он справится.

 Определение1. Целой частью числа (обозначение ) назовем наибольшее целое число, не превосходящее х.

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

 Определение2. Верхней целой частью числа (обозначение ) назовем наименьшее целое число, большее или равное х.

 Например,

 Очевидно,  

 4. Матрица Казорати. Предложения о решении ЛРУ k-го порядка.

Определение. Рассмотрим т последовательностей Будем говорить, что эти последовательности линейно зависимы, если существуют такие постоянные ,не все одновременно равные нулю, что для каждого выполняется равенство

(1)

 В противном  случае последовательности называются линейно независимыми.

 Определение. Рассмотрим т последовательностей Матрицу

(2)

будем называть матрицей Казорати. Определитель матрицы Казорати будем называть определителем Казорати.

 Предложение.

Последовательности линейно независимы тогда и только тогда, когда для любого

 определитель Казорати не равен 0.

 Доказательство. Последовательности линейно зависимы тогда и только тогда, когда линейная однородная система уравнений

имеет нетривиальное решение, а это, в свою очередь, равносильно тому, что определитель системы, являющийся определителем Казорати, равен нулю.

 Предложение. Если - линейно независимые решения (3), тогда общее решение этого уравнения имеет вид

  (4)

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

 Перейдем  к решению неоднородных уравнений

 (5).

 Теорема. Общее решение уравнения (5) равно сумме общего решения уравнения (3) и частного решения (5).

5. Сравнение   роста   и   убывания

последовательностей. Символы. Примеры.

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

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

 и  тогда говорим, что является бесконечно малой относительно и пишем

  Определение.  Пусть две посл-ти таковы, что существует постоянная _,такая, что начиная с некоторого номера x_n < Cy_n, тогда говорим, что (х_п) является ограниченной относительно и пишем

Например, _{,так как легко показать, что}                 

для всех n є N.

Замечание. Обозначение _или

 используется на практике только тогда, когда функция g(n) яв-ся более простой и не растет слишком быстро по сравнению с f(n). Иначе говоря, функция g(n) должна хорошо передавать характер роста функции f(n) и яв-ся ее очень близким верхним ограничителем. Для того чтобы фун-ии f  и g росли с одинаковой скоростью потребуем, чтобы выполнялось (f(n))=O(g(n)), (g(n))=O(f(n))

Определение. Если существуют постоянные и такие, что начиная с некоторого номера выполняется

говорят, что  посл-ти имеют один порядок, обозначим это

Предложение. Если существует конечный

то

В этом случае говорят, что . Заметим, что

_{Теорема. (Чебышёва о распределении простых чисел). Пусть -число простых чисел, не превосходящих натурального числа n. Тогда}

_{Замечание. На практике при решении рекур-х урав-й очень часто возникают решения для посл-ти расходящихся. Для анализа этих посл-й используются так называемые асимптатические ряды.}

8. Графы. Определения.  Классификации. Примеры.  Теорема о сумме  степеней вершин  графа.

Опр. Пусть даны два множества X и U : . Множество X будем называть множеством вершин, множество U — множеством веток. Пусть

Опр.(Классификация веток). Пусть -граф.

a) Ветка называется дугой, если для любых из того, что , следует, что . Вершину х назовем началом дуги, а вершину у — концом дуги. Подмножество множества U, состоящее из всех дуг обозначим через

b) Ветка называется петлей, если существует такая, что Множество петель обозначим через U.

с) Ветка называется ребром или неориентированной веткой, если для любых из того, что следует, что Множество всех ребер обозначим через

Опр. Граф , будем называть

a)   ориентированным  графом,   если ,   и   собственно ориентированным графом, если дополнительно и Ориентированные графы в XX веке назывались орграфами, а теперь диграфами (от англ. directed graph)

b)  неориентированным графом, если , и собственно неориентированным графом, если дополнительно и . Неориентированные графы называют неорграфами.

c)  Если и , то граф G называют смешанным. Граф из примера 3.1.1, изображенный на рис. 3.1.2, - смешанный.

Замечание. Вершинный граф , а также граф, состоящий из одних петель, относят и к ориентированным, и к неориентированным графам. 

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

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

Опр. Пусть п - число  вершин графа

G   = Назовем G простым графом, если любые две различные вершины в G соединены не более, чем одной веткой.

Опр. Неориентированный граф, содержащий петли и (или) кратные ребра, называют псевдографом.

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

  Опр.  Пусть _{- собственный диграф. Введем на вершинах этого графа отображение, сопоставляющее каждой вершине концы дуг, выходящих из этой вершины. Это отображение принято называть мультифункцией.}

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

Опр. Пусть дан граф, _{конечный} и x X. Число веток, инцидентных вершине x, называется степенью вершины. Это число обозначается р(х). Число дуг имеющих начало в вершине х назовем полустепенъю исхода (обозначение р⁺(х)), число дуг, имеющих конец вершине х назовем полустепенью захода (обозначение р^-(х)).

Если G- диграф без петель, то для любой вершины справедливо

13. Цикломатическое  число. Предложение  о цикломатическом  числе и его  следствие.

О. Пусть G=(X,U,M) - конечный граф, |X|=n, |U|=m и пусть число компонент связности графа равно р. Число (G)=m-n+p будем называть цикломатическим числом графа.

Пр. В графе G на рис. имеем:n=5, m=4,p=2

(G)=4-5+2=1

Предл. ПустьG=(X,U,M) - конечный граф, |X|=n, |U|=m  , число компонент связности графа равно р. Пусть G' - граф, образующийся из G добавлением одного ребра v. Соответствующие параметры графа G'будем обозначать со штрихом. Положим

_{ρ(G)=n-р, тогда}

1.   если  в графе G'ребро v соединяет вершины из разных компонент связности, то ν(G^’)=ν(G),ρ(G^’)=ρ(G)+1

2.   если  в графе G'ребро v соединяет вершины из одной компоненты связности, то ν(G^’)=ν(G)+1, ρ(G’)=ρ(G); 

Доказательство. В первом случае p’=p-1, n’=n, m’=m+1;

во втором случае 2p’=p, n’=n, m’=m+1; из (G)=m-n+p и ρ(G)=n-p следует требуемое.

Следс. Для любого конечного графа G ν(G)≥0, ρ(G)≥0,

Док-во.   Рассмотрим   вершинный   граф G_X,Ø=(X,Ø,Ø) с тем же, что и у G множеством вершин. Заметим, что ν(G_x,Ø)=0, ρ(G_x,Ø)=0

Так как граф G можно получить из G_X,Ø добавлением последовательно т ребер, из предложения (G)=m-n+p получаем требуемое.

14.Теорема  о базисе пространства  цикла графов. Следствие.

Определение 3.4.5. Пусть G=(X,U,M) - конечный граф

такой, что │∆G│>0. Пусть μ₁, …, μ_k принадлежат ∆G.

 Будем говорить, что циклы μ₁, …, μ_k независимы, если векторы линейно независимы.

      Набор циклов μ₁, …, μ_k будем называть базисом в ∆G , если μ₁, …, μ_k независимы и любой цикл μ из ∆ G можно единственным образом представить в виде линейной комбинации циклов из μ₁, …, μ_k:

(3.4.5)

Заметим, что  при этом

Теорема 3.4.1. ПустьG=(X,U,M) - конечный граф, тогда число циклов, образующих базис в ∆ G, равно цикломатическому числу ν(G).

Идея доказательства. В доказательстве будем обозначать число вершин через n, веток через т, число компонент связности через р. Напомним, что ν(G)=m-n+p, доказательство проводится индукцией по т.

Итак, базис в состоит из элементов.

Следствие  Любой набор независимых циклов,   число которых равно , будет базисом в

Предл.3.4.1. ПустьG=(X,U,M) - конечный граф, |X|=n, |U|=m  , число компонент связности графа равно р. Пусть G' - граф, образующийся из G добавлением одного ребра v. Соответствующие параметры графа G'будем обозначать со штрихом. Положим

_{ρ(G)=n-р, тогда}

1.   если  в графе G'ребро v соединяет вершины из разных компонент связности, то ν(G^’)=ν(G),ρ(G^’)=ρ(G)+1

2.   если  в графе G'ребро v соединяет вершины из одной компоненты связности, то ν(G^’)=ν(G)+1, ρ(G’)=ρ(G);

Определение 3.4.2. Рассмотрим цепь μ= (x₀, u₁, x₁, u₂, …, x_k, …). Если вершины x₀ и x_k совпадают, цепь μ будем называть замкнутой цепью,  или циклом.

16. Теорема(алгоритм Краскала)

Теорема 3.4.3 (алгоритм Краскала). Пусть G=(X,U,M)

- конечный связный граф,│X│=n,U≠Ø_.Пусть ρ:U→R₊∪{0}- некоторая весовая функция на U. Для того, чтобы найти остовное дерево Т с минимальным весом, достаточно соблюдать следующий алгоритм:

1.   выбираем ветку U1с минимальным весом;

2.   выбираем последовательно  веткиU₁,…,U_n-1, при этом на каждом шаге выбираем ветку с минимальным из невыбранных весом такую, что она не образует цикла с выбранными ранее.

Доказательство. Из теоремы 3.4.2 (пункт 3) следует, что подграф, построенный по алгоритму Краскала - дерево. Докажем, что Т - дерево с минимальным весом. Предположим, что

не минимально, то есть существует остовное дерево S :

(3.4.6)

Пусть U_k- первая ветка в Т, которая не принадлежит S. Рассмотрим Очевидно, что S_k содержит цикл С (в силу теоремы 3.4.2(4)), который проходит через U_k , заметим также, что С содержит ветку и такую, что , (Если бы цикл С целиком содержался в Т, это противоречило бы теореме 3.4.2(1)). Заменим в S ветку и на ветку и_k. Получим подграф , который будет деревом, так как связность не нарушена - мы удалили ветку, принадлежащую циклу С, кроме того, граф имеет п вершин и n -1 ветку, что достаточно по теореме 3.4.2(3).

Но по выбору u_k в алгоритме Краскала , значит,

, при этом  число общих веток у и Т на одну больше, чем у S и Т. Продолжая этот процесс, можно преобразовать S в Т, при этом вес подграфа не может возрасти. В итоге получим , что противоречит (3.4.6).

Пример 3.4.3. Найти минимальное остовное дерево в графе G на рис.3.4.6. По алгоритму Краскала находим: n=7

Теорема 3.4.2 (о  дереве). ПустьG=(X,U,M) - конечный

граф,│X│=n≥2. Тогда следующие условия равносильны:

1.  G - связный граф и не содержит нетривиальных циклов;

2.  G не содержит нетривиальных циклов и имеет п—1 ветку;

3.  G - связный граф и имеет п — 1 ветку;

4- G не содержит нетривиальных циклов, но добавление любой ветки приводит к их появлению;

5.  G - связный граф, но удаление любой ветки нарушает связность;

6.  Любые две вершины  графа G можно соединить единственной простой цепью.

20. Теорема Рамсея. Примеры.

Т.(Ф.Рамсей). Пусть - натуральные числа, Если ребра полного неориентированного графа K_n покрасить в два цвета (например, в красный и синий), то в K_n существует либо покрашенный в один из цветов полный подграф К_r, либо покрашенный в другой цвет полный подграф К_b

Замечание.В простейшем случае _{r=b=3, n=C4²=6} теорема Рамсея часто формулируется так: "В любой компании из 6 человек найдется либо 3 попарно знакомых, либо 3 попарно незнакомых".

Док-во. Сопоставим людям вершины графа, если люди знакомы, соединим соответствующие вершины красным ребром, если незнакомы, синим. Получим полный граф K₆ ребра которого раскрашены в два цвета. Возьмем произвольную вершину А. Ее степень равна 5, поэтому из нее выходят по крайней мере 3 ребра АВ, AC, AD одного цвета, допустим, красного. Если хотя бы одно из ребер ВС, BD, CD красное, получим красный треугольник с вершиной А. Если нет, треугольник BCD синий.

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

Опр. Пусть G=(X,F) - диграф. Множество S

Обозначим множество  всех внутренне устойчивых подмножеств графа G через A(G). Числом внутренней устойчивости называется число

    , где - внутренне устойчивое.

  Пример:   
 
 

Теорема 1. Пусть G=(X,F) - конечный диграф. Тогда

Д-во: Пусть - хроматическое число. Тогда вершины диграфа G можно правильно раскрасить в р цветов. Пусть S_i – множество вершин, окрашенных в i-ый цвет (i=1..p). Тогда Отсюда, учитывая, что каждое множество Si внутренне устойчиво, получаем

Пр. Пусть G - диграф, данный на рис. Пусть . Очевидно, что S - внутренне устойчивое множество. Так как любое множество, содержащее 3 вершины графа G, не будет внутренне устойчивым, то Так как в нашем случае На самом деле

Опр. Пусть G=(X,F) - связный диграф. Множество будем называть внешне устойчивым, если выполняется

, что равносильно  

Обозначим множество  всех внешне устойчивых подмножеств  графа G через В(G). Числом внешней устойчивости диграфа G назовем число

Пример 3.6.3. Пусть - диграф, данный на рис. Тогда никакое одноточечное множество вершин не будет внешне устойчивым. Любое двухточечное множество, например, будет внешне устойчивым. Значит,

  Множество, которое одновременно внутренне и внешне устойчивое называется ядром.

25. Функция Гранди. Прогресс-кон. граф.

Опр-е: Пусть G=(X,F) – диграф Бержа без петель. Функцию g: X→N₀ будем называть функцией Гранди, если g(x_i)=min{k принадл. N₀: k ¢ g(F(x_i)) }, i=1,..,|X|,

где g(F(x_i)) – множ-во значений функции G на мн-ве F(x_i).

Замечание: В диграфе Бержа иногда можно определить две функции Гранди, иногда ни одной.

ни одной

две

Предложение: Если диграф G=(X,F) имеет ф-ю Гранди  g  и для некоторого х принадл. Х оказывается, что F(x)=Ø, то g(x)=0.

Теорема: Пусть G=(X,F) – связный конечный симметричный диграф без петель. Для того чтобы диграф G был р-хроматическим с р≤|X|, Н. и Д., чтобы он обладал функцией Гранди со значениями 0,1,..р-1 и не существовало бы функции Гранди с максимальным значением меньше р-1.

Опр-е: Диграф G= (X,F) наз-ся прогрессивно-конечным,если существует k принадл. N , такое что для любой вершины х принадл. Х любой (необязательно простой) путь,  начинающийся в этой вершине, имеет длину не больше k.

Теорема: Пусть G=(X,F) – связный диграф Бержа без петель, при этом G прогрессивно конечен. Тогда G имеет функцию Гранди, притом только одну.

Теорема: Пусть G=(X,F) – диграф, имеющий функцию Гранди. Пусть S={x принадл. X: g(x)=0}. Тогда S будет ядром графа G.

 Теорема1. Если последовательности     - решения однородного ЛРУ

  (1)

 то  для любых констант последовательность , где

  (2)

 также будет решением (1).

 Доказательство.

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

 Замечание: Св-во общих решений лин-х рекур-х выражений очень похожи на св-во лин-х дифф-х урав-й соотв-го порядка.

 Определение2.  Уравнение (3).

 называется    характеристическим   уравнением    для    уравнения (1).

 Предложение1. Последовательность является решением уравнения (1) тогда и только тогда, когда t - корень характеристического уравнения (3).

 Теорема2  Если уравнение (3) имеет 2 различных вещественных корня и общее решение уравнения (1) имеет вид

  (4)

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

 имеет единственное решение С₁, С₂

    ■

Пример . (Леонардо Фибоначчи )

Пара кроликов приносит раз в месяц приплод  из двух крольчат (самки и самца), причем новорожденные кролики через  два месяца после рождения уже  приносят приплод. Сколько крольчат появиться через год, если вначале  года была одна пара новорожденных  кроликов?

Обозначим через количество пар кроликов в начале n-го месяца. Тогда (у самых первых кроликов родилась еще одна пара), и вообще

Последовательность,   заданная   этим  рекуррентным   уравнением с  начальными  условиями  , ,   называется   последовательностью   Фибоначчи.   Характеристическое   уравнение имеет вид , его корни поэтому общее решение имеет вид

Для определения  констант имеем систему уравнений

Решая ее, получаем

В итоге  получаем формулу Вине для чисел Фибоначчи,

  (5)

 Предложение 2

  Доказательство.   Запишем  основное  уравнение  как f_k+2 – f_k+1=f_k         и подставим вместо к числа от 0 до n. Получим                                                                                             
 
 
 

 Сложив, получим

 учитывая, что получаем требуемое.

 Теорема3. Если уравнение (3) имеет 1 вещественный корень t, то общее решение уравнения (1) имеет вид

  (6)

 Доказательство. Очевидно, последовательность удовлетворяет уравнению (1). Докажем, что это верно и для . Так как t - корень кратности два многочлена — , t является также корнем его производной . Поэтому

 По  теореме1 будет решением (1). При любом выборе начальных условий система уравнений

 имеет единственное решение, так как определитель системы

  в рассматриваемом  нами случае.

 Теорема4  Если уравнение (3) имеет 2 комплексно сопряженных корня то общее решение уравнения (1) имеет вид

    (7)

 Замечание: Аналогично решению хар-го урав-я 2-го порядка решается урав-е и более высоких порядков.

 Теорема5. Пусть

   (8)

 ЛРУ к-го порядка и характеристическое уравнение

  имеет к различных вещественных корней ,  Тогда общее решение ЛРУ имеет вид

    (9)

 Доказательство. В доказательстве нуждается лишь то, что для любого выбора начальных условий

 найдутся  константы  такие, что  (9)  удовлетворяет начальным условиям. Определитель соответствующей линейной системы - это определитель Вандермонда, равный

так как  все корни различны.

7. Формулы разностей.  Формулы суммирования  Эйлера. Примеры.

10. Алгебраические операции  на графах.

Определение 3.2.6.

  Пусть произвольные

диграфы.   

1.  Произведением назовем диграф такой, что

2.   Специальной суммой назовем диграф такой, что

3.Композицией назовем диграф           такой, что

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

Определение 3.2.7. Пусть и . - матрицы . Тогда объединением матриц называется матрица

 где Пересечением матриц называется матрица

где

Пример 3.2.7. Пусть

Тогда

Определение 3.2.8. Пусть и - квадратные матрицы и Тогда их правым прямым произведением

назовем матрицу

Пример 3.2.8. Пусть

P_G – матрица смежности полного диграфа Бержа с n-вершинами, а Е_G - матрица смежности графа с n-вершинами, каждая из которых инцендентна единственной петле.

Опр-е: Пусть G=(X,U,M) u H=(Y,V,K) – конечные графы, |X|=n, |Y|=m, X∩Y=Ø. Соединением графов G∞H назовём граф В=(XỤY,W,N), где W=UỤVỤ(мн-во рёбер {u_ij}, соединяющих каждую вершину из Х с каждой вершиной из Y), N=MỤKỤM_nm, где M_nm={(x_i,u_ij,y_j), i=1..n, j=1..m}.

Соединение G₁ ∞G₂ двух вершинных графов G₁=(Х,Ø,Ø) и G₂=(Y,Ø,Ø), где |X|=n, |Y|=m, будем обозначать через К_n,m и называть полным двудольным графом с n u m вершинами в долях.

12 вопрос. Геодезическая  метрика.

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

Предложение 3.3.2. Расстояние обладает следующими тремя свойствами:

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

Определение. Пусть - конечный связный граф с геодезической метрикой    Величину

назовем   удаленностью вершины х. Вершину такую, что

назовем центроидной вершиной графа, а величину r_g - радиусом графа.

Аналогично, вершины, имеющие максимальную удаленность  такую, что

  назовем периферийной вершиной графа, а величину -

диаметром 
 
 
 
 
 

Теорема. Для любого конечного связного графа G

Теорема Пусть - конечный связный граф, . Если . - периферийная вершина, то она не является точкой сочленения.

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

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

15. Теорема о дереве.

Теорема 3.4.2 (о  дереве). ПустьG=(X,U,M) - конечный

граф,│X│=n≥2. Тогда следующие условия равносильны:

1.  G - связный граф и не содержит нетривиальных циклов;

2.  G не содержит нетривиальных циклов и имеет п—1 ветку;

3.  G - связный граф и имеет п — 1 ветку;

4- G не содержит нетривиальных циклов, но добавление любой ветки приводит к их появлению;

5.  G - связный граф, но удаление любой ветки нарушает связность;

6.  Любые две вершины  графа G можно соединить единственной простой цепью.

Доказательство.  В доказательстве будем обозначать число веток через т, число компонент связности через р.

1⇒2 Так как граф связен, p=1; G не содержит нетривиальных циклов, поэтому по теореме 3.4.1   ν(G)=0, отсюда m-n+p=m-n+1=0 и m=n-1

2⇒3 . G не содержит нетривиальных циклов, поэтому ν(G)=0  отсюда, так как m=n-1, m-n+p=n-1-n+p=0 и p=1,

_3⇒4 . По условию р = 1 и m=n-1. Тогда ν(G)=m-n+p=

n-1-n+1=0 и граф не содержит нетривиальных циклов. По предложению 3.4.1 добавление любой ветки в связном графе увеличивает цикломатическое число на 1, отсюда по теореме 3.4.1 появляется хотя бы один нетривиальный цикл.

  _4⇒5 По теореме 3.4.1ν(G)=0. Предположим, что G содержит хотя бы 2 компоненты связности. Тогда по предложению 3.4.1 добавление ветки, соединяющей вершины разных компонент связности не увеличивает цикломатическое число, что противоречит 4. Значит, граф G связен и р = 1, отсюда m=ν(G)+n-p=n-1  Если теперь удалить из G произвольную ветку, в новом графе G'получим m’=m-1=n-1-1=n-2, ν(G’)=ν(G), n’=n, ,

Отсюда p’=ν(G’)-m’+n’=0-(n-2)+n=2 то есть граф G'

несвязен.

_5⇒6 По условию граф G связен, следовательно любые две его вершины можно соединить цепью, причем можно выбрать простую цепь, соединяющую эти вершины. Предположим, что существует пара вершин, которые можно соединить двумя различными простыми цепями. Тогда существует хотя бы одна ветка v, принадлежащая одной из цепей, но не принадлежащая другой. Удалив ее, мы не нарушим связности графа, что противоречит 5.

_6⇒1. Из условия 6. следует, что граф G связен. Если бы граф G содержал хотя бы один нетривиальный цикл, то удалив из него ветки, по которым цикл проходит одинаковое число раз в разных направлениях, а также заменив 2 и более прохождения в одном направлении на одно, получим простой цикл. Любые две его вершины можно соединить двумя различными простыми цепями, что противоречит 6. ■ 

Предл.3.4.1. ПустьG=(X,U,M) - конечный граф, |X|=n, |U|=m  , число компонент связности графа равно р. Пусть G' - граф, образующийся из G добавлением одного ребра v. Соответствующие параметры графа G'будем обозначать со штрихом. Положим

_{ρ(G)=n-р, тогда}

1.   если  в графе G'ребро v соединяет вершины из разных компонент связности, то ν(G^’)=ν(G),ρ(G^’)=ρ(G)+1

2.   если  в графе G'ребро v соединяет вершины из одной компоненты связности, то ν(G^’)=ν(G)+1, ρ(G’)=ρ(G); 

(Теорема 3.4.1. ПустьG=(X,U,M) - конечный граф, тогда число циклов, образующих базис в ∆ G, равно цикломатическому числу ν(G).)

19. Графы на двумерных  ориентированных  замкнутых поверхностях. Гипотеза Хивуда. 

Определение 3.5.6. Граф G=(X,U,M) будем называть графом р-го рода, р принадлежит N₀ , если существует правильная реализация графа G на двумерной замкнутой ориентированной поверхности рода р, т.е. на сфере с р ручками(обозначение этой сферы S_p) .

р=0  =4 р=1   

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

Назовем правильную реализацию связного  графа G без мостов на S_p картой (Обозначение Ğ). Будем говорить, что карта правильно окрашена, если любые два соседних региона имеют разные цвета. Обозначим через минимальное число цветов необходимое для раскраски карты Ğ.

Назовем минимальное  число цветов, необходимое для  правильной раскраски любой карты на поверхности S_p хроматическим числом   поверхности   (обозначение Очевидно Ğ) 

В 1890 году П.Хивуд выдвинул гипотезу, которая была доказана в 1968 году для всех р, кроме р = 0, немецким математиком Г.Рингелем и американцем Дж. Янгсом.

Теорема 3.5.5 (Рингель, Янгс). Пусть S_p- двумерная замкнутая ориентируемая поверхность рода . Тогда

Например,

23. Эйлеровы и гамильтоновы графы. Теорема Эйлера.Теорема Дирака. Примеры.

Опр. Пусть G=(X,U,M) - связный конечный граф. Простой цикл, содержащий все ветки графа, будем называть эйлеровым, а граф, для которого существует эйлеров цикл, также назовем эйлеровым.

Пример:  
 
 

Теорема 1 (Эйлер, 1736.) Для того, чтобы связный конечный граф без петель G=(X,U,M) был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были четными.

Следствие1. Для того чтобы в связном конечном графе без петель G = (X, U, М)  существовала простая цепь, проходящая через все ветки графа и соединяющая вершины х₁ и х₂ (такая цепь также называется эйлеровой), необходимо и достаточно, чтобы х₁ и х₂ были единственными вершинами нечетной стeneнu.

Замечание . В 30-х годах XVIII века была популярна задача о Кенигсбергских мостах. В фарватере реки Прегель находятся два острова А и В, которые соединены друг с другом и с берегами С и D семью мостами (рис.1). Можно ли пройти по ному разу по всем мостам и вернуться в исходную точку? Эйлер доказал невозможность такого обхода, нарисовав граф, вершинами второго служат берега и острова, а ветками - мосты (рис.2). Граф не эйлеров, так как степени всех вершин нечетны, значит, такой обход невозможен даже без требования вернуться в исходную точку

рис.2

Замечание Теорема и следствие 1 верны даже для графа с петлями, если считать, что каждая петля учитывается в степени вершины с кратностью 2.

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

Опр. Пусть G=(X,U,M) - связный конечный граф. Элементарный цикл, содержащий все вершины графа, будем называть гамильтоновым, граф для которого существует гамильтонов цикл, также назовём гамильтоновым. (т.е. Граф называется гамильтоновым, если существует элементарный цикл,проходящий через все вершины графа)

пример: 
 

Замечание: Для гамельтоновых графов условие необходимости и достаточности пока не найдено. Есть

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

Теорема. (Дирак, 1952) Пусть G=(X,U,M) - связный конечный граф, Если для любой вершины выполняется неравенство граф будет гамильтоновым.

Пример: Пусть дан граф G. p(x_i)=3>4/2. Значит, G гамильтонов.