МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ
МАЛА АКАДЕМІЯ НАУК УКРАЇНИ
ЖИТОМИРСЬКЕ ТЕРИТОРІАЛЬНЕ ОБ’ЄДНАННЯ
ВІДДІЛЕННЯ: МАТЕМАТИКИ
СЕКЦІЯ: ПРИКЛАДНА МАТЕМАТИКА
Возможно вы искали - Дипломная работа: Методы приближённого решения матричных игр
БАЗОВА ДИСЦИПЛІНА: МАТЕМАТИКА
РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ГРАФІВ
2009 р.
Зміст
Вступ. 3
Задача про призначення на посаду. 5
Похожий материал - Дипломная работа: Нахождение решений дифференциальных уравнений
Інші формулювання. 6
Спортивні змагання. 8
Задача про сполучення міст. 11
Знову спортивні змагання. 14
Односторонній рух. 16
Очень интересно - Курсовая работа: Решение дифференциальных уравнений по методу Эйлера
Висновок. 23
Список використаної літератури. 24
Словник термінів. 25
Вступ
Перша робота по теорії графів, що належить відомому швейцарському математику Л. Ейлеру, з'явилася в 1736 р. Спочатку теорія графів здавалась досить незначним розділом математики, тому, що вона мала справу в основному з математичними розвагами і головоломками. Проте подальший розвиток математики і особливо її напрямків дав сильний поштовх до розвитку теорії графів. Вже в XIX сторіччі графи використовувалися при побудові схем електричних ланцюгів і молекулярних схем. З іншого боку, ця теорія широко застосовується в різноманітних практичних питаннях: при встановленні різного виду відповідностей, при вирішенні транспортних задач, задач про потоки в мережі нафтопроводів... Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія. Математичні розваги і головоломки також залишаються частиною теорії графів, особливо якщо віднести до них знамениту проблему чотирьох фарб, що інтригує математиків і до цього дня.
У своїй роботові я розглядаю деякі прості питання відносно загальної теорії графів; я вибрав їх так, щоб дати деяке уявлення, з одного боку, про характер досліджень, які можна проводити за допомогою графів, і, з іншого боку, - про деякі конкретні завдання, які можна розв’язувати такими методами.
Вам будет интересно - Реферат: Етапи економічного аналізу і його організація.
Актуальність моєї роботи полягає у тому, що на даний момент теорія графів все ширше застосовується в різноманітних сферах нашої життєдіяльності. Зокрема, у фізиці: для побудови схем для розв’язання задач, за допомогою графів значно спрощується розв’язання задач з електротехніки. Архітектори використовують графи для найбільш раціонального розміщення об’єктів і прокладання доріг на плані забудови населеного пункту. Біологи використовують графи для розв’язання задач з генетики. Навіть на математичних заняттях учні та студенти використовують графи для розв’язання геометричних та задач, та задач практичного змісту.
Вивчаючи теорію графів, я поставив перед собою мету: навчитись застосовувати графи, та складати задачі, тематика яких є актуальною в нинішньому суспільстві.
Також в моїй роботі представлений обширний словник термінів з теорії графів.
Задача про призначення на посаду
Нехай є кілька різних вакантних посад і група людей, які бажають їх зайняти, причому кожен із претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?
Похожий материал - Учебное пособие: Цилиндр
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра(м,р), що з’єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд: додаток 1
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людини, яка може працювати і столяром і сантехніком, і для них є чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, один столяр залишиться без роботи, хоча в даному випадку місць більше ніж претендентів, і хоча серед претендентів є люди що можуть працювати на двох посадах.