Основи вищої математики

Властивість 6: Теорема Кантора (Кантор Георг (1845-1918) - німецький математик). Функція, неперервна на відрізку, рівномірно неперервна на ньому.

(Ця властивість справедлива тільки для відрізків, а не для інтервалів і напівінтервалів.)

Приклад.

Функція неперервна на інтервалі (0, а), але не є на ньому рівномірно неперервної, тому що існує таке число >0 таке, що існують значення х1 і х2 такі, щоf(x1) - f(x2)>, - будь-яке число за умови, що х1 і х2 близькі до нуля.

Властивість 7: Якщо функція f(x) визначена, монотонна й неперервна на деякому проміжку, то й обернена їй функція х = g(y) теж однозначна, монотонна й неперервна.

Приклад. Досліджувати на неперервність функцію й визначити тип точок розриву, якщо вони є.

у точці х = -1 функція неперервна в точці х = 1 точка розриву 1-го роду

 у

3

2

-4 -1 0 1 х

Приклад. Дослідити на неперервність функцію й визначити тип точок розриву, якщо вони є.

у точці х = 0 функція неперервна в точці х = 1 точка розриву 1-го роду

у

2

1

- -/2 0 1 x

Елементи вищої алгебри

Основні поняття теорії множин

Визначення. Множиною М називається об'єднання в єдине ціле певних розрізнюваних об'єктів а, які називаються елементами множини.

а М

Множину можна описати, указавши якусь властивість, властиву всім елементам цієї множини.

Множина, що не містить елементів, називається порожньою і позначається .

Визначення. Якщо всі елементи множини А є також елементами множини В, то кажуть, що множина А включається (міститься) у множині В.

Визначення. Якщо А В, то множина А називається підмножиною множини В, а якщо при цьому А В, то множина А називається власною підмножиною множини В и позначається А В.

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

Зв'язок між включенням і рівністю множин встановлюється наступним співвідношенням:

Тут знак позначає кон'юнкцію (логічне “і”).

Операції над множинами

Визначення. Об'єднанням множин А и В називається множина С, елементи якого належать хоча б одному із множин А и В.

Позначається .

А

В

Геометричне зображення множин у вигляді області на площині називається діаграмою Ейлера-Вейна.

Визначення. Перетином множин А и В називається множина С, елементи якої належать кожній з множин А и В.

Позначення .

А С В

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

А А = А А = А; 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 = ;

Визначення. Різницею множин А и В називається множина, що складається з елементів множини А, що не належать множині В.

Позначається С = А \ В.

А В

Визначення. Симетричною різницею множин А и В називається множина С, елементи якого належать у точності одному із множин А або В.

Позначається А В.

А В = (A \ B) (B \ A)

A B

Визначення. СЕ називається доповненням множини А щодо множини Е, якщо А Е і CЕ = Е \ A.

A E

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

A \ B A; A \ A = ; A \ (A \ B) = A B;

A B = B A; A 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 B) C = A (B C); A (B C) = (A B) (A C);

A CEA = E; A CEA = ; CEE = ; CE = E; CECEA = A;

CE(A B) = CEA CEB; CE(A B) = CEA CEB;

Приклад. Виходячи з визначення рівності множин і операцій над множинами, довести тотожність і перевірити її за допомогою діаграми Ейлера-Вейна.

Із записаних вище співвідношень видно, що

= A \ В

Що й було потрібно довести.

Для ілюстрації отриманого результату побудуємо діаграми Ейлера-Вейна:

А В А В

AB

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

A \ (B C) = (A \ B) (A \ C)

Якщо деякий елемент х А \ (В С), то це означає, що цей елемент належить множині А, але не належить множинам В и С.

Множина А \ В являє собою множину елементів множини А, що не належать множині В.

Множина А \ С являє собою множину елементів множини А, що не належать множині С.

Множина (A \ B) (A \ C) являє собою множина елементів, які належать множині А, але не належать ні множині В, ні множині С.

Таким чином, тотожність можна вважати доведеною.

Відносини й функції

Визначення. Упорядкованою парою (a, b) двох елементів a і b називається множина {{a},{a, b}}.

Для будь-яких елементів a, b, c, d справедливе співвідношення:

