Тема 18. Дерева

Зв’язний граф Т без циклів називається деревом. Орієнтація може не враховуватися, і тоді говорять про ребра дерева y_i. Якщо орієнтація враховуєть­ся, то говорять про дуги дерева, а саме дерево називається орієнтованим, наприклад, дерево логічних можливостей, генеалогічне дерево.

Формула А. Келі (1897 р.). Число _n позначених дерев з n вершинами дорівнює n^n-2.

Основними операціями над деревами є кодування та декодування. Ці операції використовуються для відображення дерев у пам’яті комп’ютера.

Існує три способи обходу дерев:

• „у глибину”;

• „у шир”;

• кінцевий порядок обходу.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 269-286; 2, c. 269-286; 8, c. 219-224; 9, c. 181-196; 12, c. 309-312; 14, c. 77-100; 17, c. 64-128].

Тема 19. Транспортні мережі

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

Транспортна мережа – це зв'язний орієнтований граф без петель і паралельних ребер, у якому:

1. Є тільки одна вершина, в яку не заходить жодна дуга, яка називається витоком x_s.

2. Є тільки одна вершина, з якої не виходить жодна дуга, яка називається стоком x_t.

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

Зазначимо, що потоки у неорієнтованих графах можна зобразити у вигляді потоків у відповідних орієнтованих; потоки у незв’язних графах можуть вивчатися покомпонентно; потік у петлі не впливає на розподіл потоку між вершинами.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 322-338; 2, c. 322-338; 9, c. 231-261; 17, c. 64-128].

Тема 20. Основи комбінаторного аналізу

Комбінаторика, чи комбінаторний аналіз – галузь дискретної математики, що вивчає комбінації та переміщення предметів, взаємоположення часток скінченних множин предметів довільного походження, а також нескінченних множин, що задовольняють деяким умовам підпорядкованості, виникла у XVII столітті. Але у самостійну наукову дисципліну комбінаторний аналіз сформувався лише у ХХ столітті. Комбінаторні методи застосовуються в теорії ймовірностей, випадкових процесах, статистиці, математичному програму­ванні, плануванні експериментів.

Правило суми. Якщо множина М є об'єднанням множин , що не перетинаються попарно, тоді

.

Правило добутку. Якщо – скінченні множини і – їх декартів добуток, то

.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 413-418; 2, c. 413-418; 10, c. 9-25; 12, c. 262-263; 17, c. 129-153].

Тема 21. Формули простого перелічення

Нехай – фіксована множина. Упорядковані підмножини з k елементів множини М називаються перестановками k елементів. Інакше k-перестановка – це розміщення в певному порядку k елементів із множини М. k-перестановки множини з n елементів називаються розміщеннями із n по k елементів.

Якщо в перестановці беруть участь всі елементи множини, то використо­вують термін перестановки, а кількість n-перестановок позначають через P_n.

Нехай – кількість k-розміщень n-множини (читається A із n по k).

Якщо n=k, тоді — кількість усіх способів упорядкування цих елементів: .

Розміщення і перестановки обов'язково враховують порядок елементів.

Розміщенням з повтореннями з n елементів по k (k-розміщенням з повторенням) називається кортеж (вибірка з повторенням) довжини k. Кількість k-розміщень з повтореннями обчислюється за формулою: .

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

Сполученням з n елементів по k (k-сполученням з n) називають різноманітні k-розташування (або k-вибірки) з цих елементів, які відрізняються між собою лише складом елементів без урахування їх порядку. Кількість k-сполучень з n елементів позначається , або , читається “кількість сполучень з n по k”.

З неупорядкованої множини елементів можна утворити k! упорядкованих k-розміщень позначених елементів. Тому кількість всіх k-сполучень з n елементів y k! разів менше, ніж кількість А всіх упорядкованих розміщень із n елементів по k:

Кількість k-сполучень з повтореннями з елементів n типів дорівнює кількості перестановок з повтореннями з одиниць та нулів:

.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 418-426; 2, c. 418-426; 9, c. 99-116, c. 123-130; 10, c. 31-63; 12, c. 263-266; 17, c. 129-153].