Научная работа: Розвязування задач за допомогою графів

МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ

МАЛА АКАДЕМІЯ НАУК УКРАЇНИ

ЖИТОМИРСЬКЕ ТЕРИТОРІАЛЬНЕ ОБ’ЄДНАННЯ

ВІДДІЛЕННЯ: МАТЕМАТИКИ

СЕКЦІЯ: ПРИКЛАДНА МАТЕМАТИКА

БАЗОВА ДИСЦИПЛІНА: МАТЕМАТИКА

РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ГРАФІВ

2009 р.

Зміст

Вступ. 3

Задача про призначення на посаду. 5

Інші формулювання. 6

Спортивні змагання. 8

Задача про сполучення міст. 11

Знову спортивні змагання. 14

Односторонній рух. 16

Висновок. 23

Список використаної літератури. 24

Словник термінів. 25

Вступ

Перша робота по теорії графів, що належить відомому швейцарському математику Л. Ейлеру, з'явилася в 1736 р. Спочатку теорія графів здавалась досить незначним розділом математики, тому, що вона мала справу в основному з математичними розвагами і головоломками. Проте подальший розвиток математики і особливо її напрямків дав сильний поштовх до розвитку теорії графів. Вже в XIX сторіччі графи використовувалися при побудові схем електричних ланцюгів і молекулярних схем. З іншого боку, ця теорія широко застосовується в різноманітних практичних питаннях: при встановленні різного виду відповідностей, при вирішенні транспортних задач, задач про потоки в мережі нафтопроводів... Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія. Математичні розваги і головоломки також залишаються частиною теорії графів, особливо якщо віднести до них знамениту проблему чотирьох фарб, що інтригує математиків і до цього дня.

У своїй роботові я розглядаю деякі прості питання відносно загальної теорії графів; я вибрав їх так, щоб дати деяке уявлення, з одного боку, про характер досліджень, які можна проводити за допомогою графів, і, з іншого боку, - про деякі конкретні завдання, які можна розв’язувати такими методами.

Актуальність моєї роботи полягає у тому, що на даний момент теорія графів все ширше застосовується в різноманітних сферах нашої життєдіяльності. Зокрема, у фізиці: для побудови схем для розв’язання задач, за допомогою графів значно спрощується розв’язання задач з електротехніки. Архітектори використовують графи для найбільш раціонального розміщення об’єктів і прокладання доріг на плані забудови населеного пункту. Біологи використовують графи для розв’язання задач з генетики. Навіть на математичних заняттях учні та студенти використовують графи для розв’язання геометричних та задач, та задач практичного змісту.

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

Також в моїй роботі представлений обширний словник термінів з теорії графів.

Задача про призначення на посаду

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

Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?

Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра(м,р), що з’єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд: додаток 1

Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--