А Ì В

 

Определение. Если А Í В, то множество А называется подмножествоммножества В, а если при этом А ¹ В, то множество А называется собственным подмножеством множества В и обозначается А Ì В.

 

Для трех множеств А, В, С справедливы следующие соотношения.

 

Связь между включением и равенством множеств устанавливается следующим соотношением:

Здесь знак Ù обозначает конъюнкцию(логическое “и”).

 

 

Операции над множествами.

 

Определение. Объединениеммножеств А и В называется множество С, элементы которого принадлежат хотя бы одномк из множеств А и В.

Обозначается С = А È В.

 

А

В

 

 

Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера – Венна.

 

Определение. Пересечениеммножеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В.

Обозначение С = А Ç В.

 

 

А С В

 

 

Для множеств А, В и С справедливы следующие свойства:

 

А Ç А = А È А = А; A È B = B È A; A Ç B = B Ç A;

 

(A Ç B) Ç C = A Ç (B Ç C); (A È B) È C = A È (B È C);

 

A È (B Ç C) = (A È B) Ç (A È C); A Ç (B È C) = (A Ç B) È (A Ç C);

 

A È (A Ç B) = A; A Ç (A È B) = A;

 

Æ = А; A Ç Æ = Æ;

 

 

Определение. Разностьюмножеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В.

Обозначается С = А В.

 

 

 

А В

 

 

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

Обозначается А D В.

 

 

А D В = (A B) È (B A)

 

A B

 

Определение. С_Е называется дополнениеммножества А относительно множества Е, если А Í Е и C_Е = Е A.

 

 

 

A E

 

 

Для множеств А, В и С справедливы следующие соотношения:

 

A B Í A; A A = Æ; A (A B) = A Ç B;

 

A D B = B D A; A D B = (A È B) (A Ç B);

 

A (B È C) = (A B) Ç (A C); A (B Ç C) = (A B) È (A C);

 

(A È B) C = (A C) È (B C); (A Ç B) C = (A C) Ç (B C);

 

A (B C) = (A B) È (A Ç C); (A B) C = A (B È C);

 

(A D B) D C = A D (B D C); A Ç (B D C) = (A Ç B) D (A Ç C);

 

A È C_EA = E; A Ç C_EA = Æ; C_EE = Æ; C_EÆ = E; C_EC_EA = A;

 

C_E(A È B) = C_EA Ç C_EB; C_E(A Ç B) = C_EA È C_EB;

 

 

Пример. Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграммы Эйлера - Вейна.

 

Из записанных выше соотношений видно, что

 

Æ= A В

 

Что и требовалось доказать.

Для иллюстрации полученного результата построим диаграммы Эйлера – Вейна

 

 

А В А В

 

AÇB

 

Пример. Исходя из определения равенства множеств и операций над множествами, доказать тождество.

A (B È C) = (A B) Ç (A C)

 

Если некоторый элемент х Î А (В È С), то это означает, что этот элемент принадлежит множеству А, но не принадлежит множествам В и С.

Множество А В представляет собой множество элементов множества А, не принадлежащих множеству В.

Множество А С предсталяет собой множество элементов множества А, не принадлежащих множеству С.

Множество (A B) Ç (A C) представляет собой множество элементов, которые принадлежат множеству А, но не принадлежат ни множеству В, ни множеству С.

Таким образом, тождество можно считать доказанным.

 

 

Отношения и функции.

 

 

Определение. Упорядоченной парой (a, b) двух элементов a и b называется множество {{a},{a, b}}.

Для любых элементов a, b, c, d справедливо соотношение:

 

Определение. Декартовым произведениеммножеств А и В называется множество всех упорядоченных пар (a, b), где аÎА, bÎB.

 

 

Декартово произведение п равных множеств А будет называться п – й декартовой степенью множества А и обозначаться Аⁿ.

 

