close

Вход

Забыли?

вход по аккаунту

?

код для вставки
Довгинцівський район
КЗШ №90
ГРАФИ
для учнів 11 класу
Розробка занять з теми:
Мета:
ознайомити з історією виникнення графів, дати основні означення та
теореми та показати практичну цінність теорії графів.
ВСТУП……………………………………………………………………………… 3
2
1 Основні поняття теорії графів
1.1. Задачі, що приводять до поняття графів………………………………. 4
1.2. Означення теорії графів………………………………………………… 6
2. Застосування теорії графів до розв’язування задач
2.1 Застосування графів до розв’язування математичних
логічних задач………………………………………………………………… 12
2.2. Пошук найкоротших шляхів на графі.
Алгоритм Дейкстри……………………………………………………… 15
2.3. Задачі з графами з використанням ідеї парності і унікурсальності…19
3. Теорія Рамсея………………………………………………………………….21
4 Розв’язування системи рівняння………………………………………….22
5. Задачі для самостійного розв’язування……………………………………27
Висновки…………………………………………………………………………..28
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ…………………29
3
ВСТУП
Спробуйте намалювати «заклеєний конверт» не відриваючи ручки від паперу і
не проводячи двічі один і той самий відрізок. Такого роду питання ще з давніх-давен
цікавили математиків. Часто математичні поняття виникали з необхідності. Теорія
графів в основному була пов’язана з математичними розвагами і головоломками,
тому була спочатку незначним розділом математики. Декілька століть тому
математиків, які досліджували дану проблему, називали диваками і мрійниками.
Проте подальший розвиток математики і особливо її напрямків дав сильний
поштовх до розвитку теорії графів. Сьогодні сучасні досягнення теорії графів
використовуються у різних галузях знань, що підтверджує наукову та практичну
значущість цієї проблеми.
Багато задач прикладного характеру зводяться до розгляду сукупності об’єктів,
властивості яких описуються зв’язками між ними. В таких випадках зручно дані
об’єкти відображати точками, а зв’язки між ними – відрізками прямої чи кривої з
кінцями в даних точках. При цьому довжини відрізків і розміщення точок можуть
бути довільними.
Перша робота по теорії графів з’явилась в 1736 році. Вона належала відомому
швейцарському математику Л.Ейлеру. В одному зі своїх листів він формулює і
пропонує розв’язок завдання про сім Кенігсборських мости. Ця задача згодом стала
однією
з
класичних
задач
теорії
графів.
Вже
в
XIX
столітті
графи
використовувалися при побудові схем електричних ланцюгів і молекулярних схем. З
іншого боку, ця теорія широко застосовується в різноманітних практичних
питаннях:
при
встановленні
різного
виду
відповідностей,
при
вирішенні
транспортних задач, задач про потоки в мережі нафтопроводів. Теорія графів тепер
застосовується і в таких областях, як економіка, психологія і біологія. Як окрема
математична дисципліна, теорія графів була вперше представлена в роботі
угорського математика Кеніга в 30-ті роки ХХ століття . Математичні розваги і
головоломки також залишаються частиною теорії графів, особливо якщо віднести до
них знамениту проблему чотирьох фарб, що інтригує математиків і до цього дня.
Граф, з формальної точки зору, можна розглядати як один із різновидів
4
алгебраїчної системи. Результати та методи алгебри широко використовуються в
теорії графів. За допомогою графів описуються взаємозв’язки між об’єктами,
процесами чи подіями. Граф – це досить чітка модель для вивчення окремих явищ
навколишньої дійсності.
1. Основні поняття теорії графів
1.1.Задачі, що приводять до поняття графів
Початок теорії графів пов’язують із такими задачами.
Задача 1. Про Кенігзберзькі мости.
У Кенігсберзі було два острови, з’єднаних сімома мостами з берегами річки
Прегель та один із одним Задача полягала в пошуку маршруту проходження всіх
чотирьох частин суші, який мав починатися на довільній з них,
закінчуватися на ній же та по одному разу проходити кожен міст. Проте всі спроби
знайти маршрут були невдалими. Розв’зок до цієї задачі запропонував Л.Ейлер.
Такого шляху не існує.
Задача 2. «Про три колодязі»
5
Три сусідки посперечалися і викопали кожна по колодязю. Вирішили прокласти
стежки до кожного колодязя, але таким чином, щоб не зустрічатися одна з одною.
Чи можна зробити так, щоб стежки не перетиналися?
Така задача має важливе практичне значення при побудові залізниць.
Відповідь на цю задачу запропонував математик Куратовський у 1930 році.
Задача 3. «Про чотири фарби»
Чи можна зафарбувати карту світу використовуючи лише 4 фарби так, щоб
жодні дві сусідні країни не зафарбовувались одним кольором. Допускається
зафарбовування одним кольором лише коли вони межують одна з одною лише
однією точкою. У 1976 році Аппель і Хейкі опублікували рішення задачі про чотири
фарби, яке базувалося на переборі варіантів за допомогою комп'ютера.
6
1.2.Означення теорії графів
Означення. Непорожня множина точок і відрізків, обидва кінці яких належать
заданій множині точок, називається графами.
Нехай V – не порожня множина, яку ми будемо називати множиною вершин.
V(2) - не впорядкована множина двох векторів.
Означення. Графом G називається пара множин таких (V, E), де E – довільна
підмножина множини V(2). Множину E називають множиною ребер графа G.
Як правило, ребра позначаються парами (u,v), де u і v – вершини з V (кінці
ребра). У цьому випадку говорять, що ребро (u,v) з’єднує вершини u і v.
Кажуть, що вершини u і v суміжні, якщо існує ребро (u,v), що належить E. В
противному випадку – несуміжні.
Вершина u і ребро е називають інцидентними, якщо u є кінцем е.
Означення. Два ребра називаються суміжними, якщо вони мають спільну
вершину.
Наприклад, (3,7), (7,9) – суміжні.
Означення. Степенем ρ(n) вершини u називається кількість інцидентних ребер.
Встановлено, що в будь-якому графі число вершин непарного степеня парне.
Вершина степеня 0 називається ізольованою, а вершина степеня 1 – кінцевою
(висячою) вершиною. Ребро, інцидентне кінцевій вершині, називається кінцевим.
Наприклад, на рис.1.1 вершини
графа зображені квадратами, а ребра
6
– лініями. Щоб розрізнити вершини
між собою, їх нумерують числами,
причому
нумерація
7
1
послідовна,
2
починаючи з 1 (без пропусків). Наш
граф містить 7 вершин, причому:
Вершина
7
–
4
3
ізольована,
вершини 6 і 2 – висячі, вершини 1 та
5 мають степінь 3, вершина 4 –
5
Рис. 1.1 Зображення графа
7
степінь 2,вершина 3 – степінь 4.
Типи графів.
Графи, які містять скінченне число вершин та ребер, називаються скінченними.
Графи, в яких допускаються кратні ребра, називаються мультографами.
Псевдограф – мультограф, який має петлі (тобто ребра, що з’єднують вершину
саму з соою)
Граф без петель та кратних ребер, називають простим або звичайним.
Граф називається повним, якщо будь-які дві його вершини суміжні.
Граф називається регулярним або однорідним, якщо всі його вершини мають
один і той же степінь.
Граф, всі вершини якого ізольовані, називається порожнім.
Граф називається двочастковим, якщо існує таке розбиття множини його
вершин на два класи, при якому кінці кожного ребра належать до різних класів.
Якщо в двочастковому графі будь-які дві вершини з різних класів суміжні, то такий
граф називається повним двочастковим графом. Позначається він Km,n , де m –
вершини, які належать одному класу, а n – другому.
Орієнтованим називається граф, якщо всі пари (u,v) – впорядковані.
6
6
7
7
1
1
2
2
4
4
3
3
5
Рис.1.2 Неорієнтований граф
5
в
Рис.1.3 Орієнтований граф
Якщо у деякого ребра початок та кінець співпадають, то такі ребра
8
називаються петлею. (рис.1.4). Ребра, що з’єднують одну і ту саму пару вершин,
називаються кратними (рис.1.5)
1
1
5
2
Рис.1.5 Кратні ребра
Рис.1.4 Петля
Кількість ребер у повному неорієнтованому простому графі з N вершинами
дорівнює
1
n(n  1) , а орієнтований граф має ребер удвічі більше, оскільки
2
переміщення по ребру дозволено тільки в одному напрямку.
На практиці такі системи майже не зустрічаються. Мають місце структури, в
яких кількість ребер значно менша вказаної величини. Такі графи називаються
розрідженими.
На практиці досить важливим є не тільки можливість переміщатися по ребру,
але й так звана «вартість» цього переміщення. Це може бути будь-яка величина: час
переміщення, довжина шляху та інші кількісні характеристики, яка називається
вагою ребра. Позначається вага ребра числом над ребром (рис.1.6)
6
2
7
1
12
1
15
2
18
4
3
7
5
5
Рис.1.6 Вага ребра
Запис такого графа містить не дві цифри, а три (початкова та кінцеві вершини
ребра та його вагу).
9
Способи подання графів
І спосіб – за допомогою малюнка (діаграмою графа)
ІІ спосіб – переліком вершин та ребер, які вони з’єднують.
Наприклад, граф на рис.1.1
V={1,2,3,4,5,6,7} перелік вершин
Е={(1,6), (1,3), (1.5), (2,3), (3,4), (3,5), (4,5)}
ІІІ спосіб – подання графів за допомогою матриць суміжності.
Матриця суміжності являє собою двовимірну таблицю розміром NxN, де N –
кількість вершин у графі. Кожен елемент цієї таблиці містить дані про суміжність
відповідних вершин:
-для незважених графів – рівний 0, якщо між вершинами ребро відсутнє, або 1,
якщо ребро існує;
-для зважених графів – містить вагу ребра, якщо воно існує, або 0 в інших
випадках.
Таблиця 1.1
10
Матриця суміжності до рис.1.1
1
2
3
4
5
6
7
1
0
0
1
0
1
1
0
2
0
0
1
0
0
0
0
3
1
1
0
1
1
0
0
4
0
0
1
0
1
0
0
5
1
0
1
1
0
0
0
6
1
0
0
0
0
0
0
7
0
0
0
0
0
0
0
Таблиця 1.2
Матриця суміжності до рис.1.6
1
2
3
4
5
6
7
1
0
0
12
0
1
2
0
2
0
0
15
0
0
0
0
3
12
15
0
18
5
0
0
4
0
0
18
0
7
0
0
5
1
0
5
7
0
0
0
6
2
0
0
0
0
0
0
7
0
0
0
0
0
0
0
Очевидно, що для неорієнтованих графів ця матриця симетрична відносно головної
діагоналі, а для орієнтованих не обов’язково. Матриця містить нулі на головній
діагоналі, якщо граф немає петель, не нулеві значення – якщо має.
11
Маршрути. Ланцюги.
Маршрутом (шляхом) у графі G називають послідовність вершин і ребер v1, е1,
v2, е2,… е к-1, vк така , що два сусідні ребра еі-1 та еі мають спільну вершину vі.
Маршрути у графах, які не мають крайніх ребер, позначають лише переліком
послідовності вершин. При цьому вершина v1 – називається початком шляху, і
вершина vк – кінцем шляху. Всі інші вершини – проміжні або внутрішні.
Число ребер маршруту називається довжиною цього маршруту.
Маршрут називається ланцюгом, якщо всі його ребра різні.
Простим ланцюгом, якщо всі його вершини різні.
Маршрут називається замкненим, якщо в нього співпадають початкова та
кінцева вершини.
Цикл – це шлях, який починається та закінчується в одній і тій самій вершині.
Якщо цикл проходить по всіх ребрах графа, його називають Ейлеровим циклом
(виник при розв’язанні задачі про Кенінгсберзькі мости). Якщо ж цикл проходить по
всіх вершинах графа, не обов’язково відвідуючи всі ребра, його називають
гемільтоновим циклом.
Граф, який немає циклів, називається ациклічним графом.
Граф називається зв’язним, якщо кожну пару вершин можна з’єднати принаймні
одним шляхом.
Граф називається унікурсальним, якщо його можна намалювати одним
розчерком олівця. Зв’язний граф являється
унікурсальним тоді і тільки тоді, коли
він містить не більше двох вершин непарної степені.
Шляхи графів
Шлях у графі – це послідовність ребер, по яких можна послідовно проходити.
Наприклад, рис.1.1 (1-5-3-2), (1-3-4-5)
У будь-якого шляху є поняття довжини шляху – кількість ребер в ньому (для
незваженого графа) або сума ваги ребер (для зваженого графа).
У незваженому графі найкоротший шлях – це шлях з найменшою кількістю
ребер в ньому. У зваженому графі найкоротшим є шлях з мінімальною сумарною
вагою ребер, незалежно від їхньої кількості.
12
2. Застосування теорії графів до розв’язування задач
2.1.Застосування до розв’язування логічних задач
При розв’язуванні логічних задач для систематизації
використовуються таблиці та графи.
даних
дуже
часто
Задача1. Три подружки Оля, Катя та Маша прийшли на свято в сукнях різного
кольору: одна – в білому, друга – в червоному, третя – в зеленому. Оля не в
червоному, Катя – не в червоному і не в зеленому. Скажіть в якій сукні кожна з
дівчаток?
Відповідь: Оля – зелена сукня, Катя – біла, Маша - червона.
Оля
біле
Катя
зелене
Маша
червоне
Задача 2. Володимир, Ігор та Сергій викладають математику, фізику і літературу.
13
Живуть вони в Києві, Львові та Одесі. Відомо, що Володимир живе не у Львові, Ігор
живе не в Одесі, одесит не фізик, Ігор не математик, Львів’янин викладає
літературу. Хто де живе та що викладає.
Відповідь: Ігор – фізик і проживає в Києві, Сергій – викладає літературу і живе
у Львові, Володимир – математик і проживає в Одесі.
математика
Володимир
Київ
фізика
Ігор
Львів
література
Сергій
Одеса
Задача 3. Іваненко, Петренко, Леоненко і Симоненко – 4 талановитих молодих
14
чоловіка. Один з них танцюрист, інший – художник, третій – співак, четвертий –
письменник. Про них відомо, що:
1)Иваненко і Леоненко сиділи в залі консерваторії тоді, коли співак виступав на
сцені.
2)Художник малював портрети Петренка і письменника.
3)Письменник написав біографічне оповідання про Симоненка і збирається
написати про Іваненка.
4)Іваненко ніколи не чув про Леоненка.
Хто чим займається?
Відповідь: Іваненко – художник, Петренко – співак, Леоненко – письменник,
Симоненко – танцюрист.
Іваненко
танцюрист
Петренко
художник
Леоненко
співак
Симоненко
письменник
15
2.2. Пошук найкоротших шляхів на графі. Алгоритм Дейкстри
Однією з найважливіших задач теорії графів є пошук найкоротших шляхів на
графі. Особливо це цікаво на зважених графах. В них може безпосередній перехід не
вигідним, ніж перехід через кілька інших вершин .
Наприклад, на рис.2.1
виберемо усі можливі варіанти
4
1
2
переходу з 1 в 4: 1-2-4; 1-3-4; 1-2-34.
Оцінюються
такі
15
переходи
11
3
відповідно числами: 7; 21; 21.
Найменшим (найкоротшим) є
3
шлях 1-2-4.
Існує два алгоритми пошуку
мінімальних
шляхів
на
6
4
Рис.2.1 Зважений граф
графі.
Названі вони на честь їх винахідників.
1.Алгоритм Дейкстри – пошук довжини найкоротших шляхів між заданою та
всіма іншими вершинами.
2. Алгоритм Флойда –Уоршалла – пошук довжини найкоротших шляхів між
усіма парами вершин графа.
Другий алгоритм використовують для невеликих графів (до 100 вершин)
Основою алгоритму Дейкстри є метод обходу графа пошуком у ширину. Метод
полягає в тому, що на кожному кроці виконується перехід до всіх суміжних вершин
з поточної вершини. Він нагадує метод «хвилі» по поверхні, оскільки виконується
поступовий перехід до всіх вершин, що можуть бути досяжними з даної вершини за
один крок від початкової, за два кроки, за три і т.д.
Алгоритм Дейкстри показує маршрут від
стартової вершини до кожної з інших вершин.
Задача 4.. Нехай задано граф. Знайдемо
найкоротший маршрут від даної вершини до
кожної з вершин і його довжину (Рис.2.2)
Рис.2.2 Заданий граф
16
Даний граф містить 5 вершин. Нехай потрібно знайти довжини всіх маршрутів
від вершини 2 до всіх вершин. Спочатку складемо матрицю довжин ребер.
Таблиця 2.1
Матриця довжин ребер
1
2
3
4
5
1
0
11
7
-
14
2
11
0
20
19
-
3
7
20
0
-
5
4
-
19
-
0
4
5
14
-
5
4
0
З даної таблиці сформуємо іншу таблицю 2.2 за таким принципом. У перший рядок
Х запишемо всі нулі, крім комірки 2 (від неї шукаємо маршрути). Одиницею будемо
помічати переглянуті вершини. В другий рядок У впишемо довжини ребер від
вершини (перенесемо другий рядок початкової таблиці). В третій рядок Z запишемо
всюди 2, крім стартової комірки (таблиця 2.2)
Таблиця 2.2
1
2
3
4
5
X
1
1
0
0
0
Y
11
0
18
19
25
Z
2
0
1
2
1
Знайдемо мінімальний елемент в рядку Y. Це число 11, яке знаходиться на
першому місці. Помітимо і рядку Х першу комірку 1. Тепер переглянемо всі відстані
від вершини 2 через вершину 1. Якщо знайдеться менша відстань замінимо на неї.
17
Отримаємо 20>11+[1;3]=11+7=18, 19>11+[1;4]=11+ - не беремо до уваги, >11+[1;5]=11+14=25. Значення зміниться в комірках Y3, Y5. Для них відповідно у
рядку Z ставимо 1. Отримаємо таблицю 2.3
Таблиця 2.3
1
2
3
4
5
X
1
1
1
0
0
Y
11
0
18
19
23
Z
2
0
1
2
3
Розглянемо найменше значення серед 0 рядка Х. Це буде 18, яке знаходиться на
3 місці. Позначимо 1 в рядку Х і перевіримо відстані, які залишились. Отримаємо
19>18+[3;4]=18+ - не розглядаємо, 25>18+[3;5]=18+5=23. Таблиця набуде вигляду
Таблиця 2.4
1
2
3
4
5
X
0
1
0
0
0
Y
11
0
20
19
-
Z
2
0
2
2
2
Продовжуючи виконувати аналогічні міркування, отримаємо кінцеву
таблицю 2.5
Таблиця 2.5
Кінцеві результати
1
2
3
4
5
X
1
1
1
1
1
Y
11
0
18
19
23
Z
2
0
1
2
4
18
Середній рядок таблиці показує найкоротші шляхи від вершини 2 до інших
вершин, а третій рядок – маршрути. Наприклад, відстань від вершини 2 до вершини
5 є число 23 через вершину 4.
"Лема про рукопотискання" У довільному графі кожне ребро інцидентне
рівно двом вершинам, тому до суми степенів вершин графа кожне ребро додає
двійку. Таким чином, справджується твердження, яке було встановлено Ейлером і є
історично першою теоремою теорії графів.
Теорема . Сума степенів вершин графа G = (V, E) дорівнює подвоєній кількості
його ребер. Цю теорему інколи називають "лемою про руко потискання". Вершини
графа подають людей, а ребра — рукопотискання, якими люди обмінялися при
зустрічі. Оскільки кожне рукостискання має дві діючи особи, число потиснутих рук
удвічі більше кількості рукопотискань. Але число потиснутих рук — це сума
степенів вершин графа, а кількість рукопотискань — це кількість ребер.
Висновок .1. Повний граф з n вершинами має n(n-1)/2 ребер.
. Висновок 2 У довільному графі сума степенів вершин парна.
Висновок 3. У будь-якому графі кількість вершин, степінь яких непарний,
парна.
Задача 5. В змаганнях з шахів по круговій системі, при якій кожний з учасників
зустрічається з кожним, приймали участь 7 школярів. Відомо, що Ваня зіграв 6
партій, Толя – 5 партій, Олексій і Дмитро –по три,Семен і Ілля – по 2партії, Євген –
одну. З ким зіграв Олексій?
Розв'язування:
Поставимо кожному гравцю в відповідність точку площини. Якщо два гравця
зустрічалися двічі, то відповідні точки з'єднаємо лінією- ребром графа. Таким
чином, побудуємо граф зустрічів гравців.
19
Нехай вершина 1відповідає , Івану вершина 2 –Толику , вершина 3 –Олексію,
вершина 4 –Дмитру, вершина 5 –Семену, вершина 6 –Іллі, вершина 7 – Євгену. Іван
провів 6 зустрічей, то степінь вершини 1 – 6( вона з'єднана з усіма вершинами
графу) Степінь вершини 2- 5. Із вершини 2 виходить 1 ребро, останні чотири –
проведені з вершмнм2 в вершини 3,4,5.6. Вершина 7 має степінь 1, ( Євген провів
одну зустріч) і з'єднана одним ребром з вершиною 1.Тепер вершини 3,4,5,6 мають
степінь 2. Тому одержуємо, що Олексій , який провів 3 зустрічі , зустрічався з
Іваном, Анатолієм і Дмитром.
2.3. Задачі з графами з використанням ідеї парності і унікурсальності.
Задача 6
В невеличкому лісі знаходиться заєць. Він вискакує з нори, бігає між деревами,
залишає сліди і ховається під деревом. Досвідчений охотник визначив, що між
двома деревами заєць пробігав не більше одного разу. Під яким деревом нора зайця і
де сховався заєць?
Розв'язування:
20
Будемо враховувати, що кожне дерево - вершина графу, а шлях зайця ребро.
Неважко помітити, що всі вершини, крім 6 і 9 мають парну степінь. Значить нора
зайця знаходиться під деревом з цифрою 6, а сам заєць під деревом з цифрою 9 або
навпаки. Задача має два розв’язки.
Задача 7
Якою повинна бути мінімальна довжина куска дроту, для того, щоб не ламаючи
його, а тільки перегинаючи, зробити каркас кубу з ребром 10см?
Розв'язування:
Кожна вершина графа куба має непарну степінь, а дріт не ламається, то граф треба
зробити унікурсальним додаванням ребер. Для цього треба 6 вершин непарної
степені з’єднати попарно трьома ребрами.
В новому графі буде 17 ребер. Значить, дріт повинен мати довжину, в крайньому
випадку 170 см.
Відповідь: 170см.
Задача 8.
Група, в складі якої Петро був у туристичній поїздки, складається з 15 чоловік.
Повернувшись з подорожі, Петро розповів, що кожен з учасників був раніш
знайомим рівно з п’ятьма іншими учасниками. Чи можливо це?
Розв'язування:
21
В даному графі 15 вершин і кожна має степінь 5. Тому кількість ребер
15 * 5 =75. Кожне ребро враховується двічі бо з’єднує дві вершини. Тому ребер
повинно бути 75 : 2 = 37,5, а це неможливо.
Відповідь: твердження Павла не вірно.
Задача 9.
В країні Диснейленд на озері 7 островів. Від кожного з них виходить 1, 3 або 5
мостів. Доведіть, що хоча б один міст веде на берег.
Розв'язування:
Будуємо граф, в якому острови – вершини, мости – ребра. Нехай на берег не
один міст не веде. Тоді всі вершини графа мають непарну степінь і сума їх теж
непарна. Але за лемою руко потискань сума повинна бути парною. Одержуємо
протиріччя. Значить, хоча б один міст повинен вести на берег.
3. Теорія Рамсея – розділ комбінаторики.. Теорія Рамсея вивчає задачі, які
схожі на наступні дві задачі:
ЗАДАЧА.
Побудуйте приклад кампанії з пяти чоловік, в якій нема трьох чоловік , які попарно
знайомі або попарно не знайомі ( тобто в любій трійці є два знайомих і два
незнайомих чоловіка.).
Розв'язування:
На рисунку точки позначають людей, червоні ребра — знайомства, а сині—
незнайомство.
Неважко зрозуміти, що в довільній трійці будуть обов'язково дві сусідні вершини
(червоне ребро) і дві несусідні вершини (синє ребро)
22
ЗАДАЧА.
Нехай є компанія з шести чоловік .Доведіть, що в цій компанії обов'язково
знайдуться три чоловіка, які будуть попарно знайомі друг з другом, або які будуть
попарно незнайомі друг с другом.
Розв'язування:
Позначимо людей в цій кампанії через 1,2,3.4.5.6 і розглянемо 1 чоловіка. Крім
нього є ще п’ять чоловік, значить, що1 буде знайомим з трьома, або не знайомим з
трьома.. Для визначенності будем вважати, що він знайомий з 2.3,4.. Тоді, можна
сказати якщо 2 і 3 будуть знайомі, то ми знайшли трійку попарно знайомих людей
(1−2−3), тому будемо вважати, що вони незнайомі.. Аналогічно можна сказати, що
пари (3−4) и (4−2) — вони повинні бути знайомими.. Звідси одержуємо, що у нас
знайшлась трійка (2−3−4), в якій всі попарно незнайомі. Доведено..
В загальному вигляді цю задачу можно сформулювати наступним чином:
ТЕОРЕМА РАМСЕЯ
Нехай дані натуральні числа n і m. Тоді існує таке достатньо велике число N, що в
любій компанії з N чоловік знайдеться група з n чоловік, ,які попарно знайомі, або
найдеться, група из m чоловік, ,які попарно знайомі..
Фрэнк Пламптон Рамсей довів, що повна неупорядкованість неможлива.
Кожна достатньо велика множина чисел, точок, або об'єктів обов'язково має високо
упорядковану структуру.
4. Розв’язування системи рівняння
23
Починаючи з 7 класу, в школі розв’язують системи лінійних рівнянь з двома
невідомими. На олімпіадах та різноманітних математичних конкурсах ми зустрічаємося із
системами лінійних рівнянь з трьома невідомими. В шкільній програмі розглядаються два
способи розв’язування систем: спосіб підстановки та спосіб додавання. Кожний з цих
способів змушує виконувати алгебраїчні обчислення, що бувають досить громіздкими.
Існує цікавий спосіб розв’язування систем рівнянь – спосіб графів. Щоб навчитися
розв’язувати системи рівнянь даним способом, потрібно знати кілька основних понять.
Вершина графа відповідає змінній, ребро, що виходить із вершини – коефіцієнту
при цій змінній. Кожна вершина характеризується змінною системи (х, у, тощо), а ребро
– числами а.b, с. Ребро можна будувати, якщо коефіцієнт при змінній відмінний від 0. В
протилежному випадку вершина є ізольованою.
Побудуємо модель лінійного рівняння або системи рівнянь. На Рис.2.3 подано
окремі приклади таких моделей. Щоб виключити якусь змінну на графі, потрібно
перетворити відповідну вершину у вершину з входом та виходом (каскадну)
Рис.2.3 Модель лінійного рівняння та системи рівнянь
24
На Рис.2.4 подано основні перетворення графів і відповідні алгебраїчні
перетворення рівнянь або систем :
Рис.2.4 Перетворення графів і відповідні алгебраїчні перетворення рівнянь або систем
а) два або кілька паралельних ребра можна замінити одним, яке дорівнює сумі
паралельних ребер (Рис.2.4 а);
б) два або кілька послідовних ребер можна замінити одним,
яке дорівнює
добутку послідовних ребер (Рис.2.4 б).
На Рис.2.4 в і 2.4 г показано перетворення послідовних ребер графа.
Щоб виразити одну змінну через інші, необхідно вершину, яка відповідає цій змінні
зробити входом. На Рис.2.5 показано як зміниться ребро при зміні входу.
Рис.2.5 Зміна ребра при зміні входу
Якщо вихід і вхід міняються місцями (Рис.2.5), то ребро на новому графі
виражається числом, оберненим значенню ребра на початковому.
При зміні входу ребра, яке виходить із того самого виходу, наприклад у,
25
дорівнює добутку числа, протилежного значенню ребра (-b), яке спочатку виходило
з цього виходу (Рис.2.6), і нового ребра, яке змінило напрям (Рис.2.5).
Ці висновки можна зробити, побудувавши графи, які відповідають рівнянням
Рис.2.6 Зміна декількох ребер при зміні входу
1
z b
z a
1) y  ax, x  ; 2) z  ax  by; x   y, y   x
a
a a
b b
Отже, за допомогою графа одну змінну можна виразити через інші, незалежно
від їх кількості.
Приклад 1. Розв'язати систему рівнянь
x  2 y  5
Розв’язок даної системи зображено на Рис.2.7

