Иерархия.Асимптотическая аппроксимация.

28.Формула суммирования Эйлера-Маклорена.

формула суммирования, связывающая частные суммы ряда с интегралом и производными его общего члена:

где - Бернулли числа, R_n - остаточный член. С помощью Бернулли многочленов B_n(t), В _n(0)=В _п остаточный член записывается в виде:

Для n=2sостаточный член R_2s может быть представлен с использованием чисел Бернулли:

Если производные и имеют одинаковые знаки и не меняют знака на [ р, т], то Э.-М. ф. играет важную роль при изучении асимптотич. разложений, в теоретико-числовых оценках, в конечных разностей исчислении. Э.-М. ф. была впервые приведена Л. Эйлером [1] в виде: где S - сумма первых членов ряда с общим членом t(п), S=t=0 при n=0, а коэффициенты определяются рекуррентными соотношениями:

Независимо формула была открыта позднее К. Маклореном.

 

Графы, ориентированные графы, псевдографы, мультиграфы.

Графом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е двухэлементных подмножеств множества V (Е — множество рёбер). G(V, E) = (V; E), V^0, Е С 2V кVe G E |e| = 2. Если элементами множества Е являются упорядоченные пары (то есть Е с V х V), то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

30. Изоморфизм и гомеоморфизм графов, двудольные графы. Говорят, что два графа G\1V1, Ei) и G2(V2, E2) изоморфны (обозначается G1 ~ G2), если существует биекция h: V1—► V2, сохраняющая смежность ei = (u, v) е Ех < => е2 = (h(u), h(v)) e E2. Пусть А = (-А, fi, П) и В = (В, П, П) — две однотипные алгебраические системы. Отображение h: А-± В называют гомоморфизмом алгебраической системы А в алгебраическую систему В, если выполняются следующие условия: 1) для любой п-арной операции ш ( ) и любых элементов 2) для любого п-арного отношения тг (n ^ 1) и любых элеэлементов следует Двудольный граф (или биграф, или чётный граф) — это граф G(V, E)y такой что множество V разбито на два непересекающихся множества V1 и V2 (Vi U V2 = V2 & V1 П V2 = 0), причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из Vi с вершиной из V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит

все рёбра, соединяющие множества V\ и V2l то он называется полным двудольным графом..

Маршруты, пути.

Маршрутом в графе называется чередующаяся последовательность вершин и рёбер vo, e1, v1, e2, v2,..., efc, Vfc, в которой любые два соседних элемента инцидентны. Если vo = Vk, то маршрут замкнут, иначе открыт. Если все рёбра различны, то маршрут называется цепью. Если все вершины

(а значит, и рёбра) различны, то маршрут называется простой цепью. В цепи vo, ei,..., еk-1, Vk вершины vq и Vk называются концами цепи. Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается (u, v). Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

32.Матричное задание графов.

Предположим, что все вершины и все ребра неориентиронеориентированного графа или все вершины и все дуги (включая петли) ориентированного графа пронумерованы начиная с единицы.

Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа nхm, где n — число вершин, a m — число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом: .

 

 

 

 

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

для неориентированного графа Заметим, что в k-й строке матрицы ориентированного граграфа количество единиц равно полустепени исхода dg+ v_k вершины v_k, а количество единиц в k-м столбце dg- v_k — полустепени захода Для неориентированного графа матрица смежности вершин симметрическая.

1234	Поделиться: