Застосування теорії графів

Ніяка  Т.В.

IV курc, напрям підготовки: математика

 

ДЕЯКІ ПРАКТИЧНІ  ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ

 

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

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

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

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

Наведемо кілька прикладів  задач, які використовуються в школах на уроках математики.

Умовно їх можна класифікувати, поділивши на кілька груп: 
1. Задачі про мости. 
2. Логічні задачі. 
3. Задачі про "правильне" розфарбовування карт.

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

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

Задача. З трьох осіб, що стоять поруч, один завжди говорить правду (правдолюб), інший завжди бреше (брехун), а третій, залежно від обставин, говорить або правду, або брехню (дипломат). У  того, що стояв зліва, запитали: "Хто стоїть поруч з тобою? ". Він відповів:" Правдолюб ". Тому, що стояв у  центрі, задали питання: "Хто ти?", і він відповів: "Я дипломат". І коли у того, що стоїть праворуч, запитали: "Хто стоїть поруч з тобою?", він сказав: "Брехун". Хто де стояв?

Розв’язання. Якщо в даній задачі ребро графа буде відповідати місцю, 
займаному тією або іншою людиною, то нам можна розглянути наступні 
можливості (рис.1а, 1б).

Рис. 1а                                                     Рис. 1б

 

 

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

Отже, ця розстановка не задовольняє  умову задачі. Розглянувши 
таким чином всі інші можливості, ми прийдемо до висновку, що позиція 
"дипломат", "брехун", "правдолюб" задовольняє умову. Дійсно, якщо 
"правдолюб" стоїть праворуч, то з його відповіді, поруч з ним стоїть "брехун", що виконується. Той, що стоїть в центрі, заявляє, що він "дипломат", і 
отже, бреше (що можливо з умови), а  той, що стоїть праворуч, також бреше. 
Таким чином, всі умови задачі виконані.

Будь-яка географічна карта є багатокутним графом, в якому країни будуть гранями, межі - ребрами, а навколо країни «Світовий океан» - нескінченною гранню.

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

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

Оскільки теорія графів є  дуже актуальною, її широко застосовують не тільки у математиці, а й в  інших природничих науках – зокрема, у фізиці, хімії, географії, біології, картографії та в багатьох інших  науках. Діаграми графа подібно до геометричних рисунків дозволяють одержати наочне представлення до різного  роду задач. Графи дозволяють будувати математичну модель зв’язків між  заданими елементами. Наведемо приклади застосування теорії графів [1-3].

 

Графи та інформація.

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

Двійкові кодові дерева допускають інтерпретацію в рамках теорії 
пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який 
можна або "так", або "ні". Позитивним і негативним відповідям 
відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно (рис.2).

 

 

Рис. 2

 

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

 

Графи і хімія.

Ще А. Келі розглянув задачу про можливі структури насичених (або 
граничних) вуглеводнів, молекули яких задаються формулою: CnH2n⁺²  .

Всі атоми вуглеводню чотиривалентні, а всі атоми водню 
одновалентні. Структурна формула найпростішого вуглеводню показана на 
рис.3 ( метан CH4).

 

Рис. 3

Молекула кожного граничного вуглеводню являє собою дерево. Якщо видалити всі атоми водню, то ті атоми вуглеводню, що залишилися, також 
будуть утворювати дерево, кожна вершина якого має степінь не вище 4. Отже, число можливих структур граничних вуглеводнів, і т. д. число гомологів даної речовини, дорівнює кількості дерев з вершинами степеня не більше чотирьох. 
Таким чином, підрахунок числа гомологів граничних вуглеводнів також 
приводить до задачі на перерахування дерев певного типу. Цю задачу і 
її узагальнення розглянув Д. Пойа.

 

Графи і біологія.

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

Нас буде цікавити лише одне питання: у скількох випадках n-е 
покоління однієї бактерії налічує рівно k нащадків? Рекурентне 
співвідношення, що позначає число необхідних випадків, відомо в біології 
під назвою процесу Гальтона-Ватсона. Його можна розглядати як 
окремий випадок багатьох загальних формул.

 

Рис. 4

 

Графи і фізика.

Ще недавно однією з  найбільш складних і утомливих завдань  для 
радіоаматорів було конструювання друкованих схем.

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

В ході вирішення цього  завдання необхідно накреслити плоский граф з 
вершинами у зазначених точках ( рис.5).

 

Рис. 5

 

 

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

 

Анотація

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

Ключові слова: теорія графів, логічна задача, двійкові дерева, друкована схема.

 

Література

1. Оре О. "Графы и их применения". М.: "Мир", 1965.

2. Берж К. "Теория графов и ее применение". М.: ИЛ, 1962.

3. Касаткин В. Н. "Необычные задачи математики". Киев:"Радянська школа", 1987(часть 2).