3x  5 y  26
а
б
в
Рис.2.7 Розв’язок до прикладу 1
Змінивши послідовно граф, що відповідає базовій системі, ми дістали граф
26
на Рис.2.7 б . Слідуючий граф отримали, змінивши послідовні та паралельні ребра
графа.
Розв’язання системи зводиться до розв’язання рівняння першого степеня з
однією змінною, яке відповідає графу на Рис.2.7 в
1
1
5   y   26;
3
3
1
26
y   5;
Щоб відшукати х, необхідно розв’язати рівняння, що відповідає
3
3
y 1
графу, поданому на Рис.2.7 б
5
1
21
x   1   26   7
3
3
3
Відповідь: (7;1)
3x  y  1
Розв’зок даної системи подано на Рис.2.8
3x  8 y  19
Приклад 2. 
а
б
в
Рис.2.8 Розв’язок до прикладу 2
Аналогічними міркування дійдемо до слідуючого лінійного рівняння
19  9 y  1;
9 y  18;
y2
Відповідь: (1;2)
1
1 2 1
x  2    1
3
3 3 3
Системи рівнянь можуть не мати розв’язків або мати нескінченну множину
27
розв’язків. Тоді розв’язок таких систем набуде такого вигляду
3x  y  8
Розв’язок зображено на Рис.2.10
6x  2 y  14
Приклад 3. 
Рис.2.10 Система розв’язків
немає
1
2
Легко помітити, що 8  14 - це неправильна числова рівність, тому система
розв’язків немає.
Приклад 4
 x  2 y  3z  6

