Теорія графів
Автор: oljakyzja • Август 4, 2023 • Курсовая работа • 3,976 Слов (16 Страниц) • 112 Просмотры
Зміст
ВСТУП 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 – кінцевими чи термінальними вершинами маршруту.
...