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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


научная работа Теоря графв та її використання у рзних галузях. У фзиц: для побудови схем для розвязання задач. У бологї: для розвязання задач з генетики. Спрощення розвязання задач з електротехнки за допомогою графв. Математичн розваги головоломки.

Информация:

Тип работы: научная работа. Предмет: Математика. Добавлен: 10.05.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


3
МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ
МАЛА АКАДЕМІЯ НАУК УКРАЇНИ
ЖИТОМИРСЬКЕ ТЕРИТОРІАЛЬНЕ ОБ'ЄДНАННЯ
ВІДДІЛЕННЯ: МАТЕМАТИКИ
СЕКЦІЯ: ПРИКЛАДНА МАТЕМАТИКА
БАЗОВА ДИСЦИПЛІНА: МАТЕМАТИКА
РОЗВ'ЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ГРАФІВ
2009 р.

Зміст

    Вступ 3
      Задача про призначення на посаду 5
      Інші формулювання 6
      Спортивні змагання 8
      Задача про сполучення міст 11
      Знову спортивні змагання 14
      Односторонній рух 16
      Висновок 23
      Список використаної літератури 24
      Словник термінів 25

Вступ

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

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

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

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

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

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

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

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

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

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

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

Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:

Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.

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

Виділену умову ми коротко назвемо умовою різноманітності.

Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.

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

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

Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайомими дівчатами?

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

А ось іще один варіант цієї задачі. В нашій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.

Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?

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

Щоб розв'язати цю задачу, ми знову звернемось до дводольного графа.

В цьому випадку одна множина вершин графа складатиметься із N гуртків,

А інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.

Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибору для них різних старост?

Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з п'яти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (додаток 2, де k = 4).

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

Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.

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

Висновок: ця задача допоможе керівникам дитячих закладів при організації гурткової роботи.

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

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

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

Цю ситуацію знову зручно змалювати за допомогою графа. Припустимо, що є N гравців, так що кожен з них грає N - 1 ігор з рештою учасників. Кожна гра як і раніше представляється ребром (A, B), що сполучає двох гравців, дві вершини A і В графа. Вся сукупність ігор представиться таким повним графом, що має N вершин, на додатку 3 зображений такий граф для N=6.

B кожному турі гравці якось об'єднуються в пари. припустимо поки, що N парне, і це можна зробити. На графі таке об'єднання в пари відповідає вибору ЅN несуміжних ребер, поодинці для кожної з N вершин. Для наступного туру можна вибрати нову множину ЅN ребер і так далі до тих пір, поки всі ігри не будуть зіграні. На додатку 3 ребра помічені таким чином: ті, на яких стоїть число 1, відносяться до пар, що зустрічаються в першому турі, ті на яких стоїть цифра 2 - до пар, що зустрічаються в другому турі, і так далі.

При великій кількості гравців фактичне складання такої таблиці для всіх турів відразу стає досить трудомістким, якщо не вказаний який-небудь систематичний метод. Багато довідників по проведенню турнірів містять просторові таблиці. Об'єднання гравців в пари для різних кількостей гравців (N=6, 8, 10, 12 і т.д.). При складанні таблиці досить припускати як і раніше, що кількість гравців N парна. Якщо вона виявиться непарною, то завжди можна додати фіктивного гравця F, домовившись, що той, хто повинен грати з F, в цьому турі вільний від гри.

Опишемо простий і цілком загальний метод побудови турнірної таблиці для парної кількості гравців N. Позначимо гравців числами 1, 2,..., N і запишемо ці числа в їх природному порядку в першому рядку квадратної таблиці. B наступному рядку цієї таблиці ми хочемо поставити номери суперників цих гравців в першому турі матчу. Аналогічно в третьому рядку ми випишемо номери суперників тих же гравців 1,2..., N в другому турі і т, д. до тих пір, поки всі гравці не зіграють один з одним. Ясно, що наша таблиця має бути такою, щоб всі можливі пари гравців зустрілися в ній в точності по одному разу.

Спосіб зробити це показаний в таблиці на додатку 4.

Щоб встановити суперника j-го гравця в k-м турі, досить поглянути на перетин j-го стовпця і (k + 1) - го рядка цієї таблиці.

Таблиця влаштована таким чином.