Визначення. Декартовим добутком множин А и В називається множина всіх упорядкованих пар (a, b), де аА, bB.

Декартовий добуток п рівних множин А буде називатися п-им декартовим степенем множини А і позначається Аn.

Визначення. n-мірним відношенням R на непорожній множині А називається підмножина Аn. Якщо R - n-мірне відношення на множині А і (а1,а2,…аn)R, то кажуть, що відношення R виконується для елементів а1,а2,…аn, і записують R а1а2…аn. Якщо n = 2, то таке відношення називається бінарним.

Для бінарного відношення замість загального запису Ra1a2 застосовують запис а1Ra2.

Властивості бінарних відносин

Визначення. Добутком двох бінарних відносин R і S, заданих на множині А, називається множина

Знак називається штрих Шеффера й позначає антикон'юнкцію.

Визначення. Оберненим (інверсним) відношенням до відношення R, заданого на множині А, називається відношення R-1, обумовлене рівністю:

Якщо R, S і T - бінарні відносини на множині А, то виконуються наступні рівності:

Алгебраїчні структури

Визначення. На множині А визначена алгебраїчна операція, якщо кожним двом елементам цієї множини, узятим у певному порядку, однозначним образом поставлений у відповідність деякий третій елемент із цієї ж множини.

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

Відзначимо, що скалярний добуток векторів не може вважатися алгебраїчною операцією, тому що результатом скалярного добутку буде число, а числа не належать до множини векторів, до якого належать співмножники.

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

1) для будь-яких трьох елементів a, b, c A виконується властивість асоціативності:

2) у множині А існує такий елемент е, що для будь-якого елемента а із цієї множини виконується рівність:

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 елементів позначається Pm і обчислюється за формулою:

2) Розміщення.

Визначення. Якщо складати з т різних елементів групи по n елементів у кожній, розташовуючи взяті елементи у різному порядку. Комбінації, що вийшли при цьому, називаються розміщеннями з т елементів по n.

Загальне число таких розміщень розраховуються за формулою:

Загалом кажучи, перестановки є частковим випадком розміщень.

3) Сполучення.

Визначення. Якщо з т елементів складати групи по п елементів у кожній, не звертаючи уваги на порядок елементів у групі, то комбінації, що вийшли при цьому, називаються сполученнями з т елементів по n.

Загальне число сполучень знаходиться за формулою:

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

Якщо серед т елементів є т1 однакових елементів одного типу, т2 однакових елементів іншого типу і далі, то при перестановці цих елементів усілякими способами одержуємо комбінації, кількість яких визначається за формулою:

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

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

Число всіх можливих комбінацій з 30 літер по двом дорівнює . Якщо врахувати можливість того, що літери можуть повторюватися, то число повторюваних комбінацій дорівнює 30 (одна можливість повтору для кожної літери). Разом, повна кількість комбінацій по дві літери дорівнює 900.

Якщо до номера додається ще одна літера з алфавіту в 30 літер, то кількість комбінацій збільшується в 30 разів, тобто досягає 27.000 комбінацій.

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

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

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

Біном Ньютона - це формула, що виражає вираз (a + b)n у вигляді багаточлена. Ця формула має вигляд:

- число сполучень з п елементів по k.

Широко відомі формули скороченого множення квадрата суми й різниці, куба суми й різниці, є окремими випадками бінома Ньютона.

Коли ступінь бінома невисокий, коефіцієнти багаточлена можуть бути знайдені не розрахунком по формулі кількості сполучень, а за допомогою так званого трикутника Паскаля. (Блез Паскаль (1623-1662) - французький математик).

Цей трикутник має вигляд:

1

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.

Приклад. У розкладанні знайти члени, що містять х, якщо k=3, p=2, n=8, =9.

За формулою бінома Ньютона маємо:

З врахуванням числових значень:

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

Знайдемо число i, що відповідає цьому члену:

Знаходимо:

Приклад. У розкладі знайти члени, що містять x. т=9, =6.

За узагальненою формулою бінома Ньютона одержуємо:

Для знаходження повного розкладу необхідно визначити всі можливі значення ni, однак, це пов'язане з величезними обчисленнями. Однак, оскільки треба знайти тільки члени, що містять х6, то n1 = 6, а сума всіх чотирьох значень п дорівнює 9. Виходить, сума п2 + п3 + п4 = 3.

