Графи та їх застосування

 

Розв′язання: Розв′язування системи зводиться до  розв′язування рівняння  першого степеня з однією  змінною,  яке відповідає  графу,  зображеному на рис.3.30, д:

 

 

Рис.3.30.

Щоб  знайти  х,  треба в рівняння, що  відповідає  графу,  поданому  на рис.3.30,г, замість змінної z підставити її значення  і записати  відповідне

рівняння:    

Аналогічно  знаходимо  y  (рис.3.30,б):

Відповідь: (1,-1,2 ) .

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

Розглянутий  спосіб  розв′язування  систем лінійних рівнянь є досить наглядним та простим для розуміння.

 

РОЗДІЛ 4. ГРАФИ В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ

 

В цьому розділі проводиться  аналіз начальних та спеціальних  програм навчання математики з теми дослідження, а також запропоновано  розроблене нами факультативне заняття  на тему «Граф. Розв’язування задач  за допомогою графа» для учнів 11 класу.

 

4.1. Аналіз навчальних  програм з теми дослідження

 

Проведемо аналіз навчальних  та спеціальних програм навчання математики з теми дослідження.

4.1.1. Програма спеціального  курсу «Прикладна математика  для учнів 8-11 класів з поглибленим  вивченням математики»

(автор О.Б.Рудик)

 

Кількість навчальних годин (за рахунок регіонального і шкільного  компонентів навчального плану  або надання додаткових платних  освітніх послуг): по 2 години на тиждень. Щороку – 70 годин. На весь курс – 280 годин. При цьому учні повинні мати можливість додаткової самостійної роботи за комп’ютером  протягом двох годин на тиждень.

11 клас. Графи (36 годин)

Зміст навчального  матеріалу: вершина, ребро і дуга графа. Зв’язність. Матриця суміжності і незвідність. Кількість маршрутів. Найкоротший шлях. Модель лабіринту. Вершини графа. Розбиття графи на компоненти. Граф як модель многогранника для побудови й аналізу розгорток [1, c.3].

 

4.1.2. факультативна  програма з математики «Економіка  в задачах математики»

(автори М.А.Вайнтрауб,  О.С.Стрельченко, І.Г.Стрельченко)

 

Дана програма є частиною єдиної програми з математики для  учнів 10-11 класів шкіл, ліцеїв та гімназій економічного профілю.  Автори програми для для вивчення графів пропонують тему «Застосування графів та методів  їх дослідження для розв’язування  економічних задач», на вивчення якої відводиться 10 годин [23, c. 56].

Метою вивчення теми є: дати означення та сформувати уявлення про основні положення теорії графів у задачах з економіки.

Зміст навчального  матеріалу: Основніпоняття теорії графів. Сітьове планування. Правила побудови сітьового графіка. Метод приведення до базового вузла. Поняття календарного графіка. Система сітьового планування та управління. Розрахунок сітьових графіків. Сітьовий план розв’язування.

4.1.3. Програма розвитку  творчого мислення  учнів (Шахи, інтелектуальні ігри. Основи математичної  логіки. Інтегрований курс навчання.)

(автор М.А.Вайнбург)

Курс «інтелектуальні  ігри» розроблений для учнів  основної та старшої школи і розрахований на шість років вивчення. При проходженні  цього курсу розділ «Теорія математичних лабіринтів і графів» пропонується вивчати на четвертому році на 4 році навчання (клас визначається в залежності з якого класу почали курс). Під  час проходження цього розділу  засвоюються вміння та навички, які  необхідні для вивчення курсу  інформатики та обчислювальної техніки.

Згідно з програмою, на освоєння розділу потрібно 36 годин (1 година на тиждень), в тому числі 15 годин теоретичних і 21 година практичних занять [1, c. 5].

Мета інтегрованого  курсу: розвинути творчі здібності учнів, застосовуючи інтегроване навчання на сучасному рівні. Курс містить нові педагогічні напрямки навчання трьох курсів: науково-практичної роботи (НПР), розвиваюче навчання (РН) та прикладну математику (ПМ).

Логічні структури тематики побудовано таким чином, що кожен  розділ з будь-якого напряму одночасно  доповнюється, повторюється, поглиблюється  в інших напрямах (Додаток А).

Комплексна програма трьох  напрямків розрахована на 4-5 років  і містить оригінальну методику викладання з елементами винахідництва  та математичного моделювання. Запропоновані  курси створюються за принципами циклічної побудови змісту навчання. З 3-го по 5-й рік навчання передбачається вивчити методи розв’язування задач  аналізу та синтезу логічних структур застосовуючи графічні моделі, статистику та розв′язок комплексної задачі. Цим і завершується викладання інтегрованого  курсу.

Тематичне планування матеріалу: 3 години на тиждень по 1 годині на кожний напрям, усього 108 годин, у тому числі 78 годин практичних занять і 30 годин теоретичних занять.

4.2. Факультативне  заняття з теорії графів для  учнів  11 класу на тему: «Граф. Розв’язування задач за допомогою графа»

 

Тема  уроку:  Граф. Розв᾿язування задач за допомогою графа.

Мета  уроку:  Скласти уявлення про організацію інформації у вигляді дерева (графа). Освоїти поняття граф. Навчитися розв’язувати  завдання за допомогою графів.

Знання: Учень знає призначення  графів

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

Застосування: Уміє записувати арифметичні вирази у вигляді  графів, відображати інформацію у  вигляді семантичної мережі, зображати  класифікації різних об'єктів у вигляді  дерева

Аналіз: Вміє з безлічі  предметів виокремити  об'єкти, позначати  зв'язки між ними.

