Реферати українською » Математика » Навчання рішенню математичних задач за допомогою графів


Реферат Навчання рішенню математичних задач за допомогою графів

>Е.А.Кудревич, А.Є.Поличка, кафедра математичного аналізу ХДПУ

Під час підготовки учнів до математичної олімпіаді часто зіштовхуєшся з проблемою- яких методів вирішення завдань приділити більше часу. Можна запропонувати, наприклад, такі критерії: щоб дітям цікаво було, щоб даним методом вирішувалося велике коло завдань, щоб було використовувати історичний матеріал тощо. п. Все це критеріям повною мірою задовольняє метод, заснований на застосуванні графів. Одне з авторів запропонованої читачам статті – декан фізико-математичного факультету ХДПУ Анатолій ЄгоровичПоличка кілька років викладає школярам і студентам елементи теорії графів та вчить їх застосовувати графи вирішення завдань. Понад те, він активно акцентовує на цьому справі своїх учнів – студентів ХДПУ.

Як і спорті, тренування юного математика вимагає витрати великого часу. Для успіху олімпіаді необхідні деякі спеціальні типи обдарованості.

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

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

Наголошую те що, що олімпіади перевіряють на відміну від іспитів кмітливість, а чи не виучку; тому найкраще – якщо школяр, не розраховуючи за свої знання, розвине всі свої здібності, у яких б грунтувалися "експромти".

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

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

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

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

По цієї проблеми розроблено такі класифікації:

За теорією використовуваної під час вирішення По способам рішення
1 Маршрути 1. Вони мають інші способи
2 Групи знайомства рішення:
3 Сила-силенна елементів а) Метод математичної ін-
4 Спортивні турніри >дукции
5 Вибір відповідності б) >Комбинаторние методи
6 Мости в) Метод складання таблиць
7 Найбільше і найменше 2. Не мають інших засобів
3.

>Требующие особливих прийомів

рішення

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

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

Наведемо приклади розв'язання окремих завдань.

>П.Т.З. 1. "Маршрути".

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

Д До

Є З

 М

 Про

 А F

У М

Рішення:

По схемою доріг видно, що подорож Чічіков почав із маєтку Є, а закінчив маєтком Про.Замечаем, що у маєтку У і З ведуть лише дві дороги, тому за цими дорогах Чічіков мав проїхати. Зазначимо їх масною лінією. Визначено ділянки маршруту, які відбуваються через А: АС і АВ. ШляхамиАЕ, АК іАМ Чічіков не їздив.Перечеркнем їх. Зазначимо жирною лінієюЕD ; перекреслимоDK .Перечеркнем МО іМН; відзначимо жирною лінієюMF; перекреслимоFO; відзначимо жирною лінієюFH, НК і КЗ. Знайдемо єдиний можливий при даному умови маршрут. Й отримуємо: маєток Є – належитьМанилову, D-Коробочке, З –Ноздреву, А –Собакевичу, У –Плюшкину, М –Тентетникову, F -Бетрищеву, М – Півню, До –Констанжолго, Про –Кошкареву.

Д До

Є З

М Про

 А F

У М

>П.Т.З. 2 "Групи, знайомства"

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

а передали парне число конвертів;

б) число учасників,обменявшихся конвертами парне число раз,четно.

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

А2

 А1 А3

 А4

>А7

А6А5

а) ступінь кожної вершиниАi показує число конвертів, який передав учасникАi своїх знайомих. Загальна кількість переданих конвертів N дорівнює сумі допомоги ступенів всіх вершин графа N = степ. А1 + степ. А2 + + . . . + степ.Аn-1 + степ.Аn ,N=2p, деp – число ребер графа, тобто. N – парне. Отже, передали парне число конвертів;

б) у рівності N = степ. А1 + степ. А2 + + . . . + степ.Аn-1 + степ.Аn сума непарних доданків мусить бутичетной, але це може лише у разі, якщо число непарних доданківчетно. І це означає, що кількість учасників,обменявшихся конвертами парне число раз, парне.

>П.Т.З. 3. "Безліч елементів"

Ліст папери Плюшкін розрізав на 3 частини. Деякі з отриманих аркушів він також розрізав втричі частини. Кілька нових листочків його знову розрізає втричі менші частини й т.д. Скільки Плюшкін отримує листків, якщо розрізаєk листків?

Рішення:Листки папери позначимо малюнку гуртками. Гуртки, відповідні листам, якіразрезаются, зафарбуємо повністю; інші гуртки залишимо не зафарбованими. малюнку видно, що з розрізуванні одного аркуша на 3 частини число листків поповнюється два. Якщо ж розрізаноk листків, то утворилося 1+2k аркушів.

>П.Т.З. 4 "Спортивні турніри".

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

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

Кожна вершина графа з9-тью вершинами може мати ступінь, рівну 0, 1, 2, 3, 4, 5, 6, 7, 8. Припустимо, що є граф, все вершини якої мають різну міру, тобто. кожна з чисел послідовності 0, 1, 2, 3, 4, 5, 6, 7, 8 є ступенем однієї й лише одній з його вершин. Але це може бути. Справді, тоді як графі є вершина ступеня 0, у ньому бракуватиме вершина зі ступенем 8, оскільки ця вершина мусить бути з'єднана із іншими вершинами графа зокрема і з тим, що має ступінь =0. Інакше висловлюючись, в графі з9-тью вершинами неможливо знайти одночасно вершини ступеня 0 і побачили 8-го. Отже знайдуться хоча б дві вершини, ступеня яких рівні між собою. Отримали, що у будь-яку час знайдуться хоча б двоє, котрі зіграли однакове число партій.

>П.Т.З. 5. "Вибір, відповідність".

