Page 48 - 4496

3 ГРАФИ

3.1 Область застосування теорії графів

Теорія графів застосовується в таких сферах, як фізика,
хімія, теорія зв’язку проектування ЕОМ, електротехніка,
машинобудування, архітектура, дослідження операцій,
генетика, економіка, лінгвістика. Ця теорія тісно пов’язана з
багатьма розділами математики, серед яких теорія матриць,
чисельний аналіз, теорія ймовірностей та комбінаторний
аналіз. Графи подають у вигляді діаграм, що надає їм
естетичний вигляд та привабливість.

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

Нехай V - довільна множина, що складається з
V i ,  n , 1
елементів i , а Е - сукупність пар складених з
 {(V ,V )}
елементів множини V, тобто Е i j , причому
i, j  n , 1 i  j
. Допускається, що /
Упорядкована пара G=(V,E), що складається з множини
V та сукупності Е називається графом із множиною вершин V
та множиною ребер E.

V 1

e 1 e 2

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

45