Розглянемо можливі значення цих величин:

n2	0	0	3	1	1	0	2	0	2	1
n3	0	3	0	2	0	1	1	2	0	1
n4	3	0	0	0	2	2	0	1	1	1

Шукані члени розкладу:

Елементи математичної логіки

Математична логіка - різновид формальної логіки, тобто науки, що вивчає умовиводи з погляду їхньої формальної будови.

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

У математичній логіці не розглядається сам зміст висловлень, визначається тільки його істинність або хибність, що прийнято позначати відповідно І або Н.

Зрозуміло, що істині й помилкові висловлювання утворять відповідні множини. За допомогою простих висловлень можна складати складніші, з'єднуючи прості висловлювання сполучниками “і”, “або”.

Таким чином, операції з висловлюваннями можна описувати за допомогою деякого математичного апарата.

Вводяться наступні логічні операції (зв'язування) над висловлюваннями

Заперечення. Запереченням висловлювання Р називається висловлювання, що істинне тільки тоді, коли висловлювання Р неправдиве.

Позначається Р або .

Відповідність між висловлюваннями визначається таблицями істинності. У нашому випадку ця таблиця має вигляд:

P	Р
І	Н
Н	І

2) Кон'юнкція. Кон'юнкцією двох висловлювань P і Q називається висловлювання, істинне тоді й тільки тоді, коли істинні обоє висловлювань.

Позначається P&Q або РQ.

P	Q	P&Q
І	І	І
І	Н	Н
Н	І	Н
Н	Н	Н

3) Диз'юнкція. Диз'юнкцією двох висловлень P і Q називається висловлювання, помилкове тоді й тільки тоді, коли обоє висловлювання помилкові.

Позначається PQ.

P	Q	PQ
І	І	І
І	Н	І
Н	І	І
Н	Н	Н

4) Імплікація. Імплікацією двох висловлень P і Q називається висловлювання, неправдиве тоді й тільки тоді, коли висловлювання Р істинне, а Q - неправдиве.

Позначається PQ (або РQ). Висловлювання Р називається посилкою імплікації, а висловлювання Q - наслідком.

P	Q	PQ
І	І	І
І	Н	Н
Н	І	І
Н	Н	І

5) Еквіваленція. Еквіваленцією двох висловлень P і Q називається висловлювання, істинне тоді й тільки тоді, коли істинність висловлювань збігається.

Позначається РQ або РQ.

P	Q	PQ
І	І	І
І	Н	Н
Н	І	Н
Н	Н	І

За допомогою цих основних таблиць істинності можна скласти таблиці істинності складних формул.

Приклад. За допомогою таблиць істинності перевірити, чи є еквівалентними формули і ш.

Складемо таблиці істинності для кожної формули:

p	r		(pr)
І	І	Н	І	І
І	Н	Н	Н	І
Н	І	І	Н	Н
Н	Н	І	Н	Н

p	r
І	І	Н	Н	Н	І
І	Н	Н	І	І	І
Н	І	І	Н	І	І
Н	Н	І	І	І	І

Дані формули не є еквівалентними.

Приклад. За допомогою таблиць істинності перевірити, чи є еквівалентними формули і ш.

Складемо таблиці істинності для заданих формул.

p	q	r	pq	(pq)r
І	І	І	І	І
І	І	Н	І	І
І	Н	І	Н	І
І	Н	Н	Н	Н
Н	І	І	Н	І
Н	І	Н	Н	Н
Н	Н	І	І	І
Н	Н	Н	І	І

p	q	r	pq	qp	(pq)(qp)	(pq)(qp)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(X1, X2, …, Xn) називається довільна n-місна функція, аргументи й значення якої належать множині {0, 1}.

Загалом кажучи між логічними висловлюваннями, логічними зв'язуваннями й булевими функціями проглядається явна аналогія. Якщо логічні функції можуть приймати значення істинне або неправдиве, то для булевой функції аналогами цих значень будуть значення 0 або 1.

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

X1	X2	X1	X1&X2	X1X2	X1X2	X1X2
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Числення предикатів

Визначення. Предикатом P(x1, x2, …, xn) називається функція, змінні якої приймають значення з деякої множини М, а сама функція приймає два значення: І (істина) і Н (неправда), тобто

