9 Приложения на линейно оптимизиране
9.1 Математическа постановка
Графът се разглежда като съвкупност от върхове (възли) и дъги (ребра). Използва се за представяне на съвкупност от обекти и техните връзки. Обикновено върховете съответстват на обектите, а дъгите - на отношенията между тях. Много задачи от различни области на науката и практиката могат да бъдат моделирани с граф и решени, като се изпълни съответният алгоритъм върху него: намиране на път между две точки, оцветяване на географска карта с най-малко цветове, движение по шахматната дъска и др.
Определения:
Граф G = (V, E) - наредена двойка от крайно непразно множество на върховете V и множество на ребрата Е. Ако ребрата са представени във вид на наредени двойки (v, w), то графът се нарича ориентиран, v е начало, а w — край на реброто (v, w). Ако ребрата са ненаредени двойки, то графът се нарича неориентиран. Ако двата края на ребро съвпадат, реброто се нарича примка.
Съседни върхове - Два върха се наричат съседни, когато съществува ребро между тях.
Степен на връх - Степента на даден връх се дефинира като броя на ребрата, чрез които той е свързан с другите върхове.
Изолиран връх - Връх от степен 0 (тоест връх, който не е свързан с други върхове) се нарича изолиран връх.
Път в граф - редица от съседни върхове (и ребрата, които ги свързват). Първият връх в редицата се нарича начало на пътя, а последният - край на пътя. Ако в пътя не се повтарят ребра, то пътят се нарича прост.
Повече информация можете да намерите тук.