Рис.2.11 ілюструє розв’язування системи 2x  3 y  z  4
3x  y  4 z  0

28
а
б
г
в
д
Рис.2.11 Схема розв’язку прикладу 5
До Рис.2.11 д
До Рис.2.11 г
0  22z  20  42;
22z  22;
z 1
x  11z  8  18;
x  11  8  18  1
1
2
3
2
1
2
1 3
2 2
До Рис.2.11 б y   x  z  6     3  2  3  1
Відповідь: (1;1;1)
5. Задачі для самостійного розв’язування
29
5.1. В шаховому турнірі по круговій системі брали участь 8 школярів. Відомо, що
Мишко і Петро зіграли по7 партій, Сашко – 5, Костя і Євген – по 4, Гриша і Віктор
по 4. З ким зіграв восьмий учасник Володимир, якщо Костя і Євген зіграли між
собою?
5.2. 11 школярів, які їхали на канікули, домовилися,що кожен з них пришле
листівку трьом з останніх. Чи може так статись, що кожен одержить листівку від
тих, кому написав сам?
5.3. В парку 9 озер. Кожне озеро з’єднано з іншими озерами не менше ніж трьома
каналами. Яка найменша кількість каналів може бути в парку?
5.4. Чи можливо на площині так накреслити 9 відрізків,щоб кожний перетинався
рівно з трьома іншими?
5.5. На яке найбільше число областей можуть розбити площину два трикутника?
5.6. Розв’язати систему рівнянь за допомогою графів:
x  y  2

