розборі даного завдання корисно записати спочатку поняття неповного і повного графа. Графи, в яких побудовані не всі можливі ребра називаються неповними. Якщо ж у графі для будь-якої вершини знайдеться ребро, що з'єднує цю вершину з усіма іншими, відмінними від даної, то такий граф вважається повним. Якщо дану задачу переформулювати в рівносильну на мові графів, то потрібно дізнатися число ребер в повному графі з 5 вершин.
Завдання 2. У Петі є 2 автомобіля, 4 олов'яних солдатика і 2 м'ячі. Він хоче подарувати набір з трьох різних іграшок своєму другові на день народження. Виявилося, вибрати не так вже просто, занадто багато виходить варіантів, тим більше що всі м'ячі, солдатики і машини такі несхожі. Скільки наборів міг скласти Петя?
Рішення. Позначимо автомобілі, солдатиків і м'ячі буквами з індексами: А1, А2, С1, С2, С3, С4, М1, М2. Побудуємо граф - дерево. Точка Н - початок, від якої виставляємо один з варіантів А1 і А2. Від точки А1 можна вибрати вже 4 варіанти солдатиків і так далі.
рис. 2.3.3.2
Рухаючись від початку по відрізках вниз отримаємо 16 варіантів (рис. 2.3.3.2)
Відповідь: 16 наборів.
2.3.4 Текстові завдання
Завдання 1. Петя приніс на базар кошик яблук. I покупцеві він продав половину всіх яблук і ще 1 яблуко, II - половину залишку і ще 1 яблуко, III - половину нового залишку і ще 1 яблуко і т.д. Останньому - шостому покупцеві вона також продав половину залишилися яблук і ще 1 яблуко, причому виявилося, що він продав всі свої яблука. Скільки яблук приніс для продажу Петя?
Рішення. Складемо граф (ріс.2.3.4.1а)
ріс.2.3.4.1а
Вирішуючи, дії робимо назад (ріс.2.3.4.1б)
ріс.2.3.4.1б
Відповідь: 126 яблук.
2.3.5 Завдання про знаходження найкоротшого шляху в графі
Широко поширені задачі знаходження найкоротшого шляху. У таких завданнях задається граф (мережа доріг) і початкова вершина (пункт відправлення). Кожному ребру можна привласнити вага - довжина дороги.
Завдання 1. Дана карта доріг між містами, де вказана довжина кожної дороги (дані не збігаються зі справжніми). Знайти: а) всі найкоротші шляхи з Санкт-Петербурга до Омська; б) всі найкоротші шляхи з Санкт-Петербурга до Магнітогорська (ріс.2.3.5.1).
ріс.2.3.5.1
За даним графу можна розглянути всі можливі варіанти шляху від Санкт-Петербурга до Омська, але таких варіантів за правилом твори виходить дуже багато. Тому зручніше скористатися спеціальними програмами, наприклад, в результаті роботи програми Maple V, отримуємо, що найкоротша відстань від Санкт-Петербурга до Омська одно 490.
. 3.6 Лабіринти
Розглянемо задачу про пошук виходу з лабіринту, коридори якого не обов'язково знаходяться на одному рівні. Подібна ситуація виникає, наприклад, при блуканні в печерах або катакомбах. На малюнку 2.3.6.1 зображений цікавий приклад лабіринту:
ріс.2.3.6.1
Побудуємо відповідний йому граф (ріс.2.3.6.2). Коридори лабіринту - це ребра графа, а перехрестя, тупики, входи і виходи - це вершини.
ріс.2.3.6.2
Тепер добре видно, що в центр лабіринту можна потрапити, слідуючи за наступними вершин: 1 - 4 - 7 - 10 - 9 - 11 - 12 - 13. І, відповідно, вийти з центру лабіринту за маршрутом:13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.
Відповідь: 13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.
Походження завдань про лабіринти відноситься до глибокої старовини. Розв'язання задачі про лабіринтах предпосилаю історичні довідки - щоб показати інтерес до цього завдання і дати наочне уявлення про існуючих і існуючих лабіринтах. Завдання про проходження лабіринту набуває практичний інтерес, оскільки пристрій ліній електропередач, каналізації, мереж доріг, каналів і т.д.- Все це більш-менш складні лабіринти.
Учні знайомляться з геометричною постановкою завдання про лабіринти; вирішують загальну задачу, виконують пошукові завдання.
Намалювавши відповідний лабіринту граф, використовують спосіб обходу всіх ребер для знаходження виходу [4, 5, 11,12,13,15].
Завдання для факультативних занять в рамках чинної навчальної програми з математики [23] можна брати в діючих підручниках математики [20].
ВИСНОВОК
Т...