У першому рядку, як вже було сказано, перераховані гравці від 1 до N; ці ж числа ми поставили і в першому стовпці. Тепер на N - 1, що залишилися, місць кожного рядка ми ставимо числа від 2 до N в циклічному порядку по вибуванню. Перші ЅN рядків починаються з парних чисел 2,4..., N і виглядають так:

Решта рядків починається з непарних чисел 3,5..., N - 1 і мають вигляд

Відмітимо, що в цій таблиці відсутнє число 1; з іншого боку, оскільки ніхто не грає проти самого себе, те число, що стоїть зверху стовпця, ніколи не повинне в цьому стовпці повторюватися. Ми усунемо обидва недоліки, якщо замінимо всі числа, що стоять на головній діагоналі, одиницями, як показано на додатку 4. Тепер кожен гравець знайде під своїм номером номери гравців, з якими він грає в різних турах. Наприклад, гравець 4 грає з гравцем N - 1 в першому турі, з гравцем 2 в другому турі, з гравцем 1 в третьому турі, з гравцем 6 в четвертому турі і так далі і, нарешті, з гравцем N - 3 в (N - 1) - му турі.

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

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

Я хочу зупинитися на задачі про засоби сполучення, поставивши її спочатку формі питання про проведення доріг. Є декілька міст А, B, С,..., які потрібно з'єднати між собою мережею шосейних або залізних доріг. Для кожної пари міст A, B відома вартість с(А, B) будівництва сполучаючої їх дороги. Завдання полягає в тому, щоб побудувати найдешевшу з можливих мереж доріг. Замість того, щоб говорити про мережу залізниць, можна було б говорити про електричні лінії, або про водопроводи, або про нафтопроводи і тому подібне

B тому окремому випадку, коли є всього три міста A, B, C, досить побудувати одну із ліній АВС, АСВ, ВАС, причому, якщо ВС - найдорожча лінія, то саме її і треба виключити, побудувавши дорогу ВАС.

Розглянемо тепер загальний випадок. Граф найбільш дешевої сполучаючої мережі має бути деревом, оскільки якби він містив цикл, можна було б видалити одну з ланок цього циклу і міста все ще залишилися б сполученими. Отже, для сполучення n міст потрібно побудувати n - 1 доріг.

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

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

с(Т) = с(S1) + с(S2) +... + с(Sn-1).

Нам треба довести, що жодне інше дерево В, що сполучає ті ж вершини, не може виявитись дешевше за економічне дерево Т. Нехай В - найдешевше дерево, що сполучає наші вершини, а Т - будь-яке економічне дерево. Припустимо, що ребра S1, S2... економічного дерева Т занумеровані в тому порядку, в якому вони приєднувалися при побудові Т. Якщо найдешевше дерево В не збігається з Т, то Т має щонайменше одне ребро,що не належить В. Нехай S1= (A, В) - перше таке ребро, і нехай Р(А, В) - ланцюг графа В, що сполучає вершини A і B (додаток 5).

3

Якщо ребро S1 додати до В, то граф В+S1, міститиме цикл С= S1+Р(А, В), а оскільки Т не має циклів, то цикл С повинен містити принаймні одне ребро, що не належить Т. Видаливши це ребро S1 ми отримаємо дерево

В'=В+S1 - S1'

з тією ж кількістю вершин, що і В, причому його вартість дорівнює

C(В') =c(В) +с(S1) - с(S1')

Оскільки В має найменшу можливу вартість, то

с(S1) ?с(S1')

Але S1; було ланкою найменшої вартості, при додаванні якого до S1, S2..., Sn-1 не виходить циклів.

Оскільки при додаванні ребра S1' до цих ребер ми теж не отримаємо ніякого циклу, то

с(S1) = с(S1')

і, отже, В' теж має мінімальну вартість:

c(В) = c(В').

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

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

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

Розв'язуючи задачу про спортивні змагання, ми об'єднували дві команди, скажімо А і C ребром АС у тому випадку, коли ці команди вже грали один з одним. Проте такий граф не дає відповіді на одне вельми суттєве питання: хто саме виграв гру?

Цей недолік легко може бути усунений. Якщо команда A виграла у C, домовимося ставити на ребрі АС стрілку, направлену від А до C. Припустимо, що нам відомі результати всіх вже зіграних ігор, і додамо до графа відповідні стрі и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.