Определение. n – мерным отношениемR на непустом множестве А называется подмножество Аⁿ. Если R – n – мерное отношение на множестве А и (а₁,а₂,…а_n)ÎR, то говорят, что отношение R выполняется для элементов а₁,а₂,…а_n и записывают R а₁а₂…а_n. Если n = 2, то такое отношение называется бинарным.

Для бинарного отношения вместо общей записи Ra₁a₂ применяют запись а₁Ra₂.

 

Свойства бинарных отношений.

 

Определение. Произведением двух бинарных отношений R и S, заданных на множестве А, называется множество

Знак | называется штрих Шеффера и обозначает антиконъюнкцию.

 

 

Определение. Обратным (инверсным) отношением к отношению R, заданному на множестве А, называется отношение R^-1, определяемое равенством:

 

Если R, S и T – бинарные отношения на множестве А, то выполняются следующие равентсва:

 

 

 

 

Алгебраические структуры.

 

Определение. На множестве А определена алгебраическая операция,если каждым двум элементам этого множества, взятым в определенном порядке, однозначным образом поставлен в соответствие некоторый третий элемент из этого же множества.

 

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

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

 

Определение. Множество А с определенной на нем алгебраической операцией (например, умножением) называется группой, если выполнены следующие условия:

1) для любых трех элементов a, b, c Î A выполняется свойство ассоциативности:

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

3) для любого элемента а множества существует элемент а’ из этого же множества такой, что

Различные множества могут являться группой относительно какой- либо операции и не являться группой относительно другой операции.

Число элементов называется порядком группы.

 

Определение. Между элементами множеств M и N установлено взаимно однозначное соответствие, если каждому элементу множества М поставлен в соответствие определенный элемент множества N, причем различным элементам одного множества соответсвуют различные элементы другого множества.

 

Определение. Две группы M и N называются изоморфными, если между их элементами можно установить взаимно однозначное соответсвие, при котором для любых двух элементов a, bÎ M и соответствующим им элементам a’, b’Î N элементу

с = ab будет соответствует элемент c’ = a’b’.

 

При этом отображение группы М на группу N называется гомоморфизмом.

 

Определение. Если операция, определенная в группе коммутативна, (т.е. для любых элементов a и b группы верно соотношение ab=ba), то такая группа называется коммутативнойили абелевой группой.

 

Определение. Множество R с двумя определенными в нем алгебраическими операциями, сложением и умножением, называется кольцом, если относительно операции сложения оно является абелевой группой, а операция умножения дистрибутивна, т.е. для любых элементов a, b и с Î R справедливы равенства:

 

Если операция умножения, определенная в кольце коммутативна, то такое кольцо называется коммутативнымкольцом.

 

Определение. Полем называется коммутативное кольцо, в котором для любого ненулевого элемента a¹ 0 и любого элемента b существует единственный элемент х такой, что ax = b.

 

 

Дискретная математика.

 

Элементы комбинаторики.

 

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

Рассмотрим подробнее эти три типа соединений:

 

1) Перестановки.

 

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

 

Общее число перестановок из m элементов обозначается P_m и вычисляется по формуле:

2) Размещения.

 

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

 

Общее число таких размещений расчитывается по формуле:

 

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

 

 

3) Сочетания.

 

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

 

Общее число сочетаний находится по формуле:

 

Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами.

Если среди т элементов имеется т₁ одинаковых элементов одного типа, т₂ одинаковых элементов другого типа и т.д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:

 

 

Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

 

Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.

Число всех возможных комбинаций из 30 букв по две равно .

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

Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.

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

 

 

Бином Ньютона. (полиномиальная формула)

 

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

Бином Ньютона – это формула, выражающая выражение (a + b)ⁿ в виде многочлена. Эта формула имеет вид:

 

- число сочетаний из п элементов по k.

 

Широко известные формулы сокращенного умножения квадрата суммы и разности, куба суммы и разности, являются частными случаями бинома Ньютона.

Когда степень бинома невысока, коэффициенты многочлена могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).

Этот треугольник имеет вид:

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

…………………

 

 

Формула бинома Ньютона может быть обобщена для произвольного числа слагаемых.

 

