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

                      Задача № 1.1

                      Розмовляють троє друзів: Білокуров, Чорнов і Рудов. Брюнет сказав Білокурову: «От що цікаво, що один з нас білявий, інший брюнет, третій рудий, але у жодного колір волосся не відповідає прізвищу». Якого кольору волосся у кожного з трьох друзів?

                            Розв’язання. Побудуємо граф відношення, заданого в умові задачі. Для цього перш за все, виділимо множину прізвищ М і множину кольорів волосся К, елементи яких позначимо точками. Точки множини М назвемо буквами Б, Ч і Р ( Білокуров, Чорнов і Рудов ); точки другої множини – б, бр, р (білявий, брюнет, рудий). Точці однієї множини відповідає точка з другого і їх можна об’єднати суцільною лінією, а якщо не відповідає – штриховою. Умова задачі вказує лише на невідповідності, тому спочатку має виникнути граф зображений на рис. 1.

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

Принцип розв’язання задачі простий. Якщо якась точка виявляється з’єднаною з двома точками другої множини штриховими лініями, то з третьою точкою її необхідно з’єднати  суцільною лінією. Саме тому граф на рис. 1 доповнюється суцільними лініями, що з’єднують точки Б і р, Р і бр (рис. 2). Далі залишається з’єднати  суцільною лінією точку Ч і точку б, так як точка Ч з’єднана з точкою бр штриховою лінією, а точка р вже «зайнята» (рис. 3).

Таким чином на графі цього рисунку автоматично можна прочитати відповідь: Білокуров – рудий, Чорнов – білявий, Рудов – брюнет. За таким же принципом можна розв’язати наступну задачу.

              Задача № 1.2

Для Вані, Колі і Михайлика спекли пироги: один з капустою, другий з пирогом, третій – з яблуками. Михайлик не любить пиріг з яблуками і не їсть з капустою. Іванко не любить пиріг з капустою. Хто який пиріг їсть?

Множину хлопчиків назвемо Х, а множину пирогів – П. Точки множини Х позначимо: Ваня – В, Коля – К, а Михайлик – М, точки множини П позначимо: пиріг з капустою – к, пиріг з рисом – р, а пиріг з яблуками – я. Виходячи з умови, за логікою попередньої задачі розв’язком до цієї є граф, який виглядає таким чином. З нього робимо висновок, що: Коля їсть пиріг з капустою, Ваня – з яблуками, Михайлик – з рисом.

Наведені задачі можна успішно розв’язати і за допомогою таблиць. Такий спосіб чи його модифікації рекомендуються і розбираються в багатьох науково-популярних книгах і педагогічних посібниках. Можна, проте, вказати класи задач, в яких застосування графів, зображених точками і відрізками, виявляється більш зручним і виправданим. Використання в розв’язках методу таблиць типу турнірних таблиць чи їх узагальнень змушує важливу частину міркування  проводити «усно». При цьому неодноразово приходиться повертатися до умови задачі, до проміжних результатів, багато чого пам’ятати і в потрібний момент користуватися отриманою інформацією. До такого типу задач відносяться задачі з трьома чи більшою кількістю множин розглянутих об’єктів.

Задача № 1.3

Три товариші – Іван, Дмитро і Степан – викладають різноманітні предмети (хімію, біологію і фізику) в школах Москви, Ленінграду і Києва. І відомо:

1.      Іван працює не в Москві, а Дмитро не в Ленінграді;

2.      Москвич викладає не фізику;

3.      Той, хто працює в Ленінграді, викладає хімію;

4.      Дмитро викладає не біологію.

Який предмет і в якому місті викладає кожен з товаришів?

Розв’язання. Виділяємо 3 множини: Множина імен, множина предметів і множина міст. Елемент кожної з множин на рис. 5 заданий своєю точкою (букви на малюнку – перші букви відповідних слів). Якщо дві різні множини характеризують ознаки різних людей, то з’єднуємо такі точки штриховою лінією. Якщо ж дві точки  з різних множин відповідають признакам однієї людини, то такі точки будемо з’єднувати суцільними лініями. Істотно, що за умовою задачі для кожної точки будь-якої множини в кожній з інших множин знайдеться одна і тільки одна точка, що їй відповідає. Таким чином, граф на рис. 5 містить всі задані в умові елементи множин і відношень між ними. Задача на мові графів зводиться до знаходження трьох «суцільних» трикутників з вершинами в різних множинах.