Хто грає Тяпкіна-Ляпкіна. У шкільному драмгуртку вирішили ставити гоголівського «Ревізора». І тоді розгорівся пристрасна суперечка. Почалося все зЛяпкина-Тяпкина.

>Ляпкиним-Тяпкиним буду я! – рішуче заявив Гена.

Ні, я будуЛяпкиним-Тяпкиним, - заперечив Діма, - з дитинства мріяв втілити цей спосіб на сцені.

Ну, добре, згоден поступитися цією роллю, коли мені дадуть зіграти Хлестакова, - виявив великодушність Гена.

. . . а тут – Осипа, - не поступився то великодушність Діма.

Хочу бутиЗемляникой чиГородничим, - сказав Вова.

Ні,Городничим буду я, - хором закричали Алік і Боря. – Або Хлєстаковим, додали вони відразу.

Чи вдасться розподілити ролі те щоб виконавці були задоволені?

Рішення. Спробуємо побудувати граф для цій ситуації.Изобразим юних акторів гуртками верхнього низки: А –Алік, Б – Боря, У – Вова, Р – Гена, Д – Діма, а ролі, що вони збираються грати, - гуртками другого низки (1 – Ляпкін-Тяпкін, 2 – Хлєстаков, 3 – Осип, 4 – Суниця, 5 - Городничий). Відтак кожного учасника проведемо відтинки, тобто. ребра до ролей, що він хотілося б зіграти. В Україні вийде граф з десятьма вершинами і десятьма ребрами.

А Б У Р

 

Д

1 2 3 4 5

Аби розв'язати завдання, треба з десяти вибрати п'ять ребер, які мають загальних вершин. Зробити це легко. Досить зауважити, що у вершини 3 і 4 веде за одним ребру, з вершин Д і У відповідно. Це означає, що Осипа (вершина 3) має відігравати Діма, аЗемлянику – Вова. Вершина 1 – Ляпкін-Тяпкін з'єднана ребрами з Р і Д.Ребро 1 – Д відпадає, оскільки Діма вже зайнятий, залишається ребро 1 – Р,Ляпкина-Тяпкина має відігравати Гена. Залишається з'єднати вершини Проте й Б з вершинами 2 і п'яти, відповідним ролям Хлестакова і Городничого. Це можна зробити двома шляхами: або вибрати ребра А - 5 і Б – 2, або ребра А – 2 і Б – 5. У першому випадку Алік відіграватиме Городничого, а Боря – Хлестакова, у другий випадок – навпаки.

>П.Т.З. 6. "Мости".

Завдання проКенигсбергских мости. Місто Кенігсберг (нині Калінінград) розташований на берегах і двох островах річкиПрегель (>Преголи). Різні частини міста з'єднані сім'ю мостами, як показано малюнку. У неділі городяни гуляють містом. Чи можна вибрати такий маршрут, аби пережити сам і лише одне раз в кожному мосту до того ж повернутися до початкову точку шляху?

 З g

 зd

 D

 

 A e

>f

a b У

Рішення.

Означимо різні частини міста літерами А, У, З, D, а мости – літерами a, b, з,d, e,f, g. У цьому завданню істотні лише переходи через мости: переходячи через будь-який міст, ми завжди з частині міста потрапимо до іншої, і, навпаки, переходячи з частині міста, у іншу ми неодмінно пройдемо мостом. Тому зобразимо план міста, у вигляді графа, вершини якого зображують частини міста, а ребра – мости, що з'єднують відповідні частини міста.

З g

зd D

 A

a b

Bf

Якби існував маршрут, зрозумілу умові завдання, то існував б замкнутий і безперервний обхід цього графа, проходить одного разу в кожному ребру. Інакше кажучи, цей граф можна було б викреслити, не відриваючи олівця від папери, і не проходячи двічі за одним й тому ребру. Але це пояснити неможливо – хоч би вершину ми вибирали за вихідну, доведеться проходити через інші вершини, і навіть кожному «який був» ребру (мосту, яким ми увійшли до Поділ) відповідатиме що виходить ребро (міст, яких ми скористаємося потім, аби залишити Поділ): число ребер, які входять у кожну вершину, дорівнюватиме числу ребер які виходять із неї, тобто. загальна кількість ребер, збіжних у кожному вершині має бутичетним. Наш граф цій умові не задовольняє, і тому необхідного маршруту немає.

>П.Т.З. 7. "Найбільше і найменше число елементів".

Місто має у плані вид прямокутника, розбитого на клітини: n вулиць рівнобіжні одна одній,m інших перетинаються під прямим кутом. На вулицях міста – але не перехрестях – стоять міліціонери. Кожен міліціонер повідомляє номер який струменіє повз нього автомобіля, спрямування його руху, і час, що він проїхав. Яке найменше число міліціонерів потрібно розставити тут, щоб за їх показанням можна було однозначно відновити шлях будь-якого автомобіля, яка їде по замкненому маршруту (маршрут не відбувається за одному й тому ділянці вулиці двічі)?

Рішення:

Найменше міліціонерів одно (>m-1)(n-1).

Якщо міліціонери розставлено потрібним чином, то вся сітка вулиць розпадається на числоk шматків, які містять замкнутих маршрутів (циклів), - інакше знайдеться цикл, яким можна проїхати який був заміненим жодним міліціонером. Якщо що залишилося шматок сітки містить р перехресть у ньому міститься рівно р – 1 відрізків вулиць. Оскільки перехресть всьогоm n, то число відрізків, у яких немає міліціонерів, одноmn –k. Загальна кількість відрізків вулиць одно2mn –m – n. Отже, число зайнятих відрізків одно

>mn –m – n +k > (n –1)(n – 1).

Приклад потрібної розстановки (n –1)(n – 1) міліціонерів показаний малюнку


Схожі реферати:

Навігація