Напомним, что при вычислениях 0! принимается равным 1.

 

 

Пример. В разложении найти члены, содержащие х^a, если k=3, p=2, n=8, a=9.

 

По фомуле бинома Ньютона имеем:

C учетом числовых значений:

 

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

Найдем число i, соответствующее этому члену:

 

Находим:

 

 

Пример. В разложении найти члены, содержащие x^g. т=9, g=6.

 

По обобщенной формуле бинома Ньютона получаем:

 

Для нахождения полного разложения необходимо определить все возможные значения n_i, однако, это связано с громадными вычислениями. Однако, т.к. надо найти только члены, содержащие х⁶, то n₁ = 6, а сумма всех четырех значений п равна 9. Значит, сумма п₂ + п₃ + п₄ = 3.

 

Рассмотрим возможные значения этих величин:

 

n2
n3
n4

 

Искомые члены разложения:

 

 

 

 

Элементы математической логики.

 

Математическая логика – разновидность формаьной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения.

 

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

 

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

Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.

Таким образом, операции с высказываниями можно описывать с помощью некоторого математического аппарата.

 

Вводятся следующие логические операции (связки) над высказываниями

 

1) Отрицание. Отрицанием высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.

Обозначается Р или .

 

Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:

 

P	Р
И	Л
Л	И

 

2) Конъюнкция. Конъюнкцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Обозначается P&Q или РÙQ.

 

P	Q	P&Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

 

3) Дизъюнкция. Дизъюнкцией двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

Обозначается PÚQ.

 

P	Q	PÚQ
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

 

4) Импликация. Импликацией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.

Обозначается PÉQ (или РÞQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.

 

P	Q	PÞQ
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

 

5) Эквиваленция. Эквиваленцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.

Обозначается Р~Q или РÛQ.

 

P	Q	P~Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

 

С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.

 

 

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

Составим таблицы истинности для каждой формулы:

 

p	r		(pÙr)
И	И	Л	И	И
И	Л	Л	Л	И
Л	И	И	Л	Л
Л	Л	И	Л	Л

 

p	r
И	И	Л	Л	Л	И
И	Л	Л	И	И	И
Л	И	И	Л	И	И
Л	Л	И	И	И	И

 

Данные формулы не являются эквивалентными.

 

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

 

 

Составим таблицы истинности для заданных формул.

 

 

p	q	r	pÛq	(pÛq)Úr
И	И	И	И	И
И	И	Л	И	И
И	Л	И	Л	И
И	Л	Л	Л	Л
Л	И	И	Л	И
Л	И	Л	Л	Л
Л	Л	И	И	И
Л	Л	Л	И	И

 

 

p	q	r	pÞq	qÞp	(pÞq)Ú(qÞp)	(pÞq)Ú(qÞp)Úr
И	И	И	И	И	И	И
И	И	Л	И	И	И	И
И	Л	И	Л	И	И	И
И	Л	Л	Л	И	И	И
Л	И	И	И	Л	И	И
Л	И	Л	И	Л	И	И
Л	Л	И	И	И	И	И
Л	Л	Л	И	И	И	И

 

Из составленных таблиц видно, что данные формулы не равносильны.

 

 

Основные равносильности.

 

Для любых формул А, В и С справедливы следующие равносильности:

 

A & B º B & A; A & A º A; A & (B & C) º (A & B) & C;

 

A Ú B º B Ú A; A Ú A º A; A Ú (B Ú C) º (A Ú B) Ú C;

 

A Ú (B & C) º (A Ú B) & (A Ú C); A & (B Ú C) º (A & B) Ú (A & C);

 

A & (A Ú B) º A; A Ú (A & B) º A; ØØA º A; Ø(A & B) º ØA Ú ØB;

 

A º (A & B) Ú (A & ØB); A º (A Ú B) & (A Ú ØB);

 

Булевы функции.

 

Определение. Булевой функциейf(X₁, X₂, …, X_n) называется называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

 

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

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

 

