- •Частина 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.
v22v3
1 4
1 v53
5 3
v14v4
2 2
1 1 1 1 1 1 1 3
G2G3G4G5
На четвертому кроці алгоритму одержали дерево G5, що з'єднує всі вершини вихідного графа. Таким чином, деревоG5, буде мінімальним кістяковим деревом графаG.