Розробка для факультативного або самостійного вивчення теми "Теорія графів" учнями 8-11 класів, страница 3

З сказаного зрозуміло, що схема району повинна бути уточнена: необхідно указати не тільки відстань від вершини А до вершини В, але й зворотну відстань. Для цього прийдеться ребро, яке йде від А до В, відокремлювати від ребра, яке йде від В до А. Робиться це за допомогою стрілки. Ребро, позначене стрілкою, називається орієнтованим (мал. 11).

мал.11

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

Повернемось до проблеми розв’язку задачі методом первинного переліку всіх можливих варіантів. Метод здається дуже простим, тим більше, що граф-дерево допомагає проводить перелік організовано. Але ця простота хибна, оскільки число маршрутів, дорівнює (К – 1)! Дуже швидко ростуть по мірі збільшення кількості вершин графа. Так 5 ! = 120, а вже 10 ! = 3628800. Співставити й оцінити таку масу маршрутів важко навіть за допомогою комп’ютера.

І все ж таки перелік маршрутів іноді буває по різному. Вдалось зробити метод розв’язку задачі, у відповідності з яких крок за кроком будується не повне, а усічене граф-дерево – частина гілок у ході його “вирощування” відсікається, а гілки, які залишились, ведуть до розв’язку. Цей метод називається методом гілок і кордонів.

Нехай граф, на якому відшукується найкоротший гамільтоновий маршрут наведено в додатку 1.

Ще раз підкреслимо, що задача про розсильного, якщо розуміти її у самому загальному вигляді, перетворилась у  задачі “на графі”: дана деяка граф-схема, й на ній необхідно знайти потрібний шлях. Постановка задачі вимагає застосування графа і, що саме цікаве, розв’язок її вимагає використання графа – один з кращих способів розв’язку, який будується на застосуванні графа типу дерево.

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

На завершення проведемо знайдену достатню умову існування гамільтованого шляху на графі.

Якщо ступінь кожної вершини (число ребер, виходячи з неї) графа, який має n вершин (n ³ 3), не менше: n/2, то на цьому графі можна побудувати гамільтонову лінію.

Це формально  проголошене утвердження можна переказати так: якщо у групі з n чоловік (n ³ 3) кожен має, у крайньому випадку: n/2 знайомих, то всю групу можна посадити навколо стола таким чином, що кожен з них буде знайомий з двома сусідами по столу.

Ця умова висуває вимоги, які у ряді випадків можна послабити. На мал. 13 приведені два графа; один (куб) має 8 вершин; ступінь кожної вершини дорівнює трьом, другої (решітка призми) – 10 вершин, частина яких має ступінь 2, а частина – 3 (не виконується вимога про ступінь кожної вершини графа: 2 £ 5 й 3 £ 5).

мал.13

Відмітимо, що необхідна умова існування гамільтонового шляху на графі таки не знайдено.

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

Як вірно розподілити обов’язки між членами бригади ? Як знайти кращий варіант укомплектування експедиції фахівцями ? Як призначити виконавців на ролі  у новій п’єсі ?

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

У складі експедиції повинно бути 6 фахівців: біолог, лікар, синоптик, гідролог, механік, радист.

Маємо 8 кандидатів, з яких і треба обрати 6 учасників експедиції. Умовні імена претендентів: А, В, С, Д, Е, F, G й Н. Обов’язки біолога можуть виконувати Е й G, лікаря – А й Д, синоптика F й G, гідролога В й F, радиста  - С й Д, механіка – С й Н. Передбачено, що в експедиції кожен з них буде виконувати тільки один обов’язок.

Кого і в якій посаді слід включити в експедицію, якщо F не може їхати без В, Д – без Н й без С, С не може їхати з G, А – разом з  В ?

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

Пристосована до задачі про експедицію одна група вершин є група з 8 кандидатів (А) й інша – з 6 посад (В).

Розв’язок задачі зображений на парному графі (мал. 14).

 

мал.14

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

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

Приведемо приклад.

На фестивалі зустрілись 6 делегатів. З’ясувалось, що з  будь-яких трьох в кратному випадку два можуть розмовляти на одній з мов.

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

Припустимо, що делегати А й В можуть розмовляти між собою (На мал. 15 відображений цей момент міркувань).

 

мал.15

Далі розглядаємо трійки, в яких можуть входить А й В; це такі трійки: АВF, АВС, ABD, АВЕ.

Зупинимось на трійці АВС. Вершину С з’єднаємо з вершинами А й В штрих-пунктирними ребрами. Це значить, що в цій трійці тільки А й В можуть розмовляти між собою.

Міркуємо аналогічно, ребра (А, Д), (В, Д), (А, Е), (В, Е), (А, F), (В, F) також зображуємо штрих-пунктирними й отримуємо граф, зображений на мал. 16.

 

мал.16

Розглянемо тепер трійки, в які входять вершина А й не входить  вершина В, наприклад, трійку АFС. У ній ребро (F, С) необхідно зобразити жирною лінією (інакше вийде, що в цій трійці немає двох делегатів, які можуть розмовляти між собою). Так само міркуючи відносно вершини В, приходимо до необхідності зображати жирною лінією ребра (Е, D), (D, C), (F, E), (E, C), (F, D). Граф після цього стає таким, як зображено на мал. 17

 

мал.17

Знаходимо, що у цьому випадку знайшлись не одна, а три трійки делегатів, які можуть вільно спілкуватись між собою. Це – ЕFС, ЕFD, DFC.

Висновки

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

                Матеріал  даної  роботи  може  бути  використаний  учнями  середньої  школи   з  метою  самостійного  навчання . Розв‘язані  задачі  можна  використовувати  при  проведенні  уроків  у  8 – 11  класах .

Перелік  використаної  літератури

1.  В . Н . Боровик , Л . Н . Вывальнюк , М . М . Мурач ,

В . И . Пономаренко , И . Ф . Тесленко . Математика . Пособие  для  факультативных  занятий   в  8  классе . – К . : Радянська  школа , 1981 г . , с . 158 – 164 .

2.  Касаткин  В . Н . Необычные  задачи  математики . – К : Радянська  школа , 1987 г . , с .50 – 71 .

3.  Р. Уилсон. Введение в теорию графов. – М. : Мир, 1977г. , с. 9 – 34.

Додаток 1

* Оцінка – сума довжин доріг ведучих

    в дану вершину.