Питання для самоконтролю
Дайте визначення поняття «множина».
Якими способами можна задати множину?
Скільки існує підмножин скінченної множини, складеної з
елементів?Що являють собою діаграми Ейлера? З якою метою їх використовують?
Чому дорівнює потужність скінченної множини?
У якому випадку дві нескінченні множини будуть рівнопотужними?
Які множини називаються лічильними?
Назвіть основні операції над множинами.
Що являє собою різниця двох множин? Їх об’єднання? Перетин?
Дайте визначення доповнення множини.
Сформулюйте закони, яким підпорядковуються операції над множинами.
Які властивості характерні для кожної з операцій над множинами?
Чи виконується в загальному випадку комутативний закон для операції «різниця множин»?
Задачі для самостійного розв'язування
Задано множини:
і
.
Знайти їх об'єднання, перетин і різниці.Дано множини:
,
.
Знайти для цих множин об'єднання,
перетин і різниці
та
.Маючи такі множини:
,
визначити їх об'єднання, перетин і
різниці
та
.Знайти множини А і В, якщо:
Виразити через множини А, В і С заштриховану ділянку D на діаграмі Ейлера (рис.1.11).
Рис. 1.11. Графічне подання умови задачі 5
Нехай А – множина студентів групи; В – множина студентів-відмінників тієї самої групи. Що означають такі твердження:
На діаграмі Ейлера (рис.1.12) заштрихувати ділянку, відповідну такій множині:
.
Рис.1.12. Графічне подання умови задачі 7
Дано множини:
.
Визначити множини:
Знайти множини А та В, якщо:
Дано множини:
.
Виразити через них такі множини:
.
Розділ 2 елементи теорії графів
Розглянуто основні поняття теорії графів і їх застосування до розв'язування оптимізаційних задач.
Багато структур, цикавих із точки зору математики, інформатики та їх практичного застосування можуть бути описані за допомогою графів. У загальному значенні графом називають непорожню множину вершин (вузлів), з'єднаних ребрами. Для різних галузей застосування графи можуть розрізнятися напрямами, обмеженнями на кількість зв’язків, додатковими відомостями про вершини та ребра. У строгому математичному визначенні граф являє собою пару множин: G = (V, E), де V – підмножина будь-якої лічильної множини (вершини), а E – підмножина V × V (ребра або зв’язки).
Теорія графів являє собою розділ дискретної математики, який вивчає властивості графів.
Зазначимо, що ця теорія набула широкого застосування в різних галузях науки та виробництва. Наприклад, у геоінформаційних системах (ГІС). Тут існуючі або проектовані будинки, споруди, квартали і т. п. розглядаються як вершини графа (множина V), а дороги, інженерні мережі, лінії електропередачі та ін., що їх з'єднують, як ребра (множина E). Обчислення, проведені на такому графі, дають можливість, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний транспортний маршрут. Коли за вершини графа взяти роботи, які мають бути виконані, а ребра будуть відповідати порядку їх виконання, то використовуючи методи теорії графів, можна, зокрема, визначити оптимальний порядок проведення робіт.
У теорії графів існує велика кількість невирішених проблем і поки що не доведених гіпотез.
Розглянемо основні поняття теорії графів.