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