UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваОсновні поняття теорії графів (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2237
Скачало353
Опис
ЗАКАЧКА
Замовити оригінальну роботу

РЕФЕРАТ

 

на тему:

 

“ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ ГРАФІВ”

 

 

Теорія графів – дисципліна математична, створена зусиллями математиків,

тому її виклад включає в себе і необхідні чіткі визначення. Засновником

теорії графів прийнято вважати математика Леонарда Ейлера (1707-1782).

 

Поняття про графи

 

   Для вирішення багатьох задач, може бути застосоване таке поняття, як

граф.

 

Граф - це множина точок (вершин), які з’єднані між собою лініями, що

називаються дугами або ребрами.

 

Приведемо приклад задачі, яка може бути розв’язана, за допомогою графів.

 

Задача 1:

 

На вечірку запрошено шестеро людей, чи може бути така ситуація,

 

що кожен знав тільки двох запрошених.

 

Розв’язання:

 

Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх. Якщо двоє

знайомі, то з’єднаємо їх відрізком (ребром). Виявляється, що така

ситуація не тільки можлива, але й може описуватися декількома схемами.

 

Тобто можна сказати, що граф-це сукупність об’єктів, зв’язками між якими

служать ребра.

 

Приклади графів з декількома вершинами та ребрами.

 

На малюнку 4 показаний граф з чотирма вершинами та шістьма ребрами

 

На малюнку 5 зображено граф з п’ятьма вершинами та двома ребрами

 

 

мал.4                                       мал.5

 

Прикладами графів можуть слугувати схеми метрополітенів, схеми шосейних

чи залізничних доріг, карти, які показують зв’язки між окремими

об’єктами

 

Задача Ейлера – як яскравий приклад задачі,

 

яка приводить до поняття графів

 

Для рішення серйозних математичних задач математик Ейлер використовував

наочні головоломки. Одна з них поклала початок зовсім новій області

досліджень, що виросла згодом у самостійний розділ математики - теорію

графів і топологію. Особливість цієї теорії - у геометричному підході до

вивчення об'єктів.

 

Буваючи в Кенігсберзі, прогулюючи по його набережних, Ейлер звернув

увагу на оригінальне розташування семи мостів міста. Причиною цьому був

вигадливий течії рукавів Прегеля, з'єднаних протокою, що охоплюють з

півночі і півдня острів Кнайпхоф, а потім зливаються разом.

 

У підручниках зображується схема розташування мостів.

 

Приблизно ось така >>>

 

 

 

 

 

 

 

 

 

Витончена по своїй конкретності Задача семи мостів Кенігсберга була

сформульована Ейлером у 1759 р. у такий спосіб: "як пройти по семи

мостах, не проходячи по одному двічі".

 

накласти вершини і зв'язки на карту центра нашого міста >>>>>>

 

 

 

 

 

Цей же граф для числа "7" у чистому виді без "підкладки". >>>

 

 

 

 

 

 

 

У кожній мережі Ейлер підраховує зв’язки, що приходять у вершини. Якщо

число зв'язків непарне, таку вершину Ейлер називає «неправильною» або

«дивною». Вершина з парною кількістю зв'язків – «правильна» (у

першоджерелі – «мудра»). Як бачимо, усі вершини в нашій мережі

з'єднують 3 чи 5 зв'язків. Отже усі вони - неправильні. Виходить, так

званої безупинної «доріжки Ейлера», яка проходить через кожну вершину

тільки один раз для цього числа не існує.

 

А в якому випадку існує така «доріжка»?

 

Для рішення цієї задачі Ейлер створив і довів теорему: якщо мережа має

не більш двох «дивних» вершин, є принаймні один подібний шлях.

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