Теорія графів

Зміст

ВСТУП        3

РОЗДІЛ. 1. ТЕОРЕТИЧНІ ЗАСАДИ ТЕОРІЇ ГРАФІВ        4

1.1. Основні поняття теорії графів        4

1.2. Визначення твірної функції та її властивості        9

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

2.1. Розв’язання задач перерахування кореневих дерев за допомогою         функцій        15

2.2. Прикладне застосування теорії графів у різних сферах життя суспільства та окремої особистості        19

2.3. Графи в математичній практиці роботи загальноосвітньої школи та напрями удосконалення їх застосування        22

ВИСНОВКИ        27

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ        28

ВСТУП

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

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

Таким чином, метою даної роботи є вивчення похідної функцій в теорії графів.

Об’єктом дослідження приймаємо безліч похідних функцій.

Предметом дослідження є функції у теорії графів.

Відповідно до мети дослідження, об’єкту та предмету, ставимо перед собою ряд завдань:

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

Методи дослідження: аналіз наукової літератури, порівняння.

Структура роботи: робота складається зі вступу, двох розділів, висновків, списку використаної літератури.

РОЗДІЛ. 1. ТЕОРЕТИЧНІ ЗАСАДИ ТЕОРІЇ ГРАФІВ

1.1. Основні поняття теорії графів

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

[pic 1]

Рис. 1.1. Приклад графа

Крапки P, Q, R, S, T – вершини графа. Лінії – ребра графа. Ступенем вершини називається число ребер, кінцем яких є ця вершина.

Два графи вважаються ізоморфними, якщо існує взаємно однозначна відповідність між їхніми вершинами, що має ту властивість, при якій дві вершини з’єднані ребром в одному графі тоді і тільки тоді, коли відповідні їм вершини з’єднані ребром в іншому графі [13, с. 29]. Граф на рис. 1.2 вважається ізоморфним графу на рис. 1.1.

[pic 2]

Рис. 1.2. Приклад графа

Ребра, що з’єднують Q з S і S з T на графі рис. 1.3, називаються кратними, ребро, що йде з P у P, називають петлею.

[pic 3]

Рис. 1.3. Приклад графа

Граф, що не містить кратних ребер та петель, називається простим.

Якщо на ребрах графа зазначено напрямок руху, то він називається орієнтованим або орграфом (рис. 1.4).

[pic 4]

Рис. 1.4. Приклад графа

Згідно з визначенням М. Свамі, маршрут у графі G = (V, E) являє собою кінцеву послідовність вершин і ребер vo, e1, v1, e2, ..., vk-1, ek, vk, що починається і закінчується на вершинах, причому vi- 1 і vi є кінцевими вершинами ребра ei, 1≤i≤k. З іншого боку, маршрут можна розглядати як кінцеву послідовність таких вершин v0, v1, v2, …, vk, що (vi-1, vi), 1≤i≤k, ребро графа G. Такий маршрут зазвичай називається v0-vk – маршрутом, а v0 та vk – кінцевими чи термінальними вершинами маршруту.