Обладнання: комп'ютер, таблиці, картки. Тривалість уроку: 40 хв

План уроку

I етап – організаційний момент (3 хв).

II етап – нова тема. Поняття графа. (8 хв)

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

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

Розв′язування  багатьох математичних задач значно спрощується, якщо вдається використовувати графи. Представлення даних у вигляді  графа надає їм наочність і  простоту. Багато математичних доведень також спрощуються, набувають переконливості, якщо користуватися графами. Для  розв’язання  логічних задач зручно використовувати графи.

Графи – це  малюнки, які  складаються з точок і ліній, що сполучають ці точки. Кожна пара точок в графі може бути з'єднана лініями.  Лінія вказує на зв'язок між двома точками. Точки називаються вершинами графа, а лінії – ребрами .

Ребро може мати напрямок, який вказується стрілкою. У графа обов'язково є Граф без ребер називається  порожнім. Приклади різних графів наведені на рисунку.

Дерево (граф) – це  спосіб організації інформації про відносини  між об'єктами.

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

Перша робота з теорії графів належить Леонарду  Ейлеру (1736р.).

Термін граф вперше ввів 1936р. угорський математик Денеш  Кеніг. Графами були названі схеми, що складаються з точок і  ці точки з’єднуються відрізками  прямих або кривих.

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

За допомогою графів зображуються схеми доріг, газопроводів, тепло- та електро- мереж.

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

III етап. Представлення інформації у вигляді дерева. (2 хв)

       Особливим  видом графа є дерево. Дана  форма моделі застосовується  тоді, коли елементи модельованого  об'єкта знаходяться в стані якогось підпорядкування. Модель управління підприємством (школою, театральним колективом і т. д.) дуже зручно представляти у вигляді дерева.

 

Описати граф-це означає, відповісти на питання:

Скільки вершин в графі?

Чи є  ребра?

Чи є напрямок?

Чи всі вершини з'єднані ребрами?

На яких шкільних предметах  ви зустрічалися з графами, наведіть приклади?

Учитель наводить кілька прикладів. Вам добре відомо поняття «родовідне дерево» і ви можете зобразити  в такій формі ваші родинні  стосунки. Каталог файлів на диску, також як і бібліотечний каталог - приклади інформаційних моделей  у формі дерева.

IV етап. Заповнення схеми. Застосування графа. (3хв)

V етап. Застосування знань і закріплення вивченого. (15 хв)

Розглянемо одну з найпростіших задач: «Червоний, синій, жовтий і зелений  олівці лежать у чотирьох коробках по одному. Колір олівця відрізняється  від кольору коробки. Відомо, що зелений  олівець лежить у синій коробці, а червоний не лежить у жовтій. У  якій коробці лежить кожен олівець? » [21, c.75].

Позначимо точками олівці і коробки. Суцільна лінія буде означати, що олівець лежить у відповідній  коробці, а пунктирна, що не лежить. Тоді з урахуванням завдання маємо  граф (1).

Далі добудовуємо граф за наступним  правилом: оскільки в кожній коробці  може лежати рівно один олівець, то з кожної точки повинні виходити тільки одна суцільна лінія і три  пунктирні. Отримуємо  граф (2), який дає  розв'язок задачі.

 

 

 

 

 

 

1.                           (2)

Задача 1. Оксана вирішила мамі на день народження подарувати букет квітів (троянди, тюльпани або гвоздики) і поставити їх або у вазу або в глечик. Скількома способами це можна зробити [27, c.96]?

Розв′язання: Відзначимо точками квіти та посудини (T,Т,Г,Г,В) (вершини графа). А зв'язки між ними – лініями між точками (ребра графа). За малюнком видно, що таких способів – 6.

Задача 2. Рано вранці Міша, Маша, Арсен обмінялися привітаннями один з одним. Скільки всього було вітань? Вирішити завдання за допомогою графа. Намалюйте граф в робочому зошиті.

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

А з В, Г, Е Г  з А, Д, Е

Б з В, Д, Е Д  з Б, Г, Е

В с А, Б Е  з А, Б, Г, Д

Скільки матчів зіграно і  скільки залишилося зіграти?

Задача 4.  Миколка вранці зібрався в школу, але по дорозі він повинен зайти в аптеку за ліками. Скількома способами він може це зробити?

Задача 5. Андрій, Борис, Віктор та Григорій після повернення з спортивного табору подарували на пам'ять один одному свої фотографії. Причому кожен хлопчик подарував кожному зі своїх друзів по одній фотографії. Скільки всього фотографій було подаровано [12, c.55].

Розв′язання: I спосіб. За допомогою стрілок на ребрах повного графа з вершинами А, Б, В і Г показаний процес обміну фотографіями. Очевидно, стрілок в 2 рази більше, ніж ребер, тобто 6 * 2 = 12. Стільки ж було подаровано і фотографій.

 

 

 

II спосіб. Кожен з чотирьох хлопчиків подарував друзям 3 фотографії, отже, всього було роздано 3 • 4 = 12 фотографій.

Відповідь: 12 фотографій.

VI етап. Домашнє завдання: Доповнити схему прикладами застосування графів. (1 хв)

VII етап. Підсумок уроку. Виставлення оцінок. (1 хв)

 

 

ВИСНОВКИ

 

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

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

Родоначальником теорії графів прийнято вважати Леонарда Ейлера, який у 1736 році розв’язавши життєву  задачу про Кенігсберзькі мости, встановив  властивості зв’язаного графа та зробив деякі загальні висновки.