X1	X2	ØX1	X1&X2	X1ÚX2	X1ÞX2	X1ÛX2

 

Исчисление предикатов.

 

Определение. ПредикатомP(x₁, x₂, …, x_n) называется функция, переменные которой принимают значения из некоторого множества М, а сама функция принимает два значения: И (истина) и Л (ложь), т.е.

 

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

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

 

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

Кванторы бывают двух видов:

 

1) Квантор общности. Обозначается ("х)Р(х). Квантором общности называется высказывание истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное – в противном случае.

 

2) Квантор существования. Обозначается ($х)Р(х). Квантором существования называется высказывание, истинное, когда существует элемент из множества М, для которого Р(х) истинно, и ложное в противном случае.

 

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

 

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

 

1) Перенос квантора через отрицание.

 

Ø("x)A(x) º ($x)ØA(x); Ø($x)A(x) º ("x)ØA(x);

 

2) Вынесение квантора за скобки.

 

($х)(А(х) & B) º ($x)A(x) & B; ("x)(A(x) & B) º ("x)A(x) & B;

 

($х)(А(х) Ú B) º ($x)A(x) Ú B; ("x)(A(x) Ú B) º ("x)A(x) Ú B;

 

3) Перестановка одноименных кванторов.

 

("y)("x)A(x,y) º ("x)("y)A(x,y); ($y)($x)A(x,y) º ($x)($y)A(x,y);

 

4) Переименование связанных переменных. Если заменить связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А.

 

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

 

Какими бы ни были формулы А и В для них справедливы следующие аксиомы:

 

1) A Þ (B Þ A);

 

2) (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));

 

3) (ØB Þ ØA) Þ ((ØB Þ A) Þ B);

 

4) ("x_i)A(x_i) Þ A(x_j), где формула А(х_i) не содержит переменной x_i.

 

5) A(x_i) Þ ($x_j)A(x_j), где формула А(х_i) не содержит переменной x_i.

 

 

Конечные графы и сети.

Основные определения.

 

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

При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

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

(v, w) в Х называется кратностьюребра (v, w).

Множество V и набор Х определяют граф с кратными ребрами – псевдограф.

G = (V, X)

 

Псевдограф без петель называется мультиграфом.

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

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

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

 

 

Определение. Если х = {v, w} – ребро графа, то вершины v, w называются концами ребра х.

Если х = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.

 

Определение. Вершины v, w графа G = (V, X) называются смежными, если {v,w}ÎX. Два ребра называются смежными, если они имеют общюю вершину.

 

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

 

Определение.Графы G₁(V₁, X₁) и G₂(V₂, X₂) называются изоморфмными, если существует взаимно однозначное отображение j: V₁ ® V₂, сохраняющее смежность.

 

Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v₁x₁v₂x₂v₃…x_kv_k+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиноймаршрута (пути).

 

Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

 

Определение. Замкнутый маршрут (путь) называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

 

 

Матрицы графов.

 

Пусть D = (V, X) – орграф, где V = {v₁, …, v_n}, X = {x₁, … , x_m}.

 

Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [a_ij] порядка п, у которой

 

Определение. Если вершина v является крнцом ребра х, то говорят, что v и х –инциндентны.

 

Определение. Матрицей инциндентности оргафа D называется матрица размерности п´т B(D) = [b_ij], у которой

 

 

Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.

 

x₁

v₁ x₄ v₂

 

x₂

x₃

v₃

 

Составим матрицу смежности:

 

	v1	v2	v3
v1
v2
v3

 

Т.е. - матрица смежности.

 

Матрица инциндентности:

	x1	x2	x3	x4
v1	-1
v2		-1		-1
v3			-1

 

Т.е.

 

Если граф имеет кратные дуги (ребра), то в матрице смежности принимается a_ij=k, где k – кратность дуги (ребра).

 

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

 

 

Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф , имеющий матрицу смежности Q, определить его матрицу инциндентности С.

x₄

x₃

 

v₂

