Теория на графите
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |  |
Теорията на графите е клон от математиката, който изучава свойствата на графите.
Графът е абстрактна структура, която представя връзките между отделните елементи на дадено множество. Всеки член на това множество се нарича връх (на двете схеми е изобразено с число в кръг), а връзката между два върха се нарича ребро. Наименованията връх и ребро идват от най-често използваното визуално представяне на графа. Когато реброто е изобразено със стрелка (независимо едно- или двупосочна) графът е ориентиран; когато е само свързваща линия графът е неориентиран, а значението е същото като всички ребра да са с двупосочна стрелка.
История
[редактиране | редактиране на кода]Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай – дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н.
Терминът е употребен най-напред в статия на Кьониг, а след това и в монографията му „Theorie der endlichen und unendlichen Graphen“ („Теория на крайните и безкрайните графи“, 1936), но самият Кьониг го е заимствал от статия на Шур (1912), в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.
Дефиниции
[редактиране | редактиране на кода]Видове графи:
- ориентиран – ребрата са насочени, изобразяват се чрез стрелки. Две ребра, свързващи еднакви върхове, но различно ориентирани, за по-голяма прегледност се изобразяват с една двупосочна стрелка.
- неориентиран;
- претеглен (тегловен) – на всяко ребро е присвоена някаква стойност – тегло;
- мултиграф – възможно е повече от едно ребро да свързва два върха (при ориентиран граф – възможно е тези ребра освен това да са ориентирани еднакво).
Приложения на графите
[редактиране | редактиране на кода]
В практическите задачи графите представляват модел на реален обект. Ето няколко класически примера за реални обекти представяни чрез граф:
- транспортна мрежа – може да се представи чрез претеглен граф, където върховете изобразяват селищата, а свързващите ги ребра – пътищата между тях. Теглото на всяко ребро ще представлява дължината на пътя.
- родословно дърво – насочен граф, в който хората се представят чрез върхове. Насочените ребра свързват родителите с децата им. Така към всеки връх ще сочат две ребра (всеки човек има двама родители), с изключение на върховете на родоначалниците, и от всеки връх ще излизат толкова ребра колкото деца има съответният човек.
- компютърна мрежа – компютрите (върхове) и свързващите ги информационни канали (ребра).
- графови бази от данни (виж схемата за „Neo4j“).