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

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

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

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

 

ПОШУК:   

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

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

Реферат на тему:

 

“Основні поняття теорії графів”

 

Вступ

 

Роком виникнення теорії графів одностайно вважається рік 1736, коли

Леонард Ейлер опублікував розв’язок так званої задачі про кенігсберзькі

мости, а також знайшов загальний критерій існування ейлерового циклу в

графі.

 

Отримання дальших суттєвих результатів у цій галузі датують серединою

ХIХ століття. Однак початок проведення активних систематичних досліджень

та становлення теорії графів як окремішного авторитетного розділу

сучасної математики відбулося ще майже 100 років по тому, тобто в

середині ХХ століття. Саме з цього часу граф стає однією з

найпоширеніших і найпопулярніших математичних моделей у багатьох сферах

науки і техніки. Картинка у вигляді набору точок на площині та ліній,

проведених між деякими з них, стала зручною і наочною формою зображення

найрізноманітніших об’єктів, процесів та явищ.

 

Великою мірою це пов’язано з виникненням, бурхливим розвитком та

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

зростанням ролі задач дискретного характеру. Математика від

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

методів у інші сфери людської діяльності. Одним з потужних інструментів

такого проникнення є граф.

 

Із суто формальної точки зору граф можна розглядати як один з різновидів

алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів (

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

використовуються в теорії графів. Однак за останні півстоліття активного

інтенсивного та екстенсивного розвитку теорія графів виробила свою

достатньо специфічну власну проблематику і методологію. На сьогодні

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

важливим розділом дискретної математики.

 

Поняття графа. Способи завдання графів

 

Нехай V ( деяка непорожня скінченна множина, а V (2) ( множина всіх

двохелементних підмножин (невпорядкованих пар різних елементів) множини

V.

 

Графом (неорієнтованим графом) G називається пара множин (V,E ), де E (

довільна підмножина множини V (2) (E ?V (2)); позначається G =(V,E ).

 

Елементи множини V називаються вершинами графа G, а елементи множини E (

ребрами графа G. Відповідно V називається множиною вершин і E ( множиною

ребер графа G.

 

Традиційно ребра {v,w} записуються за допомогою круглих дужок (v,w)

(іноді просто vw).

 

Граф, який складається з однієї вершини, називається тривіальним.

 

Оскільки для тривіального графа або так званих порожніх графів G =(V,()

переважну більшість властивостей та тверджень перевірити неважко, то

надалі не будемо кожен раз при формулюванні та доведенні тих чи інших

загальних тверджень теорії графів спеціально обумовлювати, що йдеться

про нетривіальні графи (при цьому для тривіального або порожнього графів

результат може бути дещо іншим).

 

Нехай задано граф G =(V,E ). Якщо (v,w)?Е, то кажуть, що вершини v i w є

суміжними, у противному разі вершини v i w є несуміжними. Якщо е=(v,w) (

ребро графа, то вершини v i w називаються кінцями ребра е. У цьому

-----> Page:

0 [1] [2] [3] [4]

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