Основни понятия

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

Определения

Графът е нелинейна, динамична структура от данни, изградена от възли (върхове) и връзки между тях наречени ребра (клони, дъги).
В този смисъл графът се дефинира като съвкупност от две множества – множеството на възлите V и множеството на ребрата Е:G(V,E).
Е може да се представи като множество от двойки (x,y), където x и y принадлежат на V. x и y се наричат съседни възли. Когато двойката е наредена, т.е. (x,y)≠(y,x), то реброто се нарича ориентирано. Когато двойката е ненаредена, т.е. (x,y)=(y,x), то реброто се нарича неориентирано. Всяко неориентирано ребро може да се представи като съвкупност от две ориентирани ребра с различни посоки.


Бримка – ребро, за което началния и крайния възел съвпадат.  

Паралелни ребра– ребра, които свързват едни и същи възли.