- Увод
- Основни понятия
- Неориентиран граф
- Ориентиран граф
- Още определения
- Представяне
- Преобразуване
- Обхождане bfs
- Обхождане dfs
Дефиниция: Краен ориентиран граф се нарича наредената двойка (V,E), където:
– V = {v1,v2,…,vn} е крайно множество от върхове.
– Е = {e1,e2,…,em} е крайно множество от ориентирани ребра. Всеки елемент ek ∈ E (k = 1,2,…,m) е наредена двойка (vi,vj), vi,vj∈V,1≤i,j≤n.
Ако в допъление е дадена числова функция f:E→R, съпоставяща на всяко ребро ек тегло f(ek), графът се нарича претеглен. Понякога, когато няма опасност от двусмислие се казва само ребра вместо ориентирани ребра. Някои автори използват термина дъга за ориентирано ребро, а ребро – за неориентирано ребро.
Най-често, ориентиран граф се представя графично в равнината чрез множество от точки (кръгчета), означаващи върховете му и свързващи ги стрелки – ребра на графа.
фиг.1 Ориентиран граф
фиг. 2 Ориентиран претеглен граф