Науково-дослідна робота «Графи довкола нас»
Муніципальна загальноосвітня бюджетна установа –
середня загальноосвітня школа №51
Єгорчева Вікторія Андріївна
Гіпотеза: Якщо теорію графів зблизити з практикою, можна отримати найсприятливіші результати.
Мета:Ознайомиться з поняттям графи та навчитися застосовувати їх при вирішенні різних завдань.
1)Розширити знання способи побудови графів.
2)Виделить типи завдань, розв'язання яких потребує застосування теорії графів.
3) Дослідити використання графів у математиці.
«Ейлер обчислював без жодного видимого зусилля, як людина дихає або як орел ширяє над землею».
I. Вступ. Стор.
II. Основна частина.
1. Поняття графа. Завдання про Кенігсберзькі мости. Стор.
2. Властивості графів. Стор.
3. Завдання із застосуванням теорії графів. Стор.
Значення графів. Стор.
IV. Список використаної літератури. Стор.
Теорія графів – наука порівняно молода. "Графи" мають корінь грецького слова "графо", що означає "пишу". Той самий корінь у словах «графік», «біографія».
Почувши та прочитавши теорію графів мене ця тема дуже зацікавила. Я вирішила дізнатися, як можна застосувати теорію графів на практиці, в житті, і поділитися з цим з однокласниками.
У своїй роботі я розглядаю, яким чином використовується теорія графів у різних сферах життя людей. Кожен вчитель математики і кожен учень знає, скільки труднощів доставляє рішення геометричних завдань, і навіть текстових завдань з алгебри. Дослідивши можливість застосування теорії графів у шкільному курсі математики, я дійшла висновку, що ця теорія значно спрощує розуміння та вирішення завдань.
1. Поняття графа.
Перша робота з теоріїграфів належить Леонарду Ейлер. Вона з'явилася в 1736 в публікаціях Петербурзької Академії Наук і починалася з розгляду завдання про кенігсберзьких мостах.
Ви, напевно, знаєте, що є таке місто Калінінград, раніше воно називалося Кенігсберг. Через місто протікає річка Преголя. Вона ділиться на два рукави та огинає острів. У 17 столітті у місті було сім мостів, розташованих так, як показано на малюнку.
Таку фігуру, що складається з точок та ліній, що зв'язують ці точки, називаютьграфом. Точки A, B, C, D називають вершинами графа, а лінії, які з'єднують вершини – ребра графа. На малюнку з вершин B , C , D виходять по 3 ребра, та якщо з вершини A – 5 ребер. Вершини, з яких виходить непарне число ребер, називаютьнепарними вершинами,а вершини, з яких виходить парна кількість ребер, -парними.
Вирішуючи завдання для кенігсберзькі мости, Ейлер установив, зокрема, характеристики графа:
1. Якщо всі вершини графа парні, то можна одним розчерком (тобто не відриваючи олівця від паперу і не проводячи двічі по одній і тій же лінії) накреслити граф. При цьому рух можна почати з будь-якої вершини та закінчити у тій самій вершині.
2.Граф із двома непарними вершинами теж можна накреслити одним розчерком. Рух потрібно починати від будь-якої непарної вершини, а закінчувати на іншій непарній вершині.
3.Граф із більш ніж двома непарними вершинами неможливо накреслити одним розчерком.
4. Число непарних вершин графа завжди парне.
5.Если у графі є непарні вершини, то найменше число розчерків, якими можна намалювати граф буде дорівнює половині числа непарних вершин цього графа.
Наприклад, якщо фігура має чотири непарні, то її можна накреслити щонайменше двома розчерками.
У задачі про сім кенігсберзьких мостів усі чотири вершини відповідного графа непарні, тобто. не можна пройти по всіх мостах один раз і закінчити шлях там, де його розпочали.
3.Рішення задач за допомогою графів.
1. Завдання на креслення фігур одним розчерком.
Спроби намалювати одним розчерком пера кожну з наступних постатей призводять до неоднакових результатів.
Якщо непарних точок у фігурі немає, вона завжди піддається вимальовування одним розчерком пера, байдуже, з якого місця не починати креслення. Такими є фігури 1 і 5.
Якщо у фігурі є лише одна пара непарних точок, то таку фігуру можна намалювати одним розчерком, почавши креслення в одній з непарних точок (байдуже до якої). Легко збагнути, що креслення має закінчуватися у другій непарній точці. Такі фігури 2, 3, 6. У фігурі 6, наприклад, креслення треба починати з точки А, або з точки В.
Якщо фігура має більше однієї пари непарних точок, вона зовсім не може бути намальована одним розчерком. Такі фігури 4 і 7, що містять дві пари непарних точок. Сказаного достатньо, щоб безпомилково розпізнавати, які фігури не можна намалювати одним розчерком і які можна, а також з якої точки треба починати креслення.
Пропоную накреслити одним розчерком такі постаті.
2. Розв'язання логічних задач.
У першості класу з настільного тенісу 6 учасників: Андрій, Борис, Віктор, Галина, Дмитро та Олена. Першість проводять за круговою системою – кожен із учасників грає з кожним із решти один раз. На даний момент деякі ігри вже проведені: Андрій зіграв із Борисом, Галиною, Оленою; Борис – з Андрієм, Галиною; Віктор – із Галиною, Дмитром, Оленою; Галина – зАндрієм, Віктором та Борисом. Скільки ігор проведено зараз і скільки ще залишилося?
Побудуємо граф як показано малюнку.
На цьому малюнку граф має 8 ребер, отже залишилося провести 8 ігор.
У дворі, що оточений високим парканом, знаходяться три будиночки: червоний, жовтий та синій. У паркані є три хвіртки: червона, жовта та синя. Від червоного будиночка проведіть доріжку до червоної хвіртки, від жовтого будиночка – до жовтої хвіртки, від синього – до синьої так, щоб ці доріжки не перетиналися.
Розв'язання задачі наведено на малюнку.
3. Розв'язання текстових задач.
Для вирішення завдань методом графів треба знати наступний алгоритм:
1.Про який процес йдеться у задачі? 2. Які величини характеризують цей процес? 3.Яким співвідношенням пов'язані ці величини? 4. Скільки різних процесів описується у задачі? 5.Чи є зв'язок між елементами?
Відповідаючи на ці питання, аналізуємо умову задачі та записуємо її схематично.
Наприклад. Автобус йшов 2 год зі швидкістю 45 км/год та 3 год зі швидкістю 60 км/год. Який шлях пройшов автобус за ці 5 годин?
S
S ²=180 км V ²=60 км/год t ²=3 год
1) 45 x 2 = 90 (км) – пройшов автобус за 2 год.
2) 60 x 3 = 180 (км) – пройшов автобус за 3 год.
3) 90 + 180 = 270 (км) - пройшов автобус за 5 год.
В результаті роботи над проектом я дізналася, що Леонард Ейлер був основоположником теорії графів, вирішив завдання із застосуванням теорії графів. Для себе зробила висновок, що теорія графів знаходить застосування у різних галузях сучасної математики та її численних додатків. Не доводиться сумніватися корисності ознайомлення нас, учнів, з основними поняттями теорії графів. Рішення багатьохматематичних завдань спрощується, якщо вдається використати графи. Подання даних як графа надає їм наочність. Багато доказів також спрощуються, набувають переконливості, якщо скористатися графами. Особливо це стосується таких галузей математики, як математична логіка, комбінаторика.
Таким чином, вивчення цієї теми має велике загальноосвітнє, загальнокультурне та загальноматематичне значення. У повсякденному житті все більше застосування знаходять графічні ілюстрації, геометричні уявлення та інші прийоми та методи наочності. З цією метою вивчення елементів теорії графів корисно запровадити у початковій та середній ланці школи, хоча б у позакласній роботі, оскільки до програми з математики цю тему не включено.
V. СПИСОК ЛІТЕРАТУРИ:
1. Альхова З.М., Макєєва А.В. "Позакласна робота з математики".
3. Я.І.Перельман «Цікаві завдання та досліди». - Москва: Просвітництво, 2000 р.
Проект на тему «Графи навколо нас» виконав учень 7 «А» класу МОУ-сош №3г.Красний Кут Зайцев Микита.
Відмінною рисою роботи Зайцева Микити є її актуальність, практична спрямованість, глибина розкриття теми, можливість її у подальшому.
Робота є творчою у вигляді інформаційного проекту. Учень вибрав цю тему, щоб показати взаємозв'язок теорії графів з практикою з прикладу маршруту шкільного автобуса, показати, що теорія графів знаходить застосування у різних галузях сучасної математики та її численних додатків, особливо це стосується економіки, математичної логіки, комбінаторики. Він показав, що розв'язання задач значно спрощується, якщо вдається використовувати графи, подання даних у вигляді графа надає їм наочність,багато доказів також спрощуються, набувають переконливості.
У роботі розглядаються такі питання як:
1. Поняття графа. Завдання про Кенігсберзькі мости.
2. Властивості графів.
3. Завдання із застосуванням теорії графів.
4. Значення графів.
5. Варіант маршруту шкільного автобуса.
За виконання своєї роботи Зайцев Н. використовував:
1. Альхова З.М., Макєєва А.В. "Позакласна робота з математики".
3. Я.І.Перельман «Цікаві завдання та досліди». - Москва: Просвітництво, 2000 р.
Робота виконана грамотно, матеріал відповідає вимогам цієї теми, відповідні малюнки додаються.
Ця робота рекомендована на науково-практичну конференцію «Крок у майбутнє».