Теория на графите: Разлика между версии

{{без източници}}

 

 

Графът е абстрактна структура, която представя връзките между отделните елементи на дадено [[множество]]. Всеки член на това множество се нарича '''връх''' (на двете схеми е изобразено с число в кръг), а връзката между два върха се нарича '''ребро'''. Наименованията връх и ребро идват от най-често използваното визуално представяне на графа. Когато реброто е изобразено със стрелка (независимо едно- или двупосочна) графът е '''ориентиран'''; когато е само свързваща линия графът е '''неориентиран''', а значението е същото като всички ребра да са с двупосочна стрелка.

 

== Приложения на графите ==

В практическите задачи графите представляват модел на реален обект. Ето няколко класически примера за реални обекти представяни чрез граф:

* '''транспортна мрежа''' – може да се представи чрез претеглен граф, където върховете изобразяват селищата, а свързващите ги ребра – пътищата между тях. Теглото на всяко ребро ще представлява дължината на пътя.