x₂ x₅

x₆

x₁ v₁ v₃ x₇ x₈

 

x₁₀

x₁₁ x₉

 

v₄

 

Составим матрицу инциндентности:

 

	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11
v1
v2
v3
v4

 

Итого:

 

Построим теперь ориентированный граф с заданной матрицей смежности.

 

x₄

x₅

v₂

x₂ x₇

х₃ x₆

x₁ v₁ х₈ v₃ x₁₀ x₁₁

х₉

х₁₇ х₁₅ x₁₄

x₁₆ х₁₃ x₁₂

 

v₄

 

Составим матрицу инциндентности для ориетированного графа.

 

Элемент матрицы равен 1, если точка является концом дуги, -1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

 

 

Таким образом, операции с графами можно свести к операциям с их матрицами.

 

 

Достижимость и связность.

 

Определение. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w(маршрут, соединяющий v и w).

 

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

 

Определение. Псевдографом D(V, X), ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X₀) в котором Х₀ получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные пары (v, w).

 

Определение.Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

 

 

Эйлеровы и гамильтоновы графы.

 

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

 

Теорема. Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.

 

Теорема. Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.

 

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

 

Пример.

 

 

- в графе есть и эйлеровый и гамильтонов циклы

 

 

- в графе есть эйлеров цикл, но нет гамильтонова

 

- в графе есть гамильтонов, но нет эйлерова цикла

 

- в графе нет ни эйлерова, ни гамильтонова цикла

 

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

Также необходимым условием существования гамильтонова цикла явояется связность графа.

 

 

Деревья и циклы.

 

Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

 

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

 

 

 

 

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

 

Для графов, которые сами по себе не являются деревьями, вводится понятие остовного дерева.

 

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

 

Пусть G – связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.

Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно m(G) - (n(G) - 1) = m(G) – n(G) + 1 ребер.

Число v(G) = m(G) – n(G) + 1 называется цикломатическим числом связного графа G.

 

Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.

 

1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G₂.

2) Строим граф G₃, добавляя к графу G₂ новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой либо вершине графа G₂, и одновременно инциндентно какой – либо вершине графа G, не содержащейся в графе G₂.

3) Строим графы G₄, G₅, …, G_n, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.

 

Пример. Определить минимальное остовное дерево нагруженного графа.

 

Граф называется нагруженным, если на множестве его дуг задана некоторая функция, которая называется весовой функцией, и определяет длину дуги.

В нашем примере – весовая функция определяет длины дуг числами 1, 2, 3, 4, 5.

v₂ 2 v₃

1 4

1 v₅ 3

5 3

 

v₁ 4 v₄

 

 

2 2

 

1 1 1 1 1 1 1 3

 

 

G₂ G₃ G₄ G₅

 

На четвертом шаге алгоритма получили дерево G₅, которое соединяет все вершины исходного графа. Таким образом, дерево G₅ , будет минимальным остовным деревом графа G.

 

Элементы топологии.

 

Топология изучает понятия непрерывности и близости с абстрактной точки зрения.

 

Определение. Окрестностью точки р называется произвольное множество U, содержащее открытый шар (не включая границу) с центром в точке р.

 

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

Из определения окрестности вытекают следующие очевидные свойства:

1) Точка р принадлежит любой своей окрестности.

2) Если U – окрестность точки р, а V É U, то V – тоже окрестность точки р.

3) Если U и V – окрестности точки р, то их пересечение U Ç V тоже будет окрестностью точки р.

4) Если U – окрестность точки р, то можно найти такую окрестность V точки р, что W = V Ì U является окрестностью является окрестностью каждой из своих точек.

 

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

 

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

 

Определение. Пусть Е – топологическое пространство, а F – его подмножество. Пусть р – точка множества F. Назовем подмножество U множества F окрестностьюточки р в F, если U=FÇV, где V – окрестность точки р в E.

При этом множество F называется подпространствомпространства Е.

 

Метрическое пространство.

 

Определение. Метрикойна множестве Е называется функция f(x, y), определенная на декартовом произведении Е´Е, значениями которой являются неотрицательные действительные числа, удовлетворяющая при любых значениях х, у, z из множества Е следующим условиям:

1) f(x, y) = f(y, x)

2) f(x, y) + f(y, x) ³ f(x, y)

3) f(x, y) = 0 тогда и только тогда, когда х = у.

 

 

Определение. Метрическим пространством называется множество Е с заданной на нем метрикой f.

 

Определение. Число r(x, y), где х ÎЕ и у Î Е – заданные точки, называется расстоянием между этими точками.

 

Определение. Пусть r – положительное число. Множество {y: r(x, y) < r} называется открытым шаром радиуса r с центром в точке х; множество {y: r(x, y) £ r} – замкнутым шаромрадиуса r с центром в точке х.

Например, для трехмерного евклидова пространства R³ метрика определяется как , где х(х₁, х₂, x₃) Î R³ и y(y₁, y₂, y₃) Î R³.

 

 

Открытые и замкнутые множества.

 

Определение. Пусть Е – топологическое пространство, а U – его подмножество. Множество U называется открытым, если оно является окрестностью для любой точки rÎU.

 

Определение. Пусть Е – топологическое пространство, а F – его подмножество. Множество F называется замкнутым, если множество E F – открыто.

 

Отметим следующие свойства:

1) Объединение любой совокупности открытых множеств открыто.

2) Пересечение конечного числа открытых множеств открыто.

3) Пересечение любой совокупности замкнутых множеств замкнуто.

4) Объединение конечного числа замкнутых множеств замкнуто.

 

Определение. Если А – любое множество в топологическом пространстве Е, то объединение всех открытых множеств, содержащихся в А, открыто. Это объединение называется внутренностьюмножества А. Обозначается IntA. Это объединение будет наибольши открытым множеством, содержащимся в А.

 

Определение. Множество называется замыканиеммножества А. Множество FrA = CA называется границеймножества А.

 

 

Непрерывные отображения.

 

Пусть Е и F – топологические пространства, и пусть f – отображение пространства Е в F.

f: E ® F.

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

 

Определение. Отображение f: E ® F называется непрерывным в точке р, если для любой окрестности V точки f(p) в множестве F существует такая окрестность U точки в множестве Е, что f(U) Ì V. Отображение f называется непрерывным, если оно непрерывно в каждой точке пространства Е.

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

 

Определение. Если f – взаимно одноначное отображение пространства Е в F, то существует обратное отображение g пространства F в E. Если и f и g непрерывны, то отбражение f называется гомеоморфизмом, а пространства Е и F – гомеоморфные.

 

Гомеоморфизм между множествами устанавливает взаимно однозначное соответствие между окрестностями, закрытыми и открытыми подмножествами этих множеств.

Топологические произведения.

 

Пусть E и F – топологические пространства. Множество E´F определяется как множество пар (p,q), где pÎE, a qÎF. Оно превращается в топологическое пространство следующим образом: если (p,q) Î E´F, то окрестность точки (p,q) – это любое множество, содержащее множество вида U´V, где U – окрестность точки p в E, a V– окрестность q в F.

 

Определение. Множество E´F, превращенное в топологическое пространство только что описанным способом, называется топологическим произведением пространств E и F.

 

Например, в трехмерном евклидове пространстве тор является топологическим произведением окружности на себя.

 

 

Связность.

Определение. Пространство E называется связным, если его нельзя представить в виде объединения двух непустых непересекающихся множеств, открытых в E. Множество в топологическом пространстве называется связным, если оно связно как подпространство.

 

Если Е и F – связные пространства, то произведение Е ´ F также связно.

 

 

Компактность.

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

 

Определение. Топологическое пространство называется хаусдорфовым, если оно обладает следующим свойством: каковы бы ни были две различные точки p и q, существует такая окрестность U точки p и такая окрестность V точки q, что UÇV=Æ.

Любое евклидово пространство является хаусдорф