3x  3 y  6
5.7.З якого найменшого числа кусків дроту можна зробити каркас кубу (товщина
всіх ребер повинна бути однаковою)?
5.8 На пришкільній ділянці ростуть: яблоня, тополь, береза, горобина, дуб, клен,
груша і сосна. Горобина вище груші, яблоня вище клена, дуб нище берези, але вище
сосни, сосна вище горобини, береза нище тополі ,а груша вище яблоні. Розташуйте
дерева від самого низького до самого високого..
5.9.З трьох чоловік, які стоять поруч, один говорить правду( правдолюб), другий
завжди бреше( брехун),, третій ,дивлячись на обставини, говорить то правду, то
бреше ( дипломат). У того, що стоїть зліва, спитали: « Хто стоїть поряд з тобою?»
Він відповів: « Правдолюб». У того, що стоїть в центрі задали питання: «Хто ти?», і
він відповів: «Я дипломат». Коли у того, що стоїть справа спитали: « Хто стоїть
поряд з тобою?», він відповів « Брехун». Хто де стояв?
ВИСНОВКИ
30
Теорія графів відноситься до дискретної математики. Дискретна математика є
теоретичної основою для побудови алгоритмів та написання комп’ютерних програм.
Сьогодні людська діяльність тісно пов’язана з комп’ютерною технікою та
комп’теризацію виробництва. Тому теорія графів на сьогодні є досить актуальною
темою. Особливістю теорії графів є геометричний підхід до вивчення об’єктів. Вони
дозволяють наочно зобразити розв’язування різноманітних задач.
Теорія графів застосовується не тільки в математиці, а й в інших природничих
науках, зокрема, у фізиці, хімії, географії, біології, картографії та в багатьох інших
науках. Так, наприклад, для побудови структурних формул хімічних елементів, для
складання найбільш вигідних транспортних маршрутів, при моделюванні складних
технологічних процесів, у програмуванні, в електротехніці – для конструювання
друкованих схем, а також при вивчені послідовного і паралельного з’єднання
провідників.
В своїй роботі ми висвітлили лише основні теоретичні поняття графів,
алгоритм Дейкстри та деякі практичні способи застосування графів: відшукання
найкоротших шляхів, розв’язання математичних головоломок,використання ідеї
парності і унікурсальності, розв’язання систем рівнянь за допомогою графів.
Вона є цікавою, актуальною і перспективною в наш час.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ
31
1. Берж К. Теорія графів і її застосування / К.Берж. — М.: МУЛ, 1962. — 345с.
2. Гарднер М. Математичні дозвілля / М.Гарнер. — М.: Світ, 1972. — 240с.
3. Зиков А. А. Теорія кінцевих графів / А.А.Зиков. — Новосибірськ: Наука,
1969. —
4. Касаткін В. Н. Незвичайні задачі математики / В.Н.Касаткін. — К.: Радянська
школа, 1987. —
5. Математика: Дит. енцикл. / Авт.-упоряд. А. П. Савін, В. В. Станцо, Г.
Ю. Котова; Худож.: О. В. Кардашук та ін. — К.: Школа, 2002. —
6. Олехнік С. Н. Стародавні цікаві задачі / С.Н.Олехнік, Ю.В.Нестеренко,
М.К.Потапов. — М.: Наука, 1988. —
7. Оре О. Графи і їх застосування / О.Оре. — М.: Світ, 1965. —
8. Реньє А. Трилогія про математика / А.Реньє. — М.: Світ , 1980. —
9. У світі математики: Зб. Наук.-попул. статей / Редкол.: М.Й. Ядренко (відп.
ред.) та ін. — К.: Рад. школа, 1980. —
10.Сарана О.А. Математичні олімпіади: просте і складне поруч: Навч.посібн.
/О.А.Сарана. — К.: Видавництво А.С.К., 2004. —
11.Циганівський М.С. Практикум з дискретної математики: навч.посібн. /
М.С.Циганівський, В.С.Щирба. — Кам’янець-Подільський, 2011. — 220с.
ІНТЕРНЕТ РЕСУРСИ
http://otherreferats.allbest.ru/mathematics/00254997_0.html
http://lib.exdat.com/docs/944/index-110594.htm
http://www.uabs.edu.ua/images/stories/docs/K_VM/Koibitchuk_006.pdf
http://freepapers.ru/24/grafi-ta-h-zastosuvannya/151112.940753.list1.html
http://bookscity.com.ua/cat5/name6256.html
Автор
sudarinya_324512
Документ
Категория
Образование
Просмотров
116
Размер файла
1 190 Кб
Теги
график
1/--страниц
Пожаловаться на содержимое документа