Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
Теория на графите.Общи понятия.Представяне на граф.Топологично сортиране.Краен ориентиран граф се нарича наредената двойка G=(V,E), където: V={v1,v2,…,vn} е крайно множ.от върхове; E={e1,e2,…,em} е крайно множ.от ориентирани ребра. Всеки елемент (k=1,2,…,m) е наредена двойка (vi,vj), , 1≤i,j≤n. Ако ребрата на графа са неориентирани, графът се нарича неориентиран. Ако в допълнение е дадена числова функция f:E→R, съпоставяща на всяко ребро ек тегло f(ek), графът се нарича претеглен. Най-често графът се представя графично с множество от точки, изобразяващи върховете му и свързващи стрелки, които са неговите ребра. Върхът w е съседен на v тогава и само тогава, когато в неориентиран граф, ако w е съседен на v, то и v е съседен на w. Път в граф ще наричаме последователността от върхове v1,v2,v3,…,vn, такава че , 1≤i≤n. Дължина на пътя се нарича броя на ребрата в него. Ще допускаме път от върха, до самия него, като ако няма ребра, дължината му е нула. Ако графът съдържа ребро (v,v), пътят v,v се нарича примка. Ще считаме, че графът по подразбиране няма примки.Прост път се нарича път, в който всички върхове са различни, с изключение на първия и последния. Цикъл в ориентиран граф е път с минимална дължина 1, за който v1=vn. Такъв цикъл ще наричаме прост, ако пътят е прост. За ориентирани графи ще изискваме ребрата да са различни. Причина за това е, че пътят u,v,w в неориентиран граф няма да се счита за цикъл, защото (u,v) и (v,u) са едно и също ребро. В ориентиран граф това са различни ребра и ще бъде цикъл. Един ориентиран граф е ацикличен, ако няма цикли.Един неориентиран граф е свързан, ако има път от всеки връх до всеки друг. Ориентиран граф с това свойство се нарича силно свързан. Ако съществува поне един, от двата възможни пътя, между всеки два върха, ориентираният граф е слабо свързан. Пълен граф е този, в който има ребро между всяка двойка върхове. Предст. на граф може да се осъществи чрез: Двумерна матрица на съседство: на всяка дъга (u,v) се съпоставя един елемент от матрицата А[u][v] със стойност 1 или теглото на графа, когато е претеглен. Липсата на дъги се означава с 0 или ∞. Ако съществува път (u,v), но не съществува (v,u) може да се запише (-1) за да се посочи ориентацията на дъгите в матрицата. При този начин на работа е необходима Θ(│V2│) памет за съхранение на матрицата. Това води до разхищение на памет, По- ефективно представяне за разреден граф е списъка на съседство. При него за всеки връх се създава списък на съседите му. Необходимата памет тук е O(│E│+│V│). Проверката дали съществува път между два върха е по-сложна тук. Пример: особено при граф с малко дъги. Нещата са по-добре при неориентиран граф, където матрицата е симетрична относно главния диагонал и може да се съхрани като триъгълна: само под главният диагонал. В този случай разхода на памет е За неориентиран граф, списъкът на съседство включва две явявания на всяка дъга. При това паметта се удвоява. Представянето облекчава задачата за намиране на съседни върхове. Тя се извършва с просто сканиране, т.е. времето е Изтегляне 1.47 Mb. Сподели с приятели:
|