Частичные графы и подграфы

Локальные степени графов

Пусть G(x) неориентированный граф, локальной степенью графа G(x) в вершине называется число ребер инцидентность этой вершины, у которой p(x) – локальная степень.

петля

Примечание: петли в локальных степенях увеличиваются 1 или 2 раза (что нужно отмечать при условии решения).

Пусть граф G(x) имеет m ребер. Сумма локальных степеней равна 2m

= 2m - 1 формула

P = 2

P(x) = 2

Преобразуем

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

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

Если локальные степени графа во всех вершинах одинаковы и равны и то такой граф называют однородным графом степени N.

Обозначим число вершин графа |x|. Если граф однородный и степень n, то число локальных степеней равно

= |x|n – формула 2

Из формул 1 и 2 следует что в однородном графе степени m число ребер равно

– формула 3

Пусть G(x) ориентированный граф. Число дуг графа из называют полустепенью исхода графа

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

Полустепенью захода и исхода дуги учитываем один раз=> число ребер равно не – формула 4.

Чтобы формула была справедлива для графа с петлями необходимо, чтобы число дуг графа было равно степени захода и исхода.

Ориентированный граф называется однородным степени n, если полустепень захода и исхода в любой его вершине равно m = |x|n

Граф H = (x, ) называется частичным для G = (X, Г), если для всех x ()(), гдеотображение вершины в множестве, а Гx – множество вершин входящих в отображение вершин графа G(x)

Гx G

Если H – частичный граф, граф G , то и все его ребра являются ребрами графа G.

Обратное утверждение не верно, то есть в G могут быть ребра не принадлежащие H.

G:\Новая папка: 25. Рекуррентные соотношения.

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

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

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

Рекурсивные соотношения (РС) определяют последовательность только в том случае, если заданы k-первых членов этой последовательности.

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

Пример:

Решением этого соотношения будет

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

Общего правила для решения рекуррентных соотношений не имеется.

Рассмотрим рекуррентное соотношение k-го порядка вида:

(1) , где некоторые числа.

Рекуррентное соотношение вида (1) называется линейным рекуррентным соотношением с постоянными коэффициентами.

(2) – второй порядок

Пусть известны и (2), отсюда вытекает следующее утверждение:

Для

Таким образом получили второе тождество; следовательно обращает выражение (2) в тождество и является решение рекуррентного соотношения.

Запишем следующее квадратное уравнение соответственно по отношению ко (2)

(3)

Это уравнение назовем характеристическим уравнением для (2)

Пусть корень, тогда запишем утверждение (2):

Утверждение (2): Последовательность , где n = 1,2,3… также является решением соотношения (2), таким образом:

, , , тогда подставив эти значения в уравнение (3) получим . Разделим это выражение на и получим: , это тождество очевидно, итак