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

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

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

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

 

ПОШУК:   

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

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

РЕФЕРАТ

 

на тему:

 

“Задачі, які приводять

 

до поняття графа”

 

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

 

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

граф.

 

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

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

 

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

 

Задача 1:

 

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

 

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

 

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

 

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

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

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

 

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

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

 

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

 

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

 

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

 

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

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

 

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

 

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

 

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

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

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

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

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

 

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

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

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

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

 

розташування мостів.

 

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

 

 

 

 

 

 

 

 

 

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

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

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

 

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

 

 

 

 

 

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

 

 

 

 

 

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

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

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

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

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

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

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

 

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

 

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

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

 

3. Основні теореми теорії графів

 

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

створена зусиллями математиків, тому її виклад містить у собі і

необхідні строгі визначення. Отже, приступимо до організованого введення

-----> Page:

0 [1]

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