Розглянемо граф на рис. 5. Напрошується штриховий відрізок ХД. Дійсно, Л відповідає Х і одночасно, Л не відповідає Д, тобто Х не може відповідати Д. І так, використовується такого роду задач операція на графі: якщо у трикутника з вершинами в трьох різних множинах одна сторона суцільна, друга – штрихова, то третя повинна бути штриховою. З умови задачі слідує правомірність ще однієї операції на графі: якщо якась точка з’єднана штриховими відрізками з двома точками в другій множині, то її потрібно з’єднати з третьою точкою цієї множини суцільним відрізком. Так проводиться суцільний відрізок ДФ. Далі проводиться штриховий відрізок ДМ (в трикутнику ДФМ сторона ДФ суцільна, а ФМ – штрихова), ДК суцільним (ДМ і ДЛ штрихові). Тепер з’єднаємо точки Ф і К суцільним відрізком. Якщо у трикутнику з вершинами в різних множинах дві сторони суцільні, то третя також буде суцільною. Знайдений перший «суцільний» трикутник ДФК. Так не повертаючись до тексту задачі, керуючись лише очевидними на графі, що описаний вище, ми знаходимо розв’язок (рис. 6).

Відмітимо послідовність, в якій проводились відрізки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершини кожного з трьох отриманих «суцільних» трикутників визначають відповідь задачі: Іван викладає хімію в Ленінграді, Дмитро – фізику в Києві і Степан – біологію в Москві.

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

Задача № 1.4

              Маша, Ліда, Женя і Катя вміють грати на різних інструментах (віолончелі, роялі, гітарі і скрипці), але кожна тільки на одному. Вони ж володіють різними іноземними мовами (англійським, французьким, німецьким і іспанським), але кожна тільки одним. Відомо:

1.      Дівчина, яка грає на гітарі, говорить іспанською

2.      Ліда не грає ні на скрипці, ні на віолончелі і не знає англійської

3.      Маша не грає ні на скрипці, ні на віолончелі і не знає англійської

4.      Дівчина, яка говорить німецькою, не грає на віолончелі

5.      Женя знає французьку, але не грає на скрипці.

Хто на якому інструменті грає і яку іноземну мову знає?

Умові задачі відповідає граф, зображений на рис. 7. Позначення і принцип розв’язку тут такий же як і у задачі 3. Проведемо послідовно наступні суцільні відрізки: КС, ВЖ, ВФ, АК (рис. 8). Тим самим утворюється два суцільних трикутника ЖВФ і КСА. Проводимо ще суцільний відрізок РН. Тепер впевнюємось, що умови задачі не забезпечують однозначного вибору третьої точки для кожної з пар РН і ГИ. Можливі наступні варіанти «суцільних» трикутників: МГИ і ЛРН чи

ЛГИ і МРН. Таким чином, задача має два розв’язки.

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

Задача № 1.5

Чотири спортсменки Аня, Валя, Галя і Даша зайняли перші 4 місця в змаганнях по гімнастиці , при чому жодні дві з них не ділили між собою ці місця. На питання, яке місце зайняла кожна з них, троє з вболівальників виказали припущення:

1.      Аня – ІІ місце, Даша – ІІІ місце

2.      Аня – І місце, Валя – ІІ місце

3.      Галя - ІІ місце, Даша – ІV місце

Виявилось, що кожен вболівальник один раз помилився, а інший раз вказав правильно. Яке місце зайняла кожна з спортсменок?

Розв’язок.

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

Припустимо, наприклад, що Валя зайняла ІІ місце, тоді невірним має бути припущення: «Аня – ІІ місце», «Аня – І місце», «Галя - ІІ місце». Відрізки, що відповідають помилковому припущенню, будемо перекреслювати (рис. 10). У такому випадку Даша займе ІІІ і ІV місця, що за умовою задачі неможливо. Отже, припущення, що Валя зайняла ІІ місце, невірне; вірним буде висловлення «Аня зайняла І місце» (рис. 11). Ну тоді перекреслюємо відрізки АІІ і ВІІ, залишаючи ДІІІ. Далі закреслюємо відрізок ДІV. Отже: Аня зайняла І місце, Даша – ІІІ, Галя – ІІ, Валя – ІV.

2.2 Елементи теорії графів у задачах

Задача № 2.1. Чорні і білі

              На столі три однакових скриньки. В одній  лежать дві білі кульки, у другій – дві чорні, третій – біла та чорна. На скриньках є написи: «ББ», «ЧЧ», «БЧ», але жоден напис не є правильним. Яку найменшу кількість кульок треба взяти, щоб дізнатися, в якій скриньці лежать які кульки?

              Розв’язання. На рис. 12 зображено простір станів (відрізки показують можливі розміщення кульок у скриньках). Ясно, що в скриньці з написом БЧ знаходяться кульки одного кольору. Тому потрібно вийняти одну кульку з тієї урни. Можливі 2 варіанти: а) виймуть білу; б) виймуть чорну.

              Розглянемо кожний випадок окремо:

а) Якщо зі скриньки з написом БЧ дістали білу кульку, то в ній знаходяться білі кульки. Отже у скриньці з написом ЧЧ не можуть знаходитись дві білі кульки. Таким чином, там знаходяться чорна і біла кульки. Тоді очевидно, що у скриньці з написом ББ – дві чорних кульки (рис. 13 а). Випадок б) розглядається аналогічно (рис. 13.б). Відповідь: треба взяти 1 кульку зі скриньками з написом БЧ.

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

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

Будь-яку геометричну фігуру (відрізок, трикутник, чотирикутник і т. п.) можна вважати графом з числом вершин (степенем) рівним числу вершин фігури, і кількістю ребер, рівною числу відрізків, що з’єднують ці вершини (сторони, діагоналі). Наприклад, відрізок – це граф з двома вершинами і одним ребром, чотирикутник – це граф з чотирма вершинами і чотирма ребрами. А якщо в чотирикутнику провести діагональ, не відмічаючи точку їх перетину, то отримаємо граф з чотирма вершинами і шістьма ребрами. Якщо на колі намалюємо п’ять точок, також отримаємо граф з п’ятьма вершинами і п’ятьма ребрами. (рис. 14).

Задача № 2.2 Про знайомства

              У кімнаті 5 чоловік. Доведіть, що принаймні двоє з них мають однакове число знайомих серед даних п’яти. Знайомство – «симетричне» відношення, тобто якщо Вася знайомий з Іваном, то й Іван знайомий з Васею.

              Поставимо у відповідність кожній людині, що знаходиться в кімнаті, вершину графа. А ребра відображатимуть знайомства. Для розв’язання задачі досить довести, що принаймні з двох вершин у графі вийде одне й те саме число ребер. Число знайомих у будь-кого з присутніх може бути 0,1,2,3,4. Однак, якщо є людина з нульовим числом знайомств, то немає людини з числом знайомств рівним чотирьом, і навпаки (рис. 15). Тому розглянемо 2 випадки:

1) У кімнаті є людина з чотирма знайомими (отже, в кімнаті немає людини, яка немає знайомих серед даних п’яти (рис. 15а).)

2) У кімнаті є людина, яка не має знайомих серед даних п’яти (рис. 15б).

У першому випадку кожен з присутніх у кімнаті може мати число знайомств рівне 1,2,3 або 4, оскільки присутніх п’ять. Отже принаймні двоє мають однакове число знайомих. Що й треба було довести.

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

Задача № 2.3 Про парні числа

Один цар видав указ: «У державі повинно бути непарне число міст, а з кожного міста має виходити непарне число доріг» (кожна дорога з’єднує 2 міста). Днями й ночами працювали архітектори над планом будівництва, але нічого у них не виходило. З’ясувати чи можна виконати наказ царя. Відповідь обгрунтувати.

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

              Розв’язання. Розглянемо загальний випадок. Припустимо, що указ вдалося виконати. Поставимо у відповідність кожному місту вершину графа, а кожній дорозі – ребро графа. Очевидно, що в такому графі кількість вершин непарна і кожна вершина непарна, оскільки з кожного міста вийде непарне число доріг. Позначимо через k – кількість міст у державі, а степені вершин - n1, n2, n3,…,nk, де k та всі nі – непарні числа. Загальне число ребер у графі (доріг у державі). N дорівнює сумі степенів усіх вершин графа, поділеної на два (кожна дорога підраховується двічі). Тому  - n1 + n2 + n3 + nk = N*2. А це можливо лише в тому випадку, коли кількість непарних складових nі – парна, тобто k (кількість міст) – парна. Отримали суперечність. Отже неможливо побудувати граф з непарною кількістю непарних вершин і неможливо побудувати державу, описану в царському указі. У ході розв’язання задачі № 2.3 були отримані твердження.

1.      У графі сума степенів усіх його вершин число парне і дорівнює подвоєному числу ребер графа.

2.      Число непарних вершин будь-якого графа – парне.

2.3 Задачі на використання дерев

Задача № 2.4. Хуліганські витівки.

Бешкетники Вася, Петрик розірвали стінгазету, причому Петрик рвав кожний шматок на 3 частини, а Вася - на 5. При спробі зібрати стінгазету знайшли 1998 обривків. З’ясуйте  чи всі обривки зібрані?

Розв’язання. Нехай Петрик узяв шматок газети. Вийшло три нових шматки (загальне число шматків збільшилося на 2 – інваріант його дій) (рис. 16а). Дії Васі мають варіант – 4; бере шматок газети, а повертає 5 (рис. 16б). Беручи частину газети (неважливо, хто починає), і Вася, і Петрик збільшують число її шматків на парну кількість, тому унаслідок усіх дій може вийти лише непарне число частин газети. Отже газета була зібрана неповністю.