Пространство решений и его размерность. Определение базисных решений. Формула Бине.
Пусть функция в соотношении (1) является линейной
, , (9)
где – некоторые числа. Такие соотношения называют линейными соотношениями -го порядка с постоянными коэффициентами.
Сначала исследуем подробно соотношения второго порядка, а затем перейдем к общему случаю. При из формулы (9) получим
, . (10)
Решение этих соотношений основано на следующих легко доказываемых утверждениях.
Лемма 1. Пусть – решение соотношения (10), а – любое число. Тогда последовательность также является решением этого соотношения.
Лемма 2. Пусть и – решения соотношения (10). Тогда последовательность также является решением этого соотношения.
Из этих двух простых лемм можно сделать следующий важный вывод. Совокупность всевозможных последовательностей с операциями покоординатного сложения и умножения на скаляр образует векторное пространство. Совокупность последовательностей, являющихся решениями соотношения (10), представляет собой подпространство этого пространства. Объемлющее пространство всевозможных последовательностей бесконечномерно, но подпространство решений линейного рекуррентного соотношения имеет конечную размерность, равную порядку уравнения.
Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.
Из леммы 3 следует, что для определения всех решений уравнения (12) необходимо отыскать два линейно независимых решения. Любое другое решение будет представляться линейной комбинацией этих базисных решений.
Рассмотрим рекуррентное соотношение первого порядка
, (11)
где – константа.
Если , то из (11) имеем
, (12)
то есть решением рекуррентного уравнения первого порядка является геометрическая прогрессия.
Будем искать решение рекуррентного соотношения второго порядка также в виде (12). Тогда, подставляя (12) в (10), получим
. (13)
При =0 имеем нулевое решение, которое не представляет интереса. Считая , поделим последнее соотношение на :
(14)
Таким образом, геометрическая прогрессия (12) является решением рекуррентного соотношения (10), если знаменатель прогрессии является корнем квадратного уравнения (14). Это уравнение называется характеристическим уравнением для рекуррентного соотношения (10).
Построение базисных решений зависит от корней и характеристического уравнения (14).
( ). В этом случае имеем два решения и , которые линейно независимы. Чтобы убедиться в этом, покажем, что из формулы
(15)
путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение . Выберем константы и так, чтобы при и :
(16)
Определитель линейной системы (16)
следовательно, система имеет единственное решение, а значит формула (15) – общее решения соотношения (10).
. В случае кратных корней характеристическое уравнение (13) имеет вид или . Тогда , , а для соотношения (10) получим уравнение , которое дает два базисных решения и . Общее решение представляется в виде
. (17)
В случае соотношения -го порядка (9) имеют место утверждения, аналогичные тем, которые были рассмотрены для уравнений 2-го порядка.
Совокупность всех решений уравнения (9) является подпространством в пространстве всех последовательностей.
Размерность этого пространства равна , то есть каждое решение однозначно определяется своими первыми значениями.
Для определения базиса подпространства решений составляется характеристическое уравнение
. (18)
Многочлен
(19)
называется характеристическим многочленом рекуррентного соотношения (9).
Если характеристическое уравнение имеет различных корней , то общее решение рекуррентного соотношения (9) имеет вид
. (20)
При заданных начальных значениях решения , , константы находятся из системы
Если – корень характеристического уравнения кратности , то соотношение (9) имеет следующие решения
.
Пусть характеристическое уравнение (18) имеет корни: , ,…, кратности соответственно , ,…, , причем . Тогда характеристический многочлен и общее решение соотношения (9) представятся в виде
,
.
Пример 3. Формула Бине. Поставим задачу получить формулу в явном виде для чисел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что . Составим характеристическое уравнение , найдем его корни и получим общее решение . Константы и определим из начальных условий: . Тогда или
, (21)
где – золотое сечение. Формула (21) называется формулой Бине. При этом . Из формулы Бине следует, что .
13. Определение производящей функции. Свойства линейности, дифференцирования, умножения на параметр t, интегрирования. Примеры.
Производящей функцией, или обычной производящей функцией, последовательности чисел называется формальный ряд
(1)
где – формальная переменная. При этом будем писать .
Пусть, например, . Тогда
.
Аналогично
.
Экспоненциальной производящей функцией последовательности называется ряд
(2)
Производящие функции позволяют установить различные свойства последовательностей , в том числе связанные с комбинаторными задачами. Кроме того, с помощью производящих функций можно решать рекуррентные соотношения.
Свойства производящих функций
Линейной комбинации последовательностей взаимно однозначно соответствует линейная комбинация их производящих функций:
Дифференцирование производящей функции : .
Например, дифференцируя функцию , получим
,
то есть производящей функцией последовательности является функция : .
Дифференцируя раз функцию , будем иметь
.
После деления на получим производящую функцию для сочетаний
. (3)
3) Умножение производящей функции на соответствует сдвигу членов последовательности на одну позицию вправо. Если , то .
Например, производящей функцией последовательности (0, 1, 2, …, , …) является функция : .
Интегрирование производящей функции :
В качестве примера найдем . Используем формулу бинома Ньютона
. (4)
Числа называют биномиальными коэффициентами. При :
. (5)
Из равенства (5) следует, что функция является производящей для последовательности . Можно также написать
. (6)
Интегрируя левую часть соотношения (5), получим
.
Для правой части имеем
.
При находим
.
14. Производящая функция для свертки последовательностей. Формула Вандермонда. Формула бинома Ньютона для вещественного показателя.
Формула бинома Ньютона для вещественного показателя.
, (7)
5) Производящая функция для свертки последовательностей. Сверткой последовательностей и называется последовательность , элементы которой вычисляются по правилу: , , , …, , …
Операция свертки является основной в цифровой обработке сигналов: после свертывания последовательности отсчетов сигнала со специально подобранной последовательностью происходит фильтрация – усиление одних частот и подавление других.
Свертка обозначается звездочкой: .
Производящая функция свертки равна произведению производящих функций свертываемых последовательностей:
.
Действительно, при перемножении и -ая степень переменной складывается из всевозможных произведений , в которых первый сомножитель из , а второй из .
Пример. Формула Вандермонда. Пусть
, .
По правилу свертки . С другой стороны,
.
Следовательно,
. (9)
15. Определение числа расстановок скобок в выражении с неассоциативной бинарной операцией методом производящих функций.
Ранее для числа расстановки скобок в неассоциативном произведении была получена формула
(10)
Введем для последовательности производящую функцию: .
Заменим коэффициенты их выражениями из рекуррентного соотношения (10). Так как это соотношение имеет место, начиная с , то первый член отделим от суммы:
.
Последовательность представляет собой свертку последовательности с собой. В силу свойства 5) имеем
. (12)
Таким образом, можно найти как решение квадратного уравнения (12):
(13)
Перед корнем выбран знак минус, так как . Чтобы найти , надо разложить в ряд по степеням правую часть уравнения (13). Для этого используем формулу бинома Ньютона (8) при и :
,
где
.
Умножим числитель и знаменатель последней дроби на произведение последовательных четных чисел от 2 до : .
Тогда
.
Из формулы (13) получим
.
Таким образом, число расстановок скобок в неассоциативном произведении равно
.
16. Теоретико-множественное определение графа. Геометрическая интерпретация и
реализация графов. Степени вершин. Теорема о сумме степеней вершин графа.
Графом называется пара , где . Элементы из называются вершинами графа, а элементы из – его ребрами. Если – множество упорядоченных пар, то граф называется ориентированным (орграфом) (рис. 1, а), в противном случае – неориентированным (рис. 1, б). Элементы множества , то есть пары вершин, для неориентированного графа, называются ребрами, а для ориентированного – дугами. В случае когда в орграфе необходимо пренебречь направленностью дуг, то неориентированный граф, соответствующий , обозначается как и называется неориентированным дупликатом (или неориентированным двойником).
В ряде случаев естественно рассматривать смешанные графы (рис. 1, в), имеющие как ориентированные, так и неориентированные ребра.
Граф, не имеющий ребер ( ), называется пустым или нуль-графом. Все вершины пустого графа изолированные. Граф, в котором каждая пара вершин соединена ребром, называется полным. Полный -вершинный неориентированный граф обозначается ; для каждой его вершины имеем . Для полного графа , число ребер равно .
Граф с кратными ребрами называют мультиграфом. Если в мультиграфе имеются петли, то он называется псевдографом. Граф без петель и кратных ребер называется простым графом. Граф с вершинами и ребрами называется -графом.
Часто описание орграфа состоит в задании множества вершин и соответствия , которое показывает как между собой связаны вершины , т. е. вершины и являются конечными вершинами дуг, у которых начальной вершиной является x1
Поскольку представляет собой множество таких вершин , для которых в графе существует дуга , то через естественно обозначить множество вершин , для которых в графе существует дуга . Отношение принято называть обратным соответствием.
Очевидно, что для неориентированного графа .
Когда отображение действует на множество вершин , то под понимают объединение .
Отображение записывается как .
Геометрическая интерпретация и реализация графов
При наглядном представлении графа вершины изображаются точками, ребра – линиями, соединяющими точки, а дуги – направленными линиями. В результате таких действий получим некоторый рисунок, который и называется геометрической интерпретацией графа.
Теорема1. Каждый конечный граф можно реализовать в трехмерном евклидовом пространстве.
Степени вершины
Если в графе пара вершин такова, что , то вершины называются смежными; в этой ситуации каждая из них называется инцидентной ребру , а ребро называется инцидентным каждой из вершин . Если вершина и ребро инцидентны, то пишут .
Количество ребер, инцидентных данной вершине , называется ее степенью или локальной степенью графа в вершинеиобозначают через . Для неориентированного графа . Вершина с нулевой степенью называется изолированной. Вершина, степень которой равна единице, называется висячей.
Если ребро (дуга) инцидентно только одной вершине, то его называют петлей. Ребра называют кратными, если они инцидентны одним и тем же вершинам.
Исторически первой теоремой теории графов является утверждение, принадлежащее Эйлеру и связывающее количество ребер, вершин и их степеней.
Теорема 2. Сумма степеней вершин -графа равна удвоенному числу его ребер:
.
Следствие. В любом графе число вершин нечетной степени четно.
Для орграфов вместо степени вершины вводят понятие полустепеней: полустепень исхода – это число дуг, выходящих из вершины ; полустепень захода – это число дуг, входящих в вершину . Очевидно, что
.
17. Матрицы смежности и инциденций. Подграфы. Изоморфизм графов. Инварианты.
Матрицей смежности -графа называется квадратная матрица размера , которая определяется следующим образом:
Для графа, изображенного на рис. 2, матрица смежности имеет вид:
Рис. 2
Матрица смежности полностью определяет структуру графа. Например,
, ,
Для неориентированного графа без кратных ребер и петель матрица смежности симметрична и имеет нули по главной диагонали. Для такого графа
,
Возведем матрицу смежности в квадрат. Элемент матрицы определяется по формуле
.
Слагаемое в этом уравнении равно 1 тогда и только тогда, когда оба числа равны 1, в противном случае оно равно 0. Поскольку из равенства следует существование пути длины 2 из вершины в вершину , проходящего через вершину , то равно числу путей длины 2, идущих из в .
Аналогично если является элементом матрицы , то равно числу путей длины , идущих от к .
Матрицей инциденций -графа называется прямоугольная матрица размерности , определяемая следующим образом:
Для графа, приведенного на рис. 2, матрица инциденций имеет вид:
Если в матрице инциденций нет нулевых элементов, то имеем полный орграф, который называется турниром.
Подграфы
Пусть , – два графа, для которых , ; тогда говорят, что является подграфом графа . В свою очередь, граф по отношению к своему подграфу является надграфом. Если и , то такой подграф называется остовным. Любой остовный подграф графа может быть получен путем удаления подмножества ребер надграфа.
Подграфы другого типа получаются, если выбрать подмножество вершин надграфа и присоединить к ним все ребра, концы которых принадлежат . Это вершинно-порожденные подграфы. Любой вершинно-порожденный подграф графа можно получить путем удаления подмножества вершин и всех инцидентных им ребер надграфа.
Наконец, реберно-порожденным будем называть подграф , полученный на основе произвольно выбранного подмножества ребер надграфа, причем множество вершин подграфа составляют концы только этих ребер. Любой реберно-порожденный подграф можно сформировать, если в надграфе сперва удалить подмножество ребер , а затем в получившемся остовном подграфе удалить все изолированные вершины.
Изоморфизм графов
Пусть имеются изображения графов одного порядка с одинаковым числом ребер. Требуется установить, разные это графы или один, только по разному изображенный. Для решения этой задачи используется понятие изоморфизма.
Изоморфизмом называют взаимно однозначное соответствие между множествами вершин двух графов и , сохраняющее отношение смежности, а сами графы называются изоморфными. Автоморфизмом называется изоморфное отображение графа на себя. Для установления изоморфности достаточно составить списки вершин всех графов, указав для каждой из них все ее соседние вершины. В данном случае все эквивалентные вершины пронумерованы одинаково, что упрощает решение задачи.
Инвариантом называют некоторую числовую характеристику графа , которая принимает одно и то же значение для любого графа, изоморфного . Только при совпадении значений инвариантов переходят к перебору допустимых вариантов нумерации вершин. Тривиальными инвариантами графа являются и . К числу инвариантов относится и степенная последовательность графа, т. к. при изоморфизме степень вершины не изменяется.
Тогда изоморфизм можно представить как перемещение узлов и растяжение нитей.
Оценку сверху для числа попарно неизоморфных графов дает следующая теорема.
Теорема 2. .
18. Маршруты, цепи и циклы. Связность графа и компоненты связности
Ориентированным маршрутом (или путем) орграфа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. На рис. 1 последовательности дуг
, (1)
, (2)
(3)
являются путями.
°
Рис. 1.
Ориентированной цепью (или орцепью) называется путь, в котором каждая дуга используется не больше одного раза. Так, например, пути (2) и (3) являются орцепями, а путь (1) не является таким, поскольку дуга в нем используется дважды.
Простой называется орцепь, в которой каждая вершина используется не более одного раза. Например, орцепь (3) является простой, а орцепь (2) – нет.
Маршрут есть неориентированный двойник пути, т. е. последовательность ребер , в которой каждое ребро , за исключением первого и последнего, связано концевыми вершинами с ребрами и . Черта над символом дуги означает, что ее рассматривают как ребро.
Аналогично тому, как мы определили орцепи и простые цепи, можно определить цепи и простые цепи.
Путь или маршрут можно изображать также последовательностью вершин. Например, путь (1) можно записать в виде: .
Путь называется замкнутым, если в нем начальная вершина дуги совпадает с конечной вершиной дуги . Замкнутые орцепи (цепи) называются орциклами (циклами). Орциклы называют также контурами. Замкнутые простые орцепи (цепи) называются простыми орциклами (циклами). Замкнутый маршрут является неориентированным двойником замкнутого пути.
Связность графа и компоненты связности
Говорят, что вершина в орграфе достижима из вершины , если существует путь . Если при этом достижима из , то об этих вершинах говорят, что они взаимно достижимы.
Орграф называют сильно связным или сильным, если любые две вершины в нем взаимно достижимы. Пример сильного орграфа приведен на рис. 2 а. Поскольку в графе имеется орцикл , включающий все вершины, то любые две из них взаимно достижимы.
° ° °
° ° ° ° ° °
° ° ° ° ° °
а б в
Рис. 2.
Орграф называется односторонне связным или односторонним, если в любой паре его вершин хотя бы одна достижима из другой
Орграф называется слабо связным или слабым, если в нем любые две вершины соединены полупутем. Полупуть, в отличие от пути, может иметь противоположно направленные дуги. Пример слабого орграфа приведен на рис. 2 в
Если для некоторой пары вершин не существует маршрута, соединяющего их, то такой орграф называется несвязным.
Для орграфа определены три типа компонент связности: сильная компонента – максимально сильный подграф, односторонняя компонента – максимальный односторонний подграф и слабая компонента – максимально слабый подграф
Понятие сильной компоненты иллюстрирует рис. 3.
° ° ° ° ° °
° ° ° °
° ° ° ° ° °
° ° ° ° ° °
° ° °
° ° ° ° °
Рис. 3
Граф , который является односторонне связным, содержит шесть сильных подграфов , из которых только и являются сильными компонентами. Аналогично иллюстрируется понятие односторонней компоненты. В данном примере односторонняя компонента совпадает с самим графом.
Для неориентированного графа определим на множестве его вершин бинарное отношение, полагая
, если имеется цепь, связывающая с . Это отношение обладает свойствами рефлексивности, симметричности и транзитивности, то есть является отношением эквивалентности. Оно разбивает множество вершин на непересекающиеся классы: . Две вершины из одного класса эквивалентны, то есть в графе имеется цепь, соединяющая их, для вершин из разных классов такой цепи нет. Так как концы любого ребра находятся в отношении , то множество ребер графа также разобьется на непересекающиеся классы: , где через обозначено множество всех ребер, концы которых принадлежат , .
Графы являются связными и в сумме дают граф . Эти графы называются компонентами связности графа . Число – еще одна числовая характеристика графа. Для связного графа , если граф несвязный, то .
|
Скачать 4.95 Mb.