Теория на графите

от Уикипедия, свободната енциклопедия

Теорията на графите е клон от математиката, който изучава свойствата на графите.

фиг.1
фиг.1
фиг.2
фиг.2

Графът е абстрактна структура, която представя връзките между отделните елементи на дадено множество. Всеки член на това множество се нарича връх, а връзката между два върха се нарича ребро. Наименованята връх и ребро идват от най-често използваното визуално представяне на графа, както е показано на фиг.1. Върховете са оцветени в черно, а ребрата — в зелено.

[редактиране] Дефиниции

Видове графи:

  • ориентиран (фиг.2) — ребрата са насочени, изобразяват се чрез стрелки. Две ребра, свързващи еднакви върхове, но различно ориентирани, за по-голяма прегледност се изобразяват с една двупосочна стрелка.
  • неориентиран
  • претеглен — на всяко ребро е присвоена някаква стойност — тегло.
  • мултиграф — възможно е повече от едно ребро да свързва два върха (при ориентиран граф — възможно е тези ребра, освен това, да са ориентирани еднакво).

[редактиране] Приложения на графите

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

  • транспортна мрежа — може да се представи чрез претеглен граф, където върховете изобразяват селищата, а свързващите ги ребра — пътищата между тях. Теглото на всяко ребро ще представлява дължината на пътя.
  • родословно дърво — насочен граф, в който хората се представят чрез върхове. Насочените ребра свързват родителите с децата им. Така към всеки връх ще сочат две ребра (всеки човек има двама родители), с изключение на върховете на родоначалниците, и от всеки връх ще излизат толкова ребра колкото деца е има съответния човек.
  • компютърна мрежа — компютрите (върхове) и свързващите ги информационни канали (ребра).