Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

в) Найдем композицию функций f из примера а) и g^-1 из примера б). Имеем g^-1f = {<a, 2>, <b, 3>, <c, 4>, <d, 2>}.

fg^-1 = .

Заметим, что (g^-1f)(a) = f(g^-1(a)) = f(1) = 2; (g^-1f)(c) = f(g^-1(c)) = f(3) = 4.

Элементарной функцией в математическом анализе называется всякая функция f, являющаяся композицией конечного числа арифметических функций, а также следующих функций:

1) Дробно-рациональные функции, т.е. функции вида

a₀ + a₁x + ... + a_nxⁿ

b₀ + b₁x + ... + b_mx^m.

2) Степенная функция f(x) = x^m, где m – любое постоянное действительное число.

3) Показательная функция f(x) = e^x.

4) логарифмическая функция f(x) = log_ax, a >0, a 1.

5) Тригонометрические функции sin, cos, tg, ctg, sec, csc.

6) Гиперболические функции sh, ch, th, cth.

7) Обратные тригонометрические функции arcsin, arccos и т.д.

Например, функция log²(x³ +sincos3x) является элементарной, т.к. она есть композиция функций cosx, sinx, x³, x₁ + x₂, logx, x².

Выражение, описывающее композицию функций, называется формулой.

Для многоместной функции справедлив следующий важный результат, полученный А. Н. Колмогоровым и В. И. Арнольдом в 1957 г. и являющийся решением 13-ой проблемы Гильберта:

Теорема. Всякая непрерывная функция n переменных представима в виде композиции непрерывных функций двух переменных.

Способы задания функций

1. Наиболее простой способ задания функций – это таблицы (табл. 2.2):

Таблица 2.2

Пример 2.27.

Бросается игральная кость. Пусть k – число выпавших очков, а p(k) – вероятность того, что при случайном бросании кости выпадет k очков, k = 1, 2, ..., 6.

В этом случае функция p(k) может быть задана следующей таблицей (табл. 2.3):

Таблица 2.3

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

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

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

Пример 2.28.

f(x) = sin(x + x) является композицией следующих функций:

g(y) = y; h(u, v) = u + v; w(z) = sinz.

3. Функция может быть задана в виде рекурсивной процедуры. Рекурсивная процедура задает функцию, определенную на множестве натуральных чисел, т. е. f(n), n = 1, 2,... следующим образом: а) задается значение f(1) (или f(0)); б) значение f(n + 1) определяется через композицию f(n) и других известных функций. Простейшим примером рекурсивной процедуры является вычисление n!: а) 0! = 1; б) (n + 1)! = n!(n + 1). Многие процедуры численных методов являются рекурсивными процедурами.

4. Возможны способы задания функции, не содержащие способа вычисления функции, а только описывающие ее. Например:

f_M(x) =

Функция f_M(x) – характеристическая функция множества M.

Итак, по смыслу нашего определения, задать функцию f – значит задать отображение X  Y, т.е. определить множество XY, поэтому вопрос сводится к заданию некоторого множества. Однако можно определить понятие функции, не используя языка теории множеств, а именно: функция считается заданной, если задана вычислительная процедура, которая по заданному значению аргумента находит соответствующее значение функции. Функция, определенная таким образом, называется вычислимой.

Пример 2.29.

Процедура определения чисел Фибоначчи, задается соотношением

F_n = F_n-1 + F_n-2 (n ³ 2) (2.1)

с начальными значениями F₀ = 1, F₁ = 1.

Формула (2.1) вместе с начальными значениями определяет следующий ряд чисел Фибоначчи:

n	0 1 2 3 4 5 6 7 8 9 10 11 …
Fn	1 1 2 3 5 8 13 21 34 55 89 144 …

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

Контрольные вопросы к теме 2

1. Укажите способы задания бинарного отношения.

2. Главная диагональ матрицы какого отношения содержит только единицы?

3. Для какого отношения  всегда выполняется условие  = ^–1?

4. Для какого отношения  всегда выполняется условие    .

5. Ввести отношения эквивалентности и частичного порядка на множестве всех прямых на плоскости.

6. Укажите способы задания функций.

7. Какое из следующих утверждений справедливо?

а) Всякое бинарное отношение есть функция.

б) Всякая функция есть бинарное отношение.

Тема 3. ГРАФЫ

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

3.1. Основные характеристики графов

Граф G - это математический объект, состоящий из множества вершин X = {x₁, x₂,..., x_n} и множества ребер A = {a₁, a₂,..., a_n}. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A).

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

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентиро­ванного графа называются дугами. Соответствующие вершины ориентиро­ванного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).

Пример 3.1.

На рис. 3.1 изображен неориентированный граф G =( X, A).

X = {x₁, x₂, x₃, x₄},

A = {a₁= (x₁, x₂), a₂=(x₂, x₃), a₃=(x₁, x₃), a₄= (x₃, x₄)}.

Рис. 3.1.

Пример 3.2.

На рис. 3.2. изображен ориентированный граф G = (X, A).

X = {x₁, x₂, x₃, x₄},

A = {a₁ = (x₁ , x₂ ), a₂ = (x₁ , x₃ ), a₃ = (x₃ , x₄ ), a₄ = (x₃ , x₂ )}.

Рис. 3.2.

Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.

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

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

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

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым.

Пример 3.3.

На рис. 3.3. изображен ориентированный граф G = (X, A).

X = {x₁ , x₂ , x₃ , x₄ },

A = .

Риc. 3.3.

Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины x и y инцидентны ребру a, если эти вершины соединены a.

Две вершины называются смежными, если они инцидентны одному и то­му же ребру. Два ребра называются смежными, если они имеют общую вер­шину.

Степенью вершины графа называется число ребер, инцидентных этой вершине. Вершина, имеющая степень 0, называется изолированной, а сте­пень 1 – висячей.

Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G(х), то есть G(х) = { y: ( x y ) G}. Множество G(x) называют образом вершины x. Соответс­твенно G^-1(у) – множество вершин, из которых исходят дуги, ведущие в вершину у, G^-1(y) = {x: ( x , y ) G}. Множество G^-1(у) называют прообразом вершины y.

Пример 3.4.

В графе, изображенном на рис. 3.1, концами ребра a₁ являются вер­шины x₁, x₂; вершина x₂ инцидентна ребрам a₁, a₂; степень вершины x₃ равна 3; вершины x₁ и x₃ смежные; ребра a₁ и a₂ смежные; вершина x₄ висячая. В ориентированном графе, изображен­ном на рис. 3.2, началом дуги a₁ является вершина x₁, а ее концом - вершина x₂; вершина x₁ инцидентна дугам a₁ и a₂; G(x₁) = {x₂, x₃}, G(x₂) =Æ, G^-1(x₃) = {x₁}, G^-1(x₁) = Æ.

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

Граф G = (X, A) - полный, если для любой пары вершин x_i и x_j су­ществует ребро (x_i, x_j).

Граф G = (X, A) - симметрический, если для любой дуги (x_i, x_j) существует противоположно ориентированная дуга (x_j, x_i).

Характеристики

Список файлов книги