Предикат від п аргументів називається п-місним предикатом. Висловлювання вважаються нуль-місними предикатами.

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

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

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

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) (xi)A(xi) A(xj), де формула А(хi) не містить змінної xi.

5) A(xi) (xj)A(xj), де формула А(хi) не містить змінної xi.

Скінченні графи й сітки

Основні визначення

Визначення. Якщо на площині задати скінченну множину 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. Два ребра називаються суміжними, якщо вони мають спільну вершину.

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

Визначення. Графи G1(V1, X1) і G2(V2, X2) називаються изоморфмными, якщо існує взаємно однозначне відображення : V1 V2, що зберігає суміжність.

Визначення. Маршрутом (шляхом) для графа G(V, X) називається послідовність v1x1v2x2v3…xkvk+1... Маршрут називається замкнутим, якщо його початкова й кінцева точки збігаються. Число ребер (дуг) маршруту (шляху) графа називається довжиною маршруту (шляху).

Визначення. Незамкнутий маршрут (шлях) називається ланцюгом. Ланцюг, у якій всі вершини попарно різні, називається простим ланцюгом.

Визначення. Замкнутий маршрут (шлях) називається циклом (контуром). Цикл, у якому всі вершини попарно різні, називається простим циклом.

Матриці графів

Нехай D = (V, X) - орграф, де V = {v1, …, vn}, X = {x1, … , xm}.

Визначення. Матрицею суміжності орграфа D називається квадратична матриця A(D) = [aij] порядку п, у якої

Визначення. Якщо вершина v є кінцем ребра х, то говорять, що v і х - інцидентні.

Визначення. Матрицею інцидентності орграфа D називається матриця розмірності пт B(D) = [bij], для якої

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

Складемо матрицю суміжності:

	v1	v2	v3
V1	0	1	0
V2	1	0	1
v3	1	0	0

Тобто - матриця суміжності.

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

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

Тобто

Якщо граф має кратні дуги (ребра), то в матриці суміжності приймається aij=k, де k - кратність дуги (ребра).

За допомогою матриць суміжності й інцидентності завжди можна повністю визначити граф і всі його компоненти. Такий метод завдання графів дуже зручний для обробки даних на ЕОМ.

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

Складемо матрицю інцидентності:

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

Отже:

Побудуємо тепер орієнтований граф із заданою матрицею суміжності.

Складемо матрицю інцидентності для орієнтованого графа.

Елемент матриці дорівнює 1, якщо точка є кінцем дуги, -1 - якщо початком дуги, якщо дуга є петлею, елемент матриці запишемо як 1.



Таким чином, операції із графами можна звести до операцій з їхніми матрицями.

Досяжність і зв'язність

Визначення. Вершина w графа D (або орграфа) називається досяжною з вершини v, якщо або w=v, або існує шлях з v в w(маршрут, що з'єднує v і w).

Визначення. Граф (орграф) називається зв'язним, якщо для будь-яких двох його вершин існує маршрут (шлях), що їх зв'язує. Орграф називається односторонньо зв'язним, якщо для будь-яких двох його вершин принаймні одна досяжна з іншої.

Визначення. Псевдографом D(V, X), асоційованим з орієнтованим псевдографом, називається псевдограф G(V, X0) у якому Х0 виходить із Х заміною всіх упорядкованих пар (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 ребро мінімальної довжини. Разом з інцидентними йому вершинами воно утворить підграф G2.

2) Будуємо граф G3, додаючи до графа G2 нове ребро мінімальної довжини, обране серед ребер графа G, кожне з яких інцидентне якійсь з вершин графа G2, і одночасно інцидентне якійсь з вершин графа G, що не міститься в графі G2.

3) Будуємо графи G4, G5, …, Gn, повторюючи дії пункту 2 доти, доки не переберемо всі вершини графа G.

Приклад. Визначити мінімальне кістякове дерево навантаженого графа.

Граф називається навантаженим, якщо на множині його дуг задана деяка функція, що називається ваговою функцією, і визначає довжину дуги.

У нашому прикладі - вагова функція визначає довжини дуг числами 1, 2, 3, 4, 5.

v2 2 v3

1 4

1 v5 3

5 3

v1 4 v4

2 2

1 1 1 1 1 1 1 3

G2 G3 G4 G5

На четвертому кроці алгоритму одержали дерево G5, що з'єднує всі вершини вихідного графа. Таким чином, дерево G5 , буде мінімальним кістяковим деревом графа 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=FV, де V - окіл точки р в E.

При цьому множина F називається підпростором простору Е.

Метричний простір

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

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

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

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

Визначення. Метричним простором називається множина Е з заданою на ній метрикою f.

Визначення. Число (x, y), де х Е та у Е - задані точки, називається відстанню між цими точками.

Визначення. Нехай r - додатне число. Множина {y: (x, y) < r} називається відкритою кулею радіуса r із центром у точці х; множина {y: (x, y) r} - замкнутою кулею радіуса r із центром у точці х.

Наприклад, для тривимірного евклідового простору 3 метрика визначається як , де х(х1, х2, x3) 3 і y(y1, y2, y3) 3.

Відкриті й замкнуті множини

Визначення. Нехай Е - топологічний простір, а U - його підмножина. Множина U називається відкритим, якщо воно є околицею для будь-якої точки U.

Визначення. Нехай Е - топологічний простір, а F - його підмножина. Множина F називається замкнутою, якщо множина E \ F - відкрита.

Відзначимо наступні властивості:

1) Об'єднання будь-якої сукупності відкритих множин відкрите.

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

3) Перетин будь-якої сукупності замкнутих множин замкнутий.

4) Об'єднання скінченного числа замкнутих множин замкнуте.

Визначення. Якщо А - будь-яка множина в топологічному просторі Е, то об'єднання всіх відкритих множин, що містяться в А, відкрите. Це об'єднання називається внутрішністю множини А. Позначається Int. Це об'єднання буде найбільшою відкритою множиною, що міститься в А.

Визначення. Множина називається замиканням множини А. Множина FrА = 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 - топологічні простори. Множина EF визначається як множина пар (p, q), де pE, a qF. Вона перетворюється в топологічний простір у такий спосіб: якщо (p, q) EF, то окіл точки (p, q) - це будь-яка множина, що містить множину виду UV, де U - окіл точки p в E, a V - околиця q в F.

Визначення. Множина EF, перетворене в топологічний простір тільки що описаним способом, називається топологічним добутком просторів E і F.

Наприклад, у тривимірному евклідовому просторі тор є топологічним добутком кола на себе.

Зв'язність

Визначення. Простір E називається зв'язним, якщо його не можна представити у вигляді об'єднання двох непустих множин, що не перетинається в E. Множина в топологічному просторі називається зв'язною, якщо воно зв'язна як підпростір.

Якщо Е и F - зв'язні простору, то добуток Е F також складно.

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

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

Визначення. Топологічний простір називається хаусдорфовим, якщо він має наступну властивість: які б не були дві різні точки p і q, існує така окіл U точки p і такий окіл V точки q, що UV=.

Будь-який евклідовий простір є хаусдорфовим.

Будь-який підпростір евклідового простору хаусдорфовий. Насправді будь-який підпростір будь-якого хаусдорфового простору хаусдорфовий.

Перш ніж визначати компактність, наведемо кілька попередніх визначень.

Визначення. Покриття топологічного простору E - набір множин з E, об'єднання яких дає весь простір E. Воно називається відкритим покриттям, якщо кожна множина в наборі відкрито.

Визначення. Нехай дане покриття топологічного простору. Підпокриттям називається покриття, всі множини якого належать даному покриттю.

Визначення. Компактним простором називається хаусдорфів простір, що володіє тою властивістю, що кожне його відкрите покриття містить скінченне підпокриття, тобто покриття, що складається зі скінченного числа множин. Множина в топологічному просторі називається компактною, якщо вона є компактним підпростором.

Компактна підмножина евклідового простору повинна бути замкнутою і обмеженою. Якщо компактні простори, що перемножують, A і B лежать в евклідових просторах розмірностей m і n, то їх добуток є підпростір в n+m-мірному просторі. Тому що простори A і B компактні, вони замкнуті й обмежені. Тому їхній добуток є замкнутою й обмеженою підмножиною евклідового простору. Отже, AB компактний.

Размещено